[Haskell-cafe] Re: Optimization with Strings ?
apfelmus at quantentunnel.de
Fri Dec 4 06:01:42 EST 2009
Emmanuel CHANTREAU wrote:
> In my futur program, it use a lot of binary trees with strings (words)
> as leaf. There is just arround 1000 words and they will appear a lot of
> times. The program will possibly consume a lot of process and memory
> (it is a mathematics proover).
If your strings are indeed leaves, then chances are that you share them
a lot and there's nothing much to worry about. For instance, the
following complete binary tree
data Tree a = Leaf a | Branch (Tree a) (Tree a)
example a = tree 100
tree 0 = Leaf a
tree n = let t = tree (n-1) in Branch t t
uses only linear space and the argument a is stored exactly once.
I'm not sure whether this answers your question, though, also because it
depends on what exactly you want. I suggest writing a tiny prototype of
your idea and asking on the mailing list again when there are any
Also, knowing Haskell's evaluation model helps a lot
More information about the Haskell-Cafe