On Monday 16 May 2011 22:26:18, I wrote:
On Monday 16 May 2011 20:49:35, austin seipp wrote:
As you can see, with the foldr definition, GHC is able to fuse the iteration of the input list with the generation of the result - note the 'GHC.Base.++' call with the first argument being a list from [x..x*2], and the second list to append being a recursive call. So it simplifies the code quite a bit - it doesn't really end up traversing a list, but instead generating a list only in this case, as it stores current iteration in a Int# and has the upper limit inlined into the case statement.
I don't know why GHC doesn't have this rule by default, though.
Probably because it's not good. The core it generates for concatMap is better. ...
Aw, but that's some black magic which only works under special circumstances. You need nice types and a nice k for that to work out so neatly. Give it less to work on (a less simple k, for example) and you get the same for concatMap k, concat . map k and for foldr ((++) . k) [].