4.12.3.1 List processing.md

Functional Lists

Head and Tail

Be familiar with representing a list as a concatenation of a head and a tail.

What is a head and what is a tail?

The head of the list is defined to be the first element of the list. The tail of the list is defined to be a list excluding the head, the type of tail is therefore a list of elements.

Example

Original List	Head	Tail
x:xs	x	xs
[1,2,3,4,5]	1	[2,3,4,5]

Head and tail concatination

A list can be represented as a head and tail concatination. For example the list [1,2,3,4,5] could be represented as 1:[2,3,4,5].

List operations

Know that a list can be empty.

[] is the empty list.

Describe and apply the following operations:

• return head of list
• return tail of list
• test for empty list
• return length of list
• construct an empty list
• prepend an item to a list
• append an item to a list.

Operation	Description	Example
Return head of list		Head Example
Return tail of list		Tail Example
Test for empty list		Empty Example
Return length of list		Length Example
Prepend an item to a list		Prepend Example
Append an item to a list		Append Example

Return head of list

headOfList (x:xs) = 
	x

Return tail of list

tailOfList (x:xs) = 
	xs

Test for empty list

checkEmptyList l = 
	null l

Length of list

lengthOfList l = 
	length l

Prepend to list

prependToList i l = 
	i:l

Append to list

appendToList i l =
	l ++ [i]	

Additional Information

For example, in Haskell the list [4, 3, 5] can be written in the form head:tail where head is the first item in the list and tail is the remainder of the list. In the example, we have 4:[3, 5]. We call 4 the head of the list and [3, 5] the tail.