Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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
add comment

5 Answers

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:

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" - if the link doesn't work, replace the "%24" with "$")

share|improve this answer
add comment

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
add comment

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
add comment

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
add comment

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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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