Menu
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).
933
A doubly-linked list is a linked data structure that consists of a set of sequentially linked records called nodes. Each node contains two fields, called links, that are references to the previous and to the next node in the sequence of nodes.
Doubly Linked List is a variation of Linked list in which navigation is possible in both ways, either forward and backward easily as compared to Single Linked List. Following are the important terms to understand the concept of doubly linked list. Link − Each link of a linked list can store a data called an element.
A music player which has next and previous buttons. The Browser cache which allows you to move front and back between pages is also a good example of doubly linked list. Most Recently Used is also an example of DLL. A deck of cards in a game is a classic example of application of DLL.
Uses Of DLL: It is used in the navigation systems where front and back navigation is required. It is used by the browser to implement backward and forward navigation of visited web pages that is a back and forward button. It is also used to represent a classic game deck of cards.
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.
105
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.
42
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
