Functional Doubly Linked Lists

It’s often been said that functional programming just isn’t cut out for certain tasks. File IO? Please… Databases? Forget about it!

I’ve always figured that the humble Doubly Linked list was on this list. After all, how do we implement these in C? An implementation would probably look something like this:

struct _DList { struct DList * next; struct DList * prev; void * element; } DList;

In this case, the element pointed to by prev and next have pointers to this element, if they aren’t NULL. The Doubly Linked list isn’t exactly a complicated structure, this is basically the way to do it. So, how would we do this in Haskell?

In the past, I’ve thought there were three answers to this question:

1) Use C pointers. This would involve use of unsafePerformIO, and you’d be a monster.

2) Use a singly linked list, and pretend it’s doubly linked. This would involve a “prev” function that just walks from the beginning of the list to the element before the current one. You’d be an even bigger monster than the guy who did option 1.

3) Don’t use a doubly linked list. To me, this is actually reasonable. In a world where arrays are basically always better, the only reason to use a list is because they’re very easy to deal with. If you need the level of complexity of a doubly linked list, you’re probably just better off with a different data structure.

But recently, I thought of a way to implement a doubly linked list in Haskell without being a bad person.

Preserved Here For Posterity

The implementation is actually quite simple. Here’s our type:

data DoublyLinkedList a = DList [a] [a] | Nil

Obviously, we have our Nil type for the empty list. We also have DList, which has two lists. Why two? On the left, we have the previous elements. This starts empty. On the right, we have our next elements. As we walk the list, we pop elements from the head of the right list to the head of the left list. The head of the right list is our current element. Let’s see some functions:

get :: DoublyLinkedList a -> a get (DList _ (x:xs)) = x

This function returns the “current” element; the element at the current position in the list.

next :: DoublyLinkedList a -> DoublyLinkedList a next (DList _ []) = undefined next (DList prev (c:next)) = DList (c:prev) next prev :: DoublyLinkedList a -> DoublyLinkedList a prev (DList [] _) = undefined prev (DList (c:prev) next) = DList prev (c:next)

These two functions move the cursor forward or backward. As you can see, when next is called, the current element is popped from the next list, and pushed onto the previous list. The opposite happens when prev is called. I’ve left the edge cases undefined, but a real implementation should do something sane here. (return a Maybe, throw an exception, etc…)

insert :: DoublyLinkedList a -> a -> DoublyLinkedList a insert Nil e = DList [] [e] insert (DList prev next) e = DList prev (e:next)

Elements are inserted in front of the current element.

makeDouble :: [a] -> DoublyLinkedList a makeDouble [] = Nil makeDouble l = DList [] l

…and it is trivial to convert a singly linked list into a doubly linked list. We can even add a pretty show instance!

instance (Show a) => Show (DoublyLinkedList a) where show Nil = "Nil" show (DList prev (c:next)) = (show $ reverse prev) ++ "*[" ++ (show c) ++ "]*" ++ show next

Obviously, we could go crazy and make a Monad instance and other things, but you get the idea. The final solution was very simple. One could even say simpler than the C version as you don’t have to worry about updating the next and prev pointers when adding elements. Sure, it took a bit of thought, but like many things in Haskell, the result was simple and elegant.

One response to “Functional Doubly Linked Lists”

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: