How can I write reverse by foldr efficiently in Haskell?

Question

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.

Answer 1

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