[Haskell-cafe] Finding the average in constant space

Chris Wong chrisyco+haskell-cafe at gmail.com
Thu May 31 04:53:11 CEST 2012

Sorry for the delayed response -- I've had exams the past few days.

On Sun, May 27, 2012 at 8:21 PM, Eugene Kirpichov <ekirpichov at gmail.com> wrote:
> A lot of people have done this :) eg from me: google up a fairly recent thread from me about processing streams and perhaps the keyword "timeplot" (writing from a dying phone, can't do myself)

If you mean this:
and this: https://github.com/jkff/timeplot/blob/master/Tools/TimePlot/Incremental.hs
then you're right -- the types match up exactly!

The funny thing is, I remember seeing that message half a year ago and
having absolutely no idea what any of it meant. Now I've actually
tried it myself, "reifying the case expression" actually makes perfect

On Sun, May 27, 2012 at 11:43 PM, Stephen Tetley
<stephen.tetley at gmail.com> wrote:
> There are a few blog posts by Conal Elliott and Max Rabkin (I think)
> reifying folds as a data type to get more "composition" and thus fold
> different functions at the same time. Search for "beautiful folding"
> with the above authors names.
> Personally I didn't find the examples significantly more "beautiful"
> that using regular composition in a normal fold - only that that the
> helper functions to manage pairs aren't in the standard library.

This was already bookmarked, funnily enough:

I don't think that solution was particularly beautiful either. It
seems a bit over-the-top, hiding the state in an existential type when
a simple closure would do. However, I don't understand what you mean
by "regular composition in a normal fold". Wait, what's an irregular
composition? Abnormal fold? ;)

On Mon, May 28, 2012 at 7:33 AM, Steffen Schuldenzucker
<sschuldenzucker at uni-bonn.de> wrote:
> This is (a special case of) the main point in the design of iteratees. See
> e.g. the definition of the 'Iteratee' type in the enumeratee library. -
> Looks pretty much like your 'Fold' type with an additional state (done or
> not yet done).
> Also, the pipe package seems to provide something similar.

I haven't looked too much into iteratees until now, but in hindsight
it seems obvious why they're implemented that way -- they have to
iterate over a stream chunk by chunk, keeping state as they go along,
just like the Fold type. Thanks for pointing that out!


More information about the Haskell-Cafe mailing list