[Forgot to post to the list, sorry] 2008/6/4 Duncan Coutts <[EMAIL PROTECTED]>: > > On Wed, 2008-06-04 at 09:32 +0200, Henning Thielemann wrote: >> On Tue, 3 Jun 2008, Don Stewart wrote: >> >> > I wrote up the second part of the tour of understanding low level >> > performance in GHC here, >> > >> > http://reddit.com/r/programming/info/6lx36/comments/ >> > >> > Follows on from the discussion last week about various performance >> > related things. >> >> Now the difficult question: How to write the 'mean' function in terms of >> 'sum' and 'length' while getting the same performance? > > There's another rather harder fusion transformation that notices when > two left folds are demanded in the same strictness context and they fold > over the same input list then they can be performed together. > > sum = foldl (\s x -> s + x) 0 > length = foldl (\l x -> l + 1) 0 > > mean xs = sum xs / length xs > > So we must note that sum and length are demanded at the same time and > since they are both foldl's will consume the whole of xs. > > So we can merge the two foldl's into one just by tupling them up: > > sumlength = foldl (\(s, l) x -> (s + x, l + 1)) (0, 0) > > mean xs = s / l > where (s, l) = sumlength xs
I see a problem with this particular fusion, though: It changes the space complexity of the program, from linear to constant. Therefore, with some programs, relying on this "optimization" can be a matter of correctness, not just performance. Therefore, if it is not clear when the compiler will optimize this, I'd rather not use it. (A counter example is tail calls, which are rather easily deducible, at least in a strict context) At least, with more simple fusions, the difference was between stressing the GC or not. The space and time complexities of the problem didn't change at all. Only the constants did. Loup _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe