Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

like image 933
Claudiu Avatar asked Dec 04 '09 00:12

Claudiu


People also ask

What is doubly linked list in programming?

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.

What is doubly linked list in DSA?

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.

What is doubly linked list explain with real life examples?

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.

Where is doubly linked list used in real life?

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.


2 Answers

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.

like image 105
Norman Ramsey Avatar answered Oct 11 '22 13:10

Norman Ramsey


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.

like image 42
Edward Kmett Avatar answered Oct 11 '22 14:10

Edward Kmett