我在尝试理解 Haskell 上的折叠实现时遇到了很多问题。我需要使用具有此输出的 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)
最佳答案
将折叠视为获取术语列表:
[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)))
请注意,初始值也是 fold 应用于空列表时的值,因此通常很容易计算出来。困难的部分是定义适当的二元运算符。
所以,表达runLengthEncode
作为正确的折叠,你需要:
'a' <+> ('a' <+> ('a' <+> ('b' <+> zz))) = [(3,'a'),(1,'b')]
对于运算符(operator) <+>
和一些初始值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 的 last 元素而不是第一个元素。当然可以,但是稍微不自然,这就是我在上面使用右折叠的原因。
对于 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
关于function - Haskell 中的折叠实现,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/55327293/