在Haskell中进行高效的字符串交换

Question

我正在尝试解决Haskell中的函数式编程练习的问题.我必须实现一个函数,在给定一个具有偶数个字符的字符串的情况下,该函数返回相同字符串并交换字符对.

像这样:

"helloworld" - >"ehllworodl"

这是我目前的实施:

swap :: String -> String
swap s = swapRec s ""
  where
    swapRec :: String -> String -> String
    swapRec [] result       = result
    swapRec (x:y:xs) result = swapRec xs (result++[y]++[x])

我的函数返回正确的结果,但编程练习是定时的,看起来我的代码运行得太慢了.

我能做些什么来让我的代码运行得更快,或者我是否采用了错误的方法解决问题？

Answer 1

是.如果使用(++) :: [a] -> [a] -> [a],则需要在要连接的第一个列表的元素数中使用线性时间.由于result可能很大,这将导致效率低下:算法则为O(n ²).

但是,您不需要使用累加器构造结果.您可以返回一个列表,并使用递归调用处理剩余的元素,例如:

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

上面还发现了实现的问题:如果列表有一个奇数长度,那么函数就会崩溃.在第二种情况下,我们通过返回该列表来处理包含一个元素的列表(可能需要根据规范对其进行修改).

此外,我们可以从Haskell的懒惰中受益:如果我们有一个大的列表,想要通过swap函数传递它,但只对前五个元素感兴趣,那么我们就不会计算整个列表.

我们还可以使用上述函数处理各种列表:数字列表,字符串等.

需要注意的是(++)本身不是天生坏的:如果你需要连接,这当然是最有效的方式来做到这一点.问题是你在每个递归步骤中都会再次连接,左边的列表每次都在增长.