如何列出Haskell中所有可能替换的项目？

Question

我的输入是一个任意列表,例如

["a","b","c"]

还有另一个列表元素"z".我希望输出看起来像:

[["z","b","c"],["a","z","c"],["a","b","z"]]

我该怎么做呢？

Answer 1

replace :: [a] -> a -> [[a]]
replace []     _special = []
replace (x:xs) special  = (special:xs) : map (x:) (replace xs special)

测试:

> replace ["a","b","c"] "z"
[["z","b","c"],["a","z","c"],["a","b","z"]]

说明:

我们希望生成所有列表,其中只有一个元素被一个元素替换special.

如果列表为空,则无法插入special,因此我们不返回任何选项.

如果是列表x:xs,则替换x和获取一个选项special:xs.其他选项可以通过递归地以任何方式插入special尾部来计算xs,最后x在每个选项前面加前面.

Answer 2

使用列表没有有效的方法; 渐渐地,你能做的最好的事情就是

replace x xs = zipWith f (inits xs) (dropLast $ tails xs)
  where
    f front (_ : rear) = front ++ x : rear

dropLast [] = []
dropLast [_] = []
dropLast (x:xs) = x : dropLast xs

注意:这仅适用于基础4.7.0.2或更高版本(GHC 7.8.4或更高版本).

/sf/answers/2268207861/演示了一种更清洁的方式,tail而不是使用dropLast.

这里棘手的部分隐藏在inits其中,在最近的版本中,它们非常有效且兼具效率和懒惰.

如果你真的想快速完成这个操作,你必须放弃列表并使用其他表示.

import Data.Sequence

replace :: a -> Seq a -> Seq (Seq a)
replace x xs = mapWithIndex f xs
  where
    f i _ = update i x xs

Answer 3

这看起来像一个家庭作业的问题,所以这个答案可能不会帮助你,但我喜欢解决这类问题,使用inits和tails从Data.List.

看看如何inits和tail .tails工作:

as = inits [1..3]        = [ [],    [1], [1,2], [1,2,3] ]
bs = tail (tails [1..3]) = [ [2,3], [3], [] ]
cs = [1..3]              = [ 1,     2,     3]

这些问题中的许多都是这些列表的3向拉链的功能.例如,这个问题的解决方案是:

[ a ++ "z" ++ b | (a,b) <- zip as bs ]

或者,如果您需要为每个元素添加1:

[ a ++ [c+1] ++ b | (a,b,c) <- zip3 as bs cs ]

或删除每个元素:

[ a ++ b | (a,b) <- zip as bs ]

请注意,即使as比bszip 更长,也会迭代正确数量的元素.