折叠Haskell中的实现

Question

我在尝试理解Haskell上的folds实现时遇到了很多问题。我需要使用具有此输出的fold的两个函数

> runLengthEncode "aaaaaaabbb"
[(7,'a'),(3,'b')]
> runLengthDecode [(1,'h'), (5,'i')]
"hiiiii"

所以我所做的就是首先编写函数，就像模式匹配一​​样（它们可以工作），但现在我不知道如何使用向左折叠或向右折叠来“翻译”。

runLengthEncode :: String -> [(Int,Char)]
runLengthEncode [] = []
runLengthEncode (x:xs) = runLengthEncode 1 x xs
    where
        runLengthEncode n x [] = [(n,x)]
        runLengthEncode n x (y:ys) | x == y = runLengthEncode (n + 1) y ys
                                   | otherwise = (n,x) : runLengthEncode 1 y ys

runLengthDecode :: [(Int,Char)] -> String
runLengthDecode [] = []
runLengthDecode ((a,b):xs) = replicate a b ++ (runLengthDecode xs)

Answer 1

将折叠视为列出术语列表：

[a,b,c,d]

并在术语之间添加初始值zz和二元运算符<+>：

foldl (<+>) zz [a,b,c,d] = (((zz <+> a) <+> b) <+> c) <+> d
foldr (<+>) zz [a,b,c,d] = a <+> (b <+> (c <+> (d <+> zz)))

请注意，初始值也是应用于空列表时折叠的值，因此通常很容易理解。困难的部分是定义适当的二元运算符。

因此，要将runLengthEncode表示为正确的折叠，您需要：

'a' <+> ('a' <+> ('a' <+> ('b' <+> zz))) = [(3,'a'),(1,'b')]

对于运营商<+>和一些初始值zz。

我们可以很容易地“解决”zz，因为我们知道runLengthEncode [] = []，所以zz = []。我们需要定义<+>，以便它满足从上面的例子（从右到左工作）得到的方程，如：

'b' <+> [] = [(1, 'b')]
'a' <+> [(1, 'b')] = [(1, 'a'), (1, 'b')]
'a' <+> [(1, 'a'), (1, 'b')] = [(2, 'a'), (1, 'b')]
'a' <+> [(2, 'a'), (1, 'b')] = [(3, 'a'), (1, 'b')]

定义这样的运算符实际上非常简单：

(<+>) :: Char -> [(Int, Char)] -> [(Int, Char)]
x <+> ((n, y) : rest) | x == y = ((n+1), y) : rest
x <+> rest                     = (1, x) : rest

所以我们得到：

runLengthEncode' :: String -> [(Int,Char)]
runLengthEncode' = foldr (<+>) []

尝试使用左折也可以这样做：

(((zz + 'a') <+> 'a') <+> 'a') <+> 'b' =>  [(3,'a'),(1,'b')]

你会发现，当定义<+>时，你必须检查当前RLE的最后一个元素而不是第一个元素。当然，它可以做到，但它稍微不那么自然，这就是为什么我使用了正确的折叠。

对runLengthDecode来说，这是同样的事情：

(1, 'h') <+> ((5, 'i') <+> zz) = "hiiiii"

再次，确定zz应该是什么。然后，弄清楚如何编写二进制运算符来解决：

(5, 'i') <+> zz = "iiiii"
(1, 'h') <+> "iiiii" = "hiiiii"

剧透人员跟随......

当然，您实际上并不需要使用运算符语法，因此完整的解决方案如下所示：

runLengthEncode'' :: String -> [(Int,Char)]
runLengthEncode'' = foldr step []
  where step x ((n, y) : rest) | x == y = ((n+1), y) : rest
        step x rest                     = (1, x) : rest

runLengthDecode'' :: [(Int,Char)] -> String
runLengthDecode'' = foldr step ""
  where step (n, x) str = replicate n x ++ str