[Haskell-cafe] Re: Optimization with Strings ?

[Heinrich Apfelmus]

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
      where
      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

  http://en.wikibooks.org/wiki/Haskell/Graph_reduction


Regards,
Heinrich Apfelmus

--
http://apfelmus.nfshost.com