[Haskell-beginners] Implementing a Local Propagation Network

[Stephen Blackheath [to Haskell-Beginners]]

Patrick,

If you want to implement it in a functional style, you have to use an
association map of some sort.  Haskell only has values, but not any
concept of a reference (unless you count things like IORef, but I am not
counting those).  Generally speaking this is needed whenever you are
dealing with a data structure that has cycles.  (Generally speaking
because it's possible to make data structures lazily refer to themselves.)

People usually use IntMap, but there's a new package EnumMap on Hackage
which is really powerful.  It's like IntMap only typesafe.  You will
need a counter in your data structure as a source of unique ids.  You
can also use value-supply (from Hackage), which is a great bit of code.

On the face of it, this seems cumbersome, but the way to do it is to
create a data structure and access it through accessor functions like
"add node", "delete node", "follow wire", etc.  This way you can
abstract those details away.  People have done various directed/undirect
graph packages and so on on Hackage - I can't recommend anything.

Stick with it - this approach does work.  I've done things like
conversion of 3D models into triangle strips using this method, with
very satisfying results.


Steve

On 18/05/10 12:59, Patrick LeBoutillier wrote:
> Hi all,
> 
> After learning some Haskell recently, I decided to revisit a book
> about functional programming techniques for Perl: Higher Order Perl. I
> didn't fully understand the book at the time but now my Haskell
> experience has proved to be very insightful.
> 
> Towards the end of the book the author implements a local propagation network.
> 
> Here is the Perl source code:
> http://hop.perl.plover.com/Examples/Chap9/Local-Propagation/
> The PDF of the specific chapter is here:
> http://hop.perl.plover.com/book/pdf/09DeclarativeProgramming.pdf
> 
> I would like to experiment with something similar in Haskell, but the
> way this network is designed is all about state and references:
> 
> - Wires have a values that can change over time;
> - Wires have references to nodes;
> - Nodes have references to wires;
> 
> I'm a bit stuck as to how to approach the "object has a list
> references to other objects" situation from Haskell. I tried this:
> 
> type Name = String
> data Node = Node Name [Wire]
> data Wire = Wire Name Node Double [Node]
> 
> But that doesn't seem like it would work since when I change a Wire I
> must find all "copies" of it (in the Node objects) and update them
> also. Perhaps I should just refer to Wires/Nodes by name and use an
> association list to lookup them up, but that seems cumbersome.
> 
> Anybody have any suggestions?
> 
> 
> Thanks a lot,
> 
> Patrick
> 
> 
>