[Haskell-cafe] Space Leak Help

[Dominic Steinitz]

On Saturday 03 February 2007 19:42, kahl at cas.mcmaster.ca wrote:
>  > I have re-written SHA1 so that is more idiomatically haskell and it is
>  > easy to see how it implements the specification. The only problem is I
>  > now have a space leak. I can see where the leak is but I'm less sure
>  > what to do about getting rid of it.
>  >
>  > Here's the offending function:
>  >
>  > pad :: [Word8] -> [Word8]
>  > pad xs =
>  >    xs ++ [0x80] ++ ps ++ lb
>  >    where
>  >       l = length xs
>  >       pl = (64-(l+9)) `mod` 64
>  >       ps = replicate pl 0x00
>  >       lb = i2osp 8 (8*l)
>
> I would try something along the following lines (untested):
>
> \begin{spec}
> catWithLen xs f = xs ++ f (length xs)
> \end{spec}
>
> \begin{code}
> catWithLen :: [a] -> (Int -> [a]) -> [a]
> catWithLen xs f = h 0 xs
>   where
>     h k [] = f k
>     h k (x : xs) = case succ k of            -- forcing evaluation
>                      k' -> x : h k' xs
> \end{code}
>
> \begin{code}
> pad :: [Word8] -> [Word8]
> pad xs = catWithLen xs f
>   where
>     f l = 0x80 : ps lb
>       where
>          -- we know that |l = length xs|
>          pl = (64-(l+9)) `mod` 64
>          ps = funPow pl (0x00 :)
>          lb = i2osp 8 (8*l)
> \end{code}
>
> If you are lucky, then the replicate and the (++lb) in the original code
> might be fused by the compiler as an instance of foldr-build
> or something related --- check the optimised core code.
>
Wolfram,

Thanks but this gives a different problem:

dom at heisenberg:~/sha1> ./allInOne 1000001 +RTS -hc -RTS
[2845392438,1191608682,3124634993,2018558572,2630932637]
[2224569924,473682542,3131984545,4182845925,3846598897]
Stack space overflow: current size 8388608 bytes.
Use `+RTS -Ksize' to increase it.

Dominic.