Counting occurrences of Char8s in a file To learn some Data.Map and Control.Monad.State, I have written the following code, which should count the occurrences of Char8 in a given file.

module Main where

import           Control.Monad.State
import qualified Data.ByteString.Char8 as B
import           Data.Char
import           Data.Map              (Map)
import qualified Data.Map              as M
import           Data.Maybe
import           System.Environment

type Counter = ([Char], (Char, Integer), (Char, Integer), Map Char Integer)

main :: IO ()
main = do
  file &lt;- liftM head getArgs
  string &lt;- B.readFile file
  let (chars, seldom, often, counter) = execState (countChars string) ([], (' ', 10^12), (' ', 0), M.empty)
  mapM_ (\k -&gt; putStrLn ('\'':k:"' " ++ show (fromJust $ M.lookup k counter))) chars
  putStrLn $ "minimum occurence: " ++ show (fst seldom) ++ ", " ++ show (snd seldom)
  putStrLn $ "maximum occurence: " ++ show (fst often)  ++ ", " ++ show (snd often)
  putStrLn $ "overal chars     : " ++ show (B.length string)

countChars :: B.ByteString -&gt; State Counter ()
countChars bs | B.null bs = return ()
              | otherwise = do
  let c  = B.head bs
  let cs = B.tail bs
  unless (not . isPrint $ c) $ do
    (pre, minOcc, maxOcc, counter) &lt;- get
    newPre &lt;- return $ if (c `elem` pre)
                         then pre
                         else pre ++ [c]
    newCounter &lt;- return (M.insertWith (+) c 1 counter)
    let newMinOcc = (\ (k1, v1) (k2, v2) -&gt; if v2 &lt; v1 then (k2, v2) else (k1, v1)) minOcc (c, newCounter M.! c)
    let newMaxOcc = (\ (k1, v1) (k2, v2) -&gt; if v2 &gt; v1 then (k2, v2) else (k1, v1)) maxOcc (c, newCounter M.! c)
    put (newPre, newMinOcc, newMaxOcc, newCounter)
  countChars cs


This code works as I want it for small files, counting and displaying the stats of the file, but it fails when the file gets bigger:

$ ls -l 46000.txt.utf-8
-rw-r--r-- 1 nobbz nobbz 156315 Jun 16 20:33 46000.txt.utf-8

$ ./Main 46000.txt.utf-8
Stack space overflow: current size 8388608 bytes.
Use `+RTS -Ksize -RTS' to increase it.


I don't grasp why a file of about 150kiB can overflow an 8Mib stack. If I increase to 10 MiB (./Main 46000.txt.utf-8 +RTS -k10M) it works, but using also -sstderr shows that the Program consumes 107 MiB in total.

How could I decrease memory usage, so it would work with large files and default stack-size?

Edit

Just to mention:

I want to keep the list of chars and their count of occurrence in the order of occurrence of the corresponding char, also I want that on equal count for most often and most seldom used chars that one "wins" that has occurred first.

Also I am aware of the fact that I have a file that states to be UTF-8 encoded and my program can only "see" ASCII, but I just took a random book from gutenberg.org to have a real text and not some "random" bytes in huge binarys or something comparable.
If you're using "Char8", then it would make a lot of sense to me to write a simple histogram type function using a mutable attay in the ST monad, and then calculate the minimum and maximum values at the end; there's no need to do it as you go.

import Data.Vector.Unboxed.Mutable as V
import Data.Vector.Unboxed as V
import Data.ByteString as B
import Control.Monad.ST
import Data.Char

histo :: B.ByteString -&gt; (Int,Int,Int)
histo bs = 
    let vec = create ( do
                mvec &lt;- V.replicate 256 0
                forM [0 .. B.length bs - 1] $ \i -&gt; do
                    let c = fromIntegral (B.index i bs) :: Int
                    n &lt;- unsafeRead mvec c
                    unsafeWrite mvec c (n+1)
                return mvec
                )
        f :: (Int, Int, Int) -&gt; Int -&gt; Word8 -&gt; (Int, Int, Int)
        f (mn,mx,cnt) i w =
            let mn'  = if w &gt; 0 &amp;&amp; w &lt; unsafeIndex vec mn then i else mn
                mx'  = if          w &gt; unsafeIndex vec mx then i else mx
                cnt' = if isPrint (chr . fromIntegral $ w) then cnt+1 else cnt
            in (mn', mx',cnt')

     in V.foldl' f (32, 32,0) vec -- 32 = index for ' '


This should calculate the result in constant memory (though the fold should probably be made more strict using a strict 3-tuple but all three values are forced each time f is called anyway). I haven't tested this code because I don't currently have access to a compiler so there are probably missing imports and some type errors but I hope the gist is clear.

I think this is a good demonstration of when some mutation is useful (counting lots of elements) and when functional algorithms are clearer (folding over all the data). The counting could have been done using a fold too but I think it's easier to see that here it is definitely using a constant amount of memory for the counts and should also perform quite well.