It's pretty easy to represent a tree in haskell:
data Tree a = Node Tree a Tree | Leaf a
but that's because it has no need for the concept of an imperative style "pointer" because each Node/Leaf has one, and only one parent. I guess I could represent it as a list of lists of Maybe Ints ...to create a table with Nothing for those nodes without a path between and Just n for those that do... but that seems really ugly and unwieldy.
Disclaimer: below is a mostly pointless exercise in "tying the knot" technique. Fgl is the way to go if you want to actually use your graphs. However if you are wondering how it's possible to represent cyclic data structures functionally, read on.
It is pretty easy to represent a graph in Haskell!
-- a directed graph
data Vertex a b = Vertex { vdata :: a, edges :: [Edge a b] }
data Edge a b = Edge { edata :: b, src :: Vertex a b, dst :: Vertex a b }
-- My graph, with vertices labeled with strings, and edges unlabeled
type Myvertex = Vertex String ()
type Myedge = Edge String ()
-- A couple of helpers for brevity
e :: Myvertex -> Myvertex -> Myedge
e = Edge ()
v :: String -> [Myedge] -> Myvertex
v = Vertex
-- This is a full 5-graph
mygraph5 = map vv [ "one", "two", "three", "four", "five" ] where
vv s = let vk = v s (zipWith e (repeat vk) mygraph5) in vk
This is a cyclic, finite, recursive, purely functional data structure. Not a very efficient or beautiful one, but look, ma, no pointers! Here's an exercise: include incoming edges in the vertex
data Vertex a b = Vertex {vdata::a, outedges::[Edge a b], inedges::[Edge a b]}
It's easy to build a full graph that has two (indistinguishable) copies of each edge:
mygraph5 = map vv [ "one", "two", "three", "four", "five" ] where
vv s =
let vks = repeat vk
vk = v s (zipWith e vks mygraph5)
(zipWith e mygraph5 vks)
in vk
but try to build one that has one copy of each! (Imagine that there's some expensive computation involved in e v1 v2).