3 ms·

Could that be adapted to work for a stream, rather than a complete list in memory? That could become a constraint on the problem under reasonable circumstances.

Could that be adapted to work for a stream, rather than a complete list in memory? That could become a constraint on the problem under reasonable circumstances. If it was a list of chars, it makes sense to just accumulate counts over the list (which is what you're doing, I think). I'm not great at Haskell (GHC > 6.6 won't install on my main computer... http://hackage.haskell.org/trac/ghc/ticket/1346 http://hackage.haskell.org/trac/ghc/ticket/1346 ), and while I understand the type system etc. from using OCaml, in that, I would just do this imperatively and give it a functional interface. I'm not just being difficult, I'm curious how you'd go about it. (Edit: Cool, thanks.)

eru 18y ago
Thanks for your question. There's nothing that prevents the general technique from working on a stream. I guess every sensible implementation of streams supports folds.
mbrubeck 18y ago
Since Haskell lists are lazy, they aren't necessarily in memory all at once. For example, the standard "getContents" function reads a file and returns a list of characters. But since it returns a lazily-evaluated list, you can read arbitrarily large files and they will be streamed efficiently as you consume the list. This is the same laziness that lets Haskell operate on infinite lists like [1..]
- eru 18y ago
  Yes, I guess you are right. I have been bitten a few times by questions of memory before, so I was cautious in my answer. There's still a lot for me to learn about how lazyness impacts memory requirements. (Some times Haskell was lazier than I was expecting and kept thunks in memory that were bigger than their eventual result.)
  - silentbicycle 18y ago
    While it probably wasn't clear, that's what I was wondering about when I asked about using streams. I find using lazy evaluation by default confusing sometimes, so I think about it terms of using streams or iterators. (Or are they called generators? The kind of function that, when called, returns either the next value or an end-of-stream sentinel.)
    - eru 18y ago
      Python calls them generators. Haskell lists display somewhat similar behaviour. Although I still have to learn a lot, lazyness by default brings more benefits than it costs IHMO.

eru 18y ago

Thanks for your question. There's nothing that prevents the general technique from working on a stream. I guess every sensible implementation of streams supports folds.

mbrubeck 18y ago

Since Haskell lists are lazy, they aren't necessarily in memory all at once. For example, the standard "getContents" function reads a file and returns a list of characters. But since it returns a lazily-evaluated list, you can read arbitrarily large files and they will be streamed efficiently as you consume the list. This is the same laziness that lets Haskell operate on infinite lists like [1..]

eru 18y ago
Yes, I guess you are right. I have been bitten a few times by questions of memory before, so I was cautious in my answer. There's still a lot for me to learn about how lazyness impacts memory requirements. (Some times Haskell was lazier than I was expecting and kept thunks in memory that were bigger than their eventual result.)
- silentbicycle 18y ago
  While it probably wasn't clear, that's what I was wondering about when I asked about using streams. I find using lazy evaluation by default confusing sometimes, so I think about it terms of using streams or iterators. (Or are they called generators? The kind of function that, when called, returns either the next value or an end-of-stream sentinel.)
  - eru 18y ago
    Python calls them generators. Haskell lists display somewhat similar behaviour. Although I still have to learn a lot, lazyness by default brings more benefits than it costs IHMO.