3 ms·

That's a problem for which imperative solution has a very direct fit. If you want to do everything in a purely-functional manner, some stuff is just going to be

That's a problem for which imperative solution has a very direct fit. If you want to do everything in a purely-functional manner, some stuff is just going to be awkward or hard to do efficiently, period. There are other cases where the functional solution is ideal, and trying to solve it imperatively becomes clumsy and bug-ridden. A sufficiently large project will probably have at least a few of each (or a small implementation of half of Prolog, etc.). This is why using a multiparadigm language (like OCaml or the various Lisps) or an FFI to work in a few complementary languages is often a practical approach. Working solely in a pure-(one thing) language often involves over-committing to a specific trade-off. Edit: Or, yes, the imperative sub-language embedded in the state monad.

eru 18y ago
Or Haskell and the StateMonad, if you need imperativeness. (Though I do not advocate it for this problem.) However, functional solutions to this specific problem are not cumbersome at all. See for example this snippet of literate Haskell. It assumes that you have already put your binary data in a list of chars and return a Map (similary to a Python dict) of frequencies: > import qualified Data.Map as M > freqMap :: [Char] -> M.Map Char Int > freqMap list = foldr op M.empty list > where op :: Char -> M.Map Char Int -> M.Map Char Int > op c freq_map = M.insertWith (+) c 1 freq_map
- silentbicycle 18y ago
  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.
henning 18y ago
If you want to keep everything pure and also reasonably efficient, I think you need a sophisticated type system and a good compiler to back you up, e.g. Haskell and GHC.
- silentbicycle 18y ago
  Dude, you don't need a sophisticated type system to count the occurrences of the numbers 0 to 255. Talk about, "Let's Take a Trivial Problem and Make it Hard".
  - henning 18y ago
    For this trivial contrived situation, yes. For the general problem of doing things purely where you would otherwise use destructive updates, you need a type system that lets the compiler safely and correctly figure things out about your program. Sheesh.
    - silentbicycle 18y ago
      I agree that sometimes it helps to have the type system in non-trivial situations, but in OCaml, you could do this imperatively, keep the state change isolated to a specific function (or module), and still give it a pure functional interface. The type system would do the same checks, even. (It sounds like that's what happens with Haskell's Data.Array.Diff.) At the same time, many programs in the real world get by without sophisticated type systems. They're a great tool, but they're also probably vastly more useful in some problem domains than others. Same with OOP, constraints and backtracking, relational databases, etc. (That said, I would love to use an ML-like language as small & clean as Lua. Inferred, garbage-collected, recursive tagged-union types rule.)

eru 18y ago

Or Haskell and the StateMonad, if you need imperativeness. (Though I do not advocate it for this problem.) However, functional solutions to this specific problem are not cumbersome at all. See for example this snippet of literate Haskell. It assumes that you have already put your binary data in a list of chars and return a Map (similary to a Python dict) of frequencies: > import qualified Data.Map as M > freqMap :: [Char] -> M.Map Char Int > freqMap list = foldr op M.empty list > where op :: Char -> M.Map Char Int -> M.Map Char Int > op c freq_map = M.insertWith (+) c 1 freq_map

silentbicycle 18y ago
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.

henning 18y ago

If you want to keep everything pure and also reasonably efficient, I think you need a sophisticated type system and a good compiler to back you up, e.g. Haskell and GHC.

silentbicycle 18y ago
Dude, you don't need a sophisticated type system to count the occurrences of the numbers 0 to 255. Talk about, "Let's Take a Trivial Problem and Make it Hard".
- henning 18y ago
  For this trivial contrived situation, yes. For the general problem of doing things purely where you would otherwise use destructive updates, you need a type system that lets the compiler safely and correctly figure things out about your program. Sheesh.
  - silentbicycle 18y ago
    I agree that sometimes it helps to have the type system in non-trivial situations, but in OCaml, you could do this imperatively, keep the state change isolated to a specific function (or module), and still give it a pure functional interface. The type system would do the same checks, even. (It sounds like that's what happens with Haskell's Data.Array.Diff.) At the same time, many programs in the real world get by without sophisticated type systems. They're a great tool, but they're also probably vastly more useful in some problem domains than others. Same with OOP, constraints and backtracking, relational databases, etc. (That said, I would love to use an ML-like language as small & clean as Lua. Inferred, garbage-collected, recursive tagged-union types rule.)