[Haskell-beginners] Understanding program stack usage

Patrick LeBoutillier patrick.leboutillier at gmail.com
Wed Apr 27 16:52:21 CEST 2011


I've written a program that reads doubles from stdin and creates a
distribution of the data according
to specified ranges. The program works ok and speed is acceptable (17
secs for 300000 entries),
but to run it I have to increase stack size:

$ cat input | ./distrib +RTS -K100000000 -RTS

How do I figure out why the program needs a lot of stack?
Also, is there an easy way to increace performance?



import qualified Data.Map as M
import Data.List (sort, foldl')
import qualified Data.ByteString.Char8 as L
import Data.ByteString.Lex.Double

data Range n = Range n n | OutOfBounds
                 deriving (Eq, Ord, Show)

data Distrib n = Distrib (M.Map (Range n) Int) [Range n]
                 deriving (Show)

mkDist :: (Ord n) => [n] -> Distrib n
mkDist ns = Distrib M.empty ranges
  where ranges = zipWith Range l (tail l)
        l = sort ns

record :: (Ord n) => n -> Distrib n -> Distrib n
record n (Distrib m rs) = Distrib (M.alter f slot m) rs
  where f (Just n) = Just $ n + 1
        f Nothing = Just 1
        slot = findSlot n rs
        findSlot x (r@(Range a b):rs)
          | x >= a && x < b = r
          | otherwise       = findSlot x rs
        findSlot x []       = OutOfBounds

mkDouble :: L.ByteString -> Double
mkDouble bs = case readDouble bs of
                 Just (d, rest) -> d

main = do
  let d = mkDist [0, 5, 10, 50, 100]
  bs <- L.getContents
  let ds = map (abs . mkDouble) . L.lines $ bs
  let (Distrib m _) = foldr (\n acc -> record n acc) d ds
  putStrLn . show $ m

Patrick LeBoutillier
Rosemère, Québec, Canada

More information about the Beginners mailing list