[Haskell-cafe] Re: Optimization with Strings ?

Heinrich Apfelmus 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
performance problems.

Also, knowing Haskell's evaluation model helps a lot


Heinrich Apfelmus


More information about the Haskell-Cafe mailing list