[Haskell-cafe] Right tree structure for complicated problem

[Pierre Penninckx]

Hello everyone,

So here is what I want to achieve:
I'd like a program that calculates the time needed for water to flow out of
a circuit made out of tube.
The rules are :
- There are multiple sources of water and only one exit.
- The water can only take one path from a source to the exit.
- Of course, a source of water contains a certain amount of water at the
beginning.

### Algorithm
Here's the concept of how it should be working:

#1
The tubes are connected together : 1 parent with n childs. This looks
really like a tree:
data Tree = Leaf { getVolume::Int }
                 | Path { getMaxFlow::Int
                           , getFlow::Int
                           , getOpen::Bool
                           , getChilds::[Tree}
                           }
But this structure doesn't work well :( (see later why)

When I determine the time taken by the water to flow down to the exit, I
need to take water jams (haha) into account.
To do this, the algorithm begins by the exit node and "distribute" it's
maximum flow through the childs, but only to open tubes.
And the childs distribute their flow to their own child. Repeat until you
reach a Leaf.

example :
Path 5 0 True [Path 4 0 True [], Path 3 0 True [], Path 3 0 False []]
after distribution:
Path 5 5 True [Path 4 4 True [], Path 3 2 True [], Path 3 0 False []]

#2
After the distribution, you must get the water out. Easy, the time taken by
the water to flow down is, in pseudo code:
max( for all leafs : getVolume * getFlow )

### Problem
My problem, is this : I must be able to change the "distribution" the flow
of the parent to its childs:
in my example, I said "take the biggest child, give it all you can and give
the rest to the other childs, repeat"
but I could have said "give first to the lowest child" or "give a certain
percentage depending of the sum of the childs max capacity"

So I can't map simply over the childs:
distribute :: (Int -> Int -> Int) -> Tree -> Tree
distribute _ (Leaf a) = Leaf a
distribute f path@(Path _ _ False _) = path
distribute f (Path max cur open childs) = Path max (f cur) open (map f
childs)

I must indeed let the distribution function choose to which childs it wants
to give:
distribute :: (Int -> [Tree] -> [Tree]) -> Tree -> Tree
distribute f (Path max use open child) = Path max use open $ map
(distribute (f use)) newChilds
    where newChilds = f use childs

And I find this quite awful...
I know Hakell is everything about data structure, so I suppose my data
structure is awful too.
Do you have any suggestions/remarks to help me?

Sorry I made it so long, but you needed to know what I wanted to acheive to
help me (I hope I made it crystal clear ^^).
Thanks,
Ibiz
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20120122/d212c9e6/attachment-0001.htm>