Lists

A list is an abstract data type used for storing sequential items. They are an important concept in the Lisp family of programming languages and in functional programming languages in general. It's more common to use arrays, queues, and stacks for similar tasks in imperative languages.

The power of lists comes from their definition of head and tail:

The head is the first item in the list; the tail is all remaining items. The tail is itself a list, having its own head and tail:

This can be repeated for every tail:

Exploiting this property allows for operations to be defined on lists using recursion with minimal code.

Function Name* \(\hspace{15mm}\)	Provided Functionality
new	Creates an empty list.
append	Adds an item to the end of the list.
prepend	Adds an item to the beginning of the list.
head	Returns the item at the beginning of the list.
tail	Returns all items except the head. If the list only has 1 item, returns an empty list.
is_empty	Returns a bool indicating whether or not the list contains any items.

*Exact names are not required. In fact, some functionality may be provided by a given language directly via special syntax.

Note that Python has a built-in type that it calls list. It doesn't specifically define the required API to be used as a list ADT (abstract data type), but it does provide built-in syntax for array slicing. Since the tail function of the list ADT could be considered a specific case of slicing, the argument could be made that the Python list does fulfill the requirements of the list ADT API in a roundabout fashion.

This sample implements a linked list in an object-oriented style and includes the minimum functionality of a list ADT. The list class only has a reference to the head node, so the append operation has to walk through all the nodes to find the last node, making it an \(O(n)\) operation.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

class Node(object):
    def __init__(self, value, next_node=None):
        self.value = value
        self.next_node = next_node


class List(object):
    def __init__(self, head_node=None):
        self.head_node = head_node

    # this isn't strictly required, just allows the list to be printed
    def __str__(self):
        result = '['
        current_node = self.head_node
        is_first = True
        while current_node:
            if is_first:
                is_first = False
            else:
                result += ','
            result += str(current_node.value)
            current_node = current_node.next_node
        result += ']'
        return result

    def head(self):
        return self.head_node.value

    def tail(self):
        if self.is_empty():
            raise Exception('An empty list does not have a tail.')
        else:
            return List(self.head_node.next_node)

    # note that this is O(1)
    def prepend(self, value):
        new_head_node = Node(value, self.head_node)
        self.head_node = new_head_node

    # note that this is O(n)
    def append(self, value):
        new_node = Node(value)
        if self.is_empty():
            self.head_node = new_node
        else:
            last_node = self.head_node

            while last_node.next_node:
                last_node = last_node.next_node

            last_node.next_node = new_node

    def is_empty(self):
        return self.head_node is None

Try out append and prepend:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

animals = List()
animals.prepend('turtle')
print(animals)
animals.append('tiger')
print(animals)
animals.prepend('horse')
print(animals)
animals.append('bear')
print(animals)
animals.append('zebra')
print(animals)
animals.append('lion')
print(animals)

1
2
3
4
5
6

[turtle]
[turtle,tiger]
[horse,turtle,tiger]
[horse,turtle,tiger,bear]
[horse,turtle,tiger,bear,zebra]
[horse,turtle,tiger,bear,zebra,lion]

Now try out head and tail:

1
2

print(animals.head())
print(animals.tail())

1
2

horse
[turtle,tiger,bear,zebra,lion]

Using the Python implementation from above:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

def sum_list(the_list): if not the_list.is_empty(): return the_list.head() + sum_list(the_list.tail()) else: return 0 some_numbers = List() some_numbers.prepend(3) some_numbers.prepend(3) some_numbers.prepend(4) some_numbers.prepend(1) some_numbers.prepend(7) some_numbers.prepend(7) some_numbers.prepend(1) some_numbers.prepend(4) some_numbers.prepend(5) some_numbers.prepend(7) print(sum_list(some_numbers))

---

1

42

Using the Haskell built-in list:

1 2 3 4 5

sumList :: (Num a) => [a] -> a sumList [] = 0 sumList x = head x + sumList(tail x) main = print(sumList [7,5,4,1,7,7,1,4,3,3])

---

1

42

Generalizing upon the previous example, a right fold takes any arbitrary function and cumulatively applies it to the entire list.

Using the Python implementation from above:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

def special_add(x, y): return x + 2 * y # specifically, this is a right fold def fold_list(the_function, the_list): if the_list.tail().is_empty(): return the_list.head() else: return the_function(the_list.head(), fold_list(the_function, the_list.tail())) some_numbers = List() some_numbers.prepend(3) some_numbers.prepend(3) some_numbers.prepend(4) some_numbers.prepend(1) some_numbers.prepend(7) some_numbers.prepend(7) some_numbers.prepend(1) some_numbers.prepend(4) some_numbers.prepend(5) some_numbers.prepend(7) print(fold_list(special_add, some_numbers))

---

1

3257

Using the Haskell built-in list:

1 2 3 4 5 6 7 8 9

specialAdd :: (Num a) => a -> a -> a specialAdd x y = x + 2 * y -- specifically, this is a right fold foldList :: (a -> a -> a) -> [a] -> a foldList f [x] = x foldList f l = f (head l) (foldList f (tail l)) main = print(foldList specialAdd [7,5,4,1,7,7,1,4,3,3])

---

1

3257