Sign up ×

I'm currently playing with LISP (particularly Scheme and Clojure) and I'm wondering how typical data structures are dealt with in functional programming languages.

For example, let's say I would like to solve a problem using a graph pathfinding algorithm. How would one typically go about representing that graph in a functional programming language (primarily interested in pure functional style that can be applied to LISP)? Would I just forget about graphs altogether and solve the problem some other way?

share|improve this question

5 Answers 5

up vote 11 down vote accepted

It's been a while since I've worked in LISP, but as I recall, the basic non-atomic structure is a list. Everything else is based on that. So you could have a list of atoms where each atom is a node followed by a list of edges that connect the node to other nodes. I'm sure there's other ways to do it too.

Maybe something like this:

  (a (b c)),
  (b (a c)),
  (c (a b d)),
  (d (c))

could give a graph like this:

^         ^
|         |

If you want to get fancy, you could add weights to it as well:

  (a (b 1.0 c 2.0)),
  (b (a 1.0 c 1.0)),
  (c (a 1.3 b 7.2 d 10.5)),
  (d (c -10.5))

You might also be interested in this: CL-Graph (found by google-searching the phrase "lisp graph structure" - if the link doesn't work, replace the "%24" with "$")

share|improve this answer

Functional languages deal with data structures the same way that non-functional languages do: by separating interface from implementation, creating abstract data types.

You can create abstract data types in Lisp. For instance, for a graph, you might want a couple of functions:

(define (get-vertices graph) ;; gets all the vertices from a graph

(define (get-edges graph) ;; gets all the edges from a graph

(define (get-weight vertex-from vertex-to) ;; get the weight of a specific vertex

Once you've created that interface to a graph, you can implement the actual data structures in many different ways, possibly optimizing such factors as programmer efficiency, flexibility, and computational efficiency.

The key is to make sure that the code that uses graphs only uses the graph interface, and doesn't access the underlying implementation. This will keep the client code simpler as its uncoupled from the actual implementation.

share|improve this answer

Well it would depend on whether your graph is directed/undirected, weighted/unweighted but one way to represent a directed, weighted graph (which would be the most general) is with a map of maps (in Clojure)

 :a {:b 3 :c 4} 
 :b {:a 1} 
 :c {}

would represent a map with nodes :a :b and :c. :a points to :b with a weight of 3 and :c with :a weight of 4. :b points to :a with a weight of 1. :c doesn't point to anything.

share|improve this answer

In Haskell the list is the basic data structure and if you want a more advanced data struktures you often use recursive struktures like a tree is either null or a node and two trees

data Tree a = Null | Node Tree a Tree  
share|improve this answer

In Common Lisp, if I needed to represent a tree, I'd use either a list (if it was for just a quick hack) or define a tree class (or struct, but classes interact well with generic functions, so why not).

(defclass tree ()
  ((node :accessor node :initarg :node)
   (children :accessor children :initarg :children)))

If I need literal trees in the code, I'd probably also define a make-tree function that takes a list representation of the tree I want and turn it into a tree of tree-objects.

share|improve this answer

Your Answer


