How do you represent a graph in Haskell?

by

In shang’s answer you can see how to represent a graph using laziness. The problem with these representations is that they are very difficult to change. The knot-tying trick is useful only if you’re going to build a graph once, and afterward it never changes.

In practice, should I actually want to do something with my graph, I use the more pedestrian representations:

  • Edge list
  • Adjacency list
  • Give a unique label to each node, use the label instead of a pointer, and keep a finite map from labels to nodes

If you’re going to be changing or editing the graph frequently, I recommend using a representation based on Huet’s zipper. This is the representation used internally in GHC for control-flow graphs. You can read about it here:

More Related Contents:

  1. Abusing the algebra of algebraic data types – why does this work?
  2. Haskell: moving image on horizontal line
  3. Getting started with Haskell
  4. Applicatives compose, monads don’t
  5. How do I define Lisp’s apply in Haskell?
  6. What does (f .) . g mean in Haskell?
  7. Is there a Haskell idiom for updating a nested data structure?
  8. What are paramorphisms?
  9. Is monad bind (>>=) operator closer to function composition (chaining) or function application?
  10. Large-scale design in Haskell? [closed]
  11. How to compare two functions for equivalence, as in (λx.2*x) == (λx.x+x)?
  12. Should do-notation be avoided in Haskell?
  13. How to infer the type of an expression manually
  14. Haskell: I/O and Returning From a Function
  15. Ordering of parameters to make use of currying
  16. Typeclass constraints on data declarations
  17. Type Constraints in Data Declaration Haskell
  18. How to use (->) instances of Monad and confusion about (->)
  19. Why can a Num act like a Fractional?
  20. What part of Hindley-Milner do you not understand?
  21. What does the `forall` keyword in Haskell/GHC do?
  22. Iterate over all pair combinations without repetition in Haskell
  23. What’s the status of multicore programming in Haskell?
  24. What does “pure” mean in “pure functional language”?
  25. Implement zip using foldr
  26. How to enumerate a recursive datatype in Haskell?
  27. Functional lenses
  28. How to compare two functions for extensional equivalence, as in (λx.2*x) == (λx.x+x)?
  29. ‘some’ and ‘many’ functions from the ‘Alternative’ type class [duplicate]
  30. Sampling sequences of random numbers in Haskell

Leave a Comment