如何在 Haskell 中有效地通过foldr 编写反向操作？

Question

请注意，由于复杂性呈二次方增长，平凡的解决方案

reverse a = foldr (\b c -> c ++ [b] ) [] a

效率不高。如果尝试使用通常的foldl 到foldr 转换（盲目地），但我的尝试

foldr (\b g x -> g ((\x old -> x:old) x b)) id list []

没有按我的预期工作。

Answer 1

试试这个：

reverse bs = foldr (\b g x -> g (b : x)) id bs []

虽然通常使用

reverse = foldl' (flip (:)) []

Answer 2

考虑以下内容：

foldr (<>) seed [x1, x2, ... xn] == x1 <> (x2 <> (... <> (xn <> seed)))

让我们将其“切割”成碎片：

(x1 <>) (x2 <>) ... (xn <>)  seed

现在我们有了这堆函数，让我们组合它们：

(x1 <>).(x2 <>). ... .(xn <>).id $ seed

((.), id) 它是 Endo 幺半群，所以

foldr (<>) seed xs == (appEndo . foldr (mappend.Endo.(<>)) mempty $ xs) seed

对于左折叠，我们只需要 Dual 幺半群。

leftFold (<>) seed xs = (appEndo . getDual . foldr (mappend . Dual . Endo . (<>)) mempty $ xs) seed

(<>) = (:) 和 seed = []

reverse' xs = (appEndo . getDual . foldr (mappend . Dual . Endo . (:)) mempty $ xs) []

或者简单：

reverse' xs = (appEndo . foldr (flip mappend . Endo . (:)) mempty $ xs) []
reverse' xs = (foldr (flip (.) . (:)) id $ xs) []
reverse' = flip (foldr (flip (.) . (:)) id) []

Answer 3

基本上，您需要将 1:2:3:[] 转换为 (3:).(2:).(1:) 并将其应用于 []。因此：

reverse' xs = foldr (\x g -> g.(x:)) id xs []

这里累积的 g 的含义是，它通过将 xs 的反向部分尾部附加到它的参数上来作用于它的参数。

对于 1:2:3:[] 示例，在最后一步中 x 将是 3，g 将是 (2:).(1:)。

Answer 4

foldl (\acc x -> x:acc) [] [1,2,3]

Answer 5

老问题，我知道，但是这种方法有什么非最佳的吗，由于惰性求值，foldr 似乎会更快，并且代码相当简洁：

 reverse' :: [a] -> [a]
 reverse' = foldr (\x acc -> acc ++ [x]) []

(++) 明显慢于 (:)，这需要FUZxxl 的回答中显示了一些逻辑上的扭曲

Answer 6

reverse = Foldl(\ ab -> b :a) []