# Data structures in functional programming

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?

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:

```a<-->b<-->c<-->d
^         ^
|         |
+---------+
```

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" )

• This is a bit late, but I think I should warn that "Everything else is based on [list]" is misleading. Common Lisp, Scheme and Clojure all have vectors, maps, strings, as well as structures/classes, not built on-top of lists; the code we write to create them generally is a list, e.g. (make-array '(2 2) :initial-element 0), but the data structure are not implemented using lists. Jun 15, 2016 at 22:36

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.

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.

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.

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
``````