[Haskell] Re: overuse of maybe and [] in prelude and libs, PS

[Koen Claessen]

Janis Voigtlaender wrote:

 |   foldl (++) [] [[i] | i <- [1..]]
 |
 | fails to terminate, whereas
 |
 |   foldr (++) [] [[i] | i <- [1..]]
 |
 | happily produces output.

Indeed, and evan for finite lists we have that

  foldl (++) [] [[i] | i <- [1..n]]

has quadratic time behavior in n, whereas

  foldr (++) [] [[i] | i <- [1..n]]

behaves linearly in n.

/Koen

--
Koen Claessen        http://www.cs.chalmers.se/~koen/
Chalmers University of Technology, Gothenburg, Sweden