Pedro Baltazar Vasconcelos wrote: > > Two solutions using immutable and mutable arrays and no unsafe operations:
Both solutions certainly count as nice, but both exhibit an ugly memory
leak. As usual, this is due to too much laziness: no intermediate
result is ever evaluated until it is too late. GHCi dies on both (freq1
$ replicate 1000000 'x') and (freq2 $ replicate 1000000 'x') with a
stack overflow.
Both versions can be fixed by using unboxed arrays, which is fine when
counting Ints, but already impossible with Intergers. The mutable
version has an easy general fix:
> -- using mutable ST arrays
> hist2 :: String -> STArray s Char Int -> ST s ()
> hist2 str arr = sequence_ [do { i<-readArray arr c; writeArray arr c $! 1+i }
> | c<-str]
Note the strict application ^^
What I find unsettling, is that the nice solution, the only one not to
rely on GHC specific extensions, cannot be fixed:
> hist1 str = accumArray (+) 0 ('\0','\255') [(c,1) | c<-str]
No amount of strictness annotations can fix this, the correct place
would be *inside* accumArray. The same problem arises with other
containers that provide accum-like functions, notably
Data.Map.insertWith and Data.Map.mapAccum.
That raises the question: Should combining functions on containers be
provided in a strict variant? Should strict application be the default?
If something turns out to be too strict, I can always wrap it in a data
type; if it turns out to be too lazy, I'm hosed. Or am I overlooking
something?
Udo.
signature.asc
Description: Digital signature
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
