Haskell中的高效字符串交换

对。如果你使用 (++) :: [a] -> [a] -> [a] 第一 result O(无) ) .

但是你没有 需要

swap :: [a] -> [a]
swap [] = []
swap [x] = [x]
swap (x:y:xs) = y : x : swap xs

上述内容还揭示了实现中的一个问题:如果列表长度为奇数,那么函数就会崩溃。在第二种情况下,我们通过返回一个元素来处理一个列表(也许您需要根据规范对此进行修改)。

此外,在这里我们可以从哈斯克尔的懒惰中获益:如果我们有一个大的列表,想通过 swap 不

请注意 (++) 固有的 ,左边的列表每次都在增长。

在累加器的末端粘贴某物 递归调用

    swapRec (x:y:xs) resultSoFar  =  swapRec xs 
         (resultSoFar ++ [y] ++ [x])

与在返回结果的开头加上相同 从 递归调用:

    swapRec (x:y:xs)  =  [y] ++ [x] ++ swapRec xs 

你必须自始至终相应地修改你的职能。

折叠)。

另一个好处是现在 在线 (即采取 每个处理元素的时间)。你在创造 (++) 在树上筑巢 左边 二次的 行为,例如。 here .