代码之家 › 专栏 › 技术社区 › Matteo Ugolotti

Haskell中的高效字符串交换

haskell

5

Matteo Ugolotti · 技术社区 · 7 年前

我在为Haskell的函数式编程练习解决一个问题。我必须实现这样一个函数:给定一个字符数为偶数的字符串,该函数返回交换了字符对的相同字符串。

这是我当前的实现:

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])

我的函数返回正确的结果,但是编程练习是定时的,而且我的代码似乎运行得太慢。

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

2 回复 | 直到 7 年前

1

9

willeM_ Van Onsem 7 年前

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

但是你没有需要

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

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

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

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

2

3

Will Ness Derri Leahy 6 年前

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

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

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

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

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

折叠)。

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