Doubly Linked List in a Purely Functional Programming Language

Claudiu picture Claudiu · Dec 4, 2009 · Viewed 7.9k times · Source

How does one go about doing doubly linked lists in a pure functional language? That is, something like Haskell where you're not in a Monad so you don't have mutation. Is it possible? (Singly linked list is obviously pretty easy).

Answer

Norman Ramsey picture Norman Ramsey · Dec 4, 2009

In a pure functional language, a doubly-linked list is not that interesting. The idea of a doubly linked list is to be able to grab a node and go in either direction, or to be able to splice into the middle of a list. In a pure functionaly language you probably are better off with one of these two data structures:

  • A singly linked list with a pointer in the middle, from which you can go either left or right (a variant of Huet's "Zipper")

  • A finger tree, which is a mind-blowing data structure invented by Ralf Hinze and Ross Paterson.

I'm a big fan of the zipper; it's useful in a lot of situations.