Doubly Linked List in a Purely Functional Programming Language

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

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.

There are a number of approaches.

If you don't want to mutate the doubly-linked list once you have constructed it you can just 'tie the knot' by relying on laziness.

http://www.haskell.org/haskellwiki/Tying_the_Knot

If you want a mutable doubly-linked list you need to fake references somehow -- or use real ones -- a la the trick proposed by Oleg Kiseylov and implemented here:

http://hackage.haskell.org/packages/archive/liboleg/2009.9.1/doc/html/Data-FDList.html

Interestingly, note that the former relies fundamentally upon laziness to succeed. You ultimately need mutation or laziness to tie the knot.

I would reiterate musicfan's question: "what exactly do you need this for?" As Norman Ramsey notes: if you need multi-directional traversal, then zippers are easier; if you need fast splicing, finger trees work well.

But, just to see how it looks...

import Control.Arrow
import Data.List

data LNode a = LNode { here :: a, prev :: LList a, next :: LList a }
type LList a = Maybe (LNode a)

toList :: LList a -> [a]
toList = unfoldr $ fmap $ here &&& next

fromList :: [a] -> LList a
fromList l = head nodes where
    nodes = scanr ((.) Just . uncurry LNode) Nothing $ zip l $ Nothing : nodes

append :: LList a -> LList a -> LList a
append = join Nothing where
    join k (Just a) b = a' where
        a' = Just $ a { prev = k, next = join a' (next a) b }
    join k _ (Just b) = b' where
        b' = Just $ b { prev = k, next = join b' Nothing (next b) }
    join _ _ _ = Nothing