11

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?

14

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

  • 4
    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. – coredump Jun 15 '16 at 22:36
3

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.

2

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.

1

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.

-2

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  

protected by gnat Jan 20 '17 at 17:10

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.