[Haskell-cafe] Painting logs to get a coloured tree

[Joachim Breitner]

Hi,

I have a problem that, it seems, I can not solve cleanly without
resorting to imperative programming (via ST):

Assume you have a tree (and you can think of a real tree here), defined
by something like this:

data Tree a = Bud | Branch a Double Tree Tree
--                         | ` Lenght of this branch
--                         ` General storage field for additional information

Now, I have a nice algorithm that calulates something for each branch,
but it only works on lists of branches, so I have to cut them apart
first, remembering their position in space, and then work on these,
well, logs.

data Point = Point Double Double
data Log = Log Point Point
type Info = ...
noInfo :: Info

cutTreeApart :: Tree a -> [(Log, a)]
someAlgorithm :: [(Log,a)] -> [(a, Info)]

Conveniently, the algorithm allows me to tag the logs with something, to
be able to keep track at least somewhat of the logs.

Unfortunately, I need this information in the storage field in my Tree,
as the list of logs is not sufficient for later calculations.

Idea: Using ST
==============

annotateTree :: Tree a -> Tree Info
annotateTree tree = runSt $ do
	-- Put an STRef in each node
        treeWithPointer <- mapM const (newSTRef noInfo) tree
        -- Cut this tree apart
        let logsWithPointers = cutTreeApart treeWithPointer
        -- Run the algorithm
        let informations = someAlgorithm logsWithPointers
        -- Put the information back, via the ST ref
        mapM (\(stRef, info) -> writeSTRef stRef info) informations
        -- Read the ST refs
        mapM readIORef tree

Note that I assume a instance Traversable Tree here, and mapM is
Data.Traversable.mapM.


Now while this works, and while ST is still somewhat pure, I’m wondering
if there is no better way of expressing "This piece of information came
from the point in a data structure, so something else can be put here
easily".

Some ideas where numbering the Nodes and then using this number as the
tag on the log, but this is not much different from using STRefs, it
seems.

Thanks,
Joachim

-- 
Joachim "nomeata" Breitner
  mail: mail at joachim-breitner.de | ICQ# 74513189 | GPG-Key: 4743206C
  JID: nomeata at joachim-breitner.de | http://www.joachim-breitner.de/
  Debian Developer: nomeata at debian.org
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 197 bytes
Desc: Dies ist ein digital signierter Nachrichtenteil
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20090209/790d63f8/attachment.bin