How can I write the inverse foldr function efficiently in Haskell?

Question

Note that the trivial solution

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

not very effective due to quadratic growth of complexity. If you tried to use normal foldl to convert foldr (blindly), but my attempt

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

didn't work as i expected.

Answer 1

Try the following:

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

Although it's usually best to write it with foldl ' :

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

Answer 2

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 them make them up:

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

((.), id) it Endo monoid, therefore

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

For the left fold, we only need the monotone Dual .

 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 simply:

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

Answer 3

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

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

The value of the accumulated g here is that it acts on its argument by adding the inverse partial tail xs to it.

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

Answer 4

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

Answer 5

old question, I know, but is there something suboptimal in this approach, it seems that foldr will be faster due to lazy evaluation, and the code is pretty concise:

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

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