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

Question

注意那个简单的解决方案

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

由于复杂性的二次增长,效率不高.如果试图使用通常的foldl来折叠转换(盲目),但我的尝试

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

虽然使用foldl'编写它通常会更好:

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