Are functionally implemented linked lists actually used?

Question

It seems functional lists of the type:

Node of 'a * 'a node | Nil

have worse run times in most cases O(n) than their object oriented counterparts O(1), an example is enqueue - the functional implementation would have to non tail-recursively loop to the end while the object-oriented implementation could just make last.next = new and last = new. Is there a clean functional implementation of these lists that doesn't have this issue? If not are functional lists actually used at all and why?

Thanks

Answer 1

The singly linked list is the most important and primary data structure in functional languages. Both haskell, Common Lisp, Scheme, etc.. relies heavily on it.

Functional linked lists is far worse than you think- Adding to tail would mean copying every segment of the argument linked list and make the last created segment point to a new node with the new value since you cannot mutate the argument.

In Lazy languages this is done, but since it's lazy nothing is really created until you use it. It doesn't blow the stack and the optimization is crazy intelligent. (eg. Haskell)

In eager languages, like Scheme, you usually either build a list from end to beginning and at the end you reverse the list. Making it will then be O(n). Usually you can linear reverse a list if you have made all the nodes in it to save memory and it would work as if you didn't. map and fold-right can even connect forward as long as it works as intended. In Common LISP you can do the same in code and say it's functional as long as it computes the same value from the same arguments and never mutate the actual arguments themselves. Some implementations, like Racket, rely on immutable lists and thus can store information about them that aids speed. eg. list? needs to inspect the very last cons to check if it's () to be #t, but it seems memoize the result. This couldn't be done if the lists were mutable.

Being able to mutate something has nothing to do with OO. You can do it in Scheme and Common Lisp since they are multi paradigm languages and not purely functional.

Here is a queue implemented in Scheme with singly linked list (cons) by mutating the tail when adding (not functional):

#!r6rs
(import (rnrs)
        (rnrs mutable-pairs))

(define (queue-make)
  (let ((q (list 'head)))
    (set-car! q q)
    q))

(define (queue-empty? q)
  (and (pair? q)
       (null? (cdr q))))

(define (queue-push! q v)
  (let ((tmp (car q))
        (vc (cons v '())))
    (set-cdr! tmp vc)
    (set-car! q vc)))

(define (queue-pop! q)
  (if (null? (cdr q))
      (error 'queue-empty "Empty queue")  ; empty
      (let ((v (cadr q)))
        (set-cdr! q (cddr q))        
        v)))

(define q (queue-make))
(queue-push! q 1)
(queue-push! q 2)
(queue-push! q 3)
(queue-pop! q) ; ==> 1
(queue-pop! q) ; ==> 2
(queue-pop! q) ; ==> 3
(queue-pop! q) ; ==> throws  queue-empty: Empty queue

Answer 2

have worse run times in most cases O(n) than their object oriented counterparts O(1)

This is nothing to do with being object-oriented. Any linked structure will take O(N) for appending at the tail unless a pointer is maintained. And yes, lots of languages do actually use linked lists.

Update: Also, pointers have nothing to do with object-orientation.

Answer 3

If not are functional lists actually used at all and why?

Given that you're interested in data structures that are frequently modified, about the only use case I can see for persistent (linked) lists are as a basis for implementing a stack data structure.

• The push operation adds a new value at the front of the list (i.e. it creates one new list element and reuses the remainder of the previously existing list).
• The peek or top operation returns the first value in the list.
• The pop operation returns the list starting after the first element.

Lists as defined by you work well as a stack data structure because all modifications happen in the ideal place, you never have to rebuild any part of the existing list when a new element is added or removed. And stacks typically don't require iteration over all of its elements / traversal in the order in which they were added (back to front).

Apart from that, AFAIK lists are a less than optimal data structure, because when you want to edit it in any place other than at its front, you have to rebuild all elements up to the place where the change occurs. Worst case is appending an element at the "end" of the list. That's why tree-based structures are a better fit as a basis for persistent ("immutable") data structures: they can reuse more existing nodes, while usually, only the nodes must be replaced that lie along the path to the node where some change should occur. ("change" = deriving a new, different data structure from the unchanged original.)

If you don't need to modify your list often, and you mostly read its elements in-sequence (not in random order), it might just be enough, too. One advantage is that it has very little memory overhead compared to more complicated structures, such as trees.

Node of 'a * 'a node | Nil

[…] Is there a clean functional implementation of these lists that doesn't have this issue?

Obviously not, if your definition of "list" is the one you gave. But again (and this is perhaps a somewhat naïve suggestion), you could implement a "list" on the basis of some kind of self-balancing binary tree:

• Iterating over all elements in that "list" would mean traversing the tree in the order left child first, parent node, right child first.
• Appending at the end of the list would mean a change at the right-most leaf node; you would have to rebuild only the path from the root node to that right-most leaf node, everything else could be reused.
• The less deep the tree is, the less elements you are likely to have to change when you're modifying the tree. Thus my suggestion of a self-balancing binary tree.

But again, I'm not an expert, and my suggestion might be naïve. For an in-depth treatment of functional data structures, check out the resources referenced below.

Further reading:

• Chris Okasaki (1996), Purely Functional Data Structures
• The thesis (available online as a PDF) on which it's based.
• Question on Computer Science SE, "What's new in purely functional data structures since Okasaki?".