CODEWITHSUNDEEP
haskell
shuhalo
shuhalo

Reputation: 6462

How can I write reverse by foldr efficiently in Haskell?

Note that the trivial solution

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

is not very efficient, because of the quadratic growth in complexity. If have tried to use the usual foldl to foldr conversion (blindly), but my attempt

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

did not work as I expected.

Upvotes: 10

Views: 13641

Answers (6)

Srinath
Srinath

Reputation: 66

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

Upvotes: 0

low_ghost
low_ghost

Reputation: 590

old question, I know, but is there anything non-optimal about this approach, it seems like foldr would be faster due to lazy evaluation and the code is fairly concise:

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

is (++) significantly slower than (:), which requires a few logical twists as shown in FUZxxl's answer

Upvotes: 0

fuz
fuz

Reputation: 93107

Try this:

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

Though it's usually really better to write it using foldl':

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

Upvotes: 24

comco
comco

Reputation: 573

Basically, you need to transform 1:2:3:[] into (3:).(2:).(1:) and apply it to []. Thus:

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

The meaning of the accumulated g here is that it acts on its argument by appending the reversed partial tail of xs to it.

For the 1:2:3:[] example, in the last step x will be 3 and g will be (2:).(1:).

Upvotes: 4

ivan_a
ivan_a

Reputation: 613

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

Upvotes: 0

klapaucius
klapaucius

Reputation: 1102

Consider the following:

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

Let's just "cut" it into pieces:

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

Now we have this bunch of functions, let's compose them:

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

((.), id) it's Endo monoid, so

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

For left fold we need just Dual monoid.

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

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

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

Or simple:

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

Upvotes: 9

Related Questions