Re: overuse of maybe and [] in prelude and libs, PS
Subject: [Haskell] overuse of maybe and [] in prelude and libs Date: Wed, 7 Apr 2004 23:41:55 -0400 (Eastern Standard Time) From: "S. Alexander Jacobson" <alex@alexjacobson.com> To: Haskell Mailing List <haskell@CS.YALE.EDU>
...
PS Shouldn't concat be defined with foldl and not foldr? Doesn't foldr imply that you can't concat infinite lists? (I know this is a FAQ, but where?)
Quite in contrary: foldl (++) [] [[i] | i <- [1..]] fails to terminate, whereas foldr (++) [] [[i] | i <- [1..]] happily produces output. Ciao, Janis. -- Janis Voigtlaender http://wwwtcs.inf.tu-dresden.de/~voigt/ mailto:voigt@tcs.inf.tu-dresden.de
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
participants (2)
-
Janis Voigtlaender -
Koen Claessen