Lecture 8-1

COMP105 Lectures 2020-10-27

List Recursion

Lists have a head and a tail. We use these command and pattern matching to recurse lists. Generally list recursions use the empty list [] as part of the base case.

Consuming Lists

sum' []		= 0 
sum' (x:xs)	= x + sum' xs

• The base case is the empty list.
• The recursive rule breaks the list into its head and tail.

length' []		= 0
length' (_:xs)	= 1 + length' xs

• This time the head of the list isn’t used.

Building Lists

We can also build lists using recursion.

down_from 0	= []
down_from x	= x : down_from (x-1)

This will produce a list counting down from the number provided until zero is reached.

Transforming Lists

If you want to consume and build a list in one go it is called transforming a list.

square_list []		= []
square_list (x:xs)	= x * x : square_list xs

This list will square each value and add it recursively onto the list.

The defining feature of transforming lists is that the base case has an input of [] which is equal to the output of [].

Exercises

1.  product' []		= 1
    product' (x:xs)	= x * product' xs
   

2.  upToTen 10	= 10
    upToTen x 	= x : upToTen (x + 1)
   

3.  halveList [] 		= []
    halveList (x:xs) 	= (x / 2) : halveList (xs)