[Haskell-cafe] Re: k-minima in Haskell

Nicolas Frisby nicolas.frisby at gmail.com
Thu Apr 12 23:10:09 EDT 2007


Both Yitzchak's and my suggestions should run in constant space--some
strictness annotation or switching to foldl' might be necessary.

On 4/12/07, Mark T.B. Carroll <mark at ixod.org> wrote:
> Dan Weston <westondan at imageworks.com> writes:
>
> > Ah, but which k elements? You won't know until you've drained your
> > entire stream!
>
> True, but you still don't need to keep the whole stream in memory at
> once, just the k-least-so-far as you work your way through the stream -
> once you've read a part of the stream you can mostly forget it again.
> The question as I understood it was one of if even in Haskell there's a
> better way than sorting that means you need only have a fragment of the
> stream in memory at once.
>
> -- Mark
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>


More information about the Haskell-Cafe mailing list