`List`

A list in CSL is represented by the type `List a`

, where `a`

is the type of the values in the list.
For example, a list of integers, of type `Int`

, has the type `List Int`

.

A list is either empty or it consists of an element followed by the rest of the list.
The empty list is called `Nil`

, and the list that contains one element `x`

followed by a list `l`

is called `Cons x l`

.
The type of lists is thus:

```
type List a
| Nil
| Cons a (List a)
```

Some examples of lists:

```
val oneTwoThree = Cons 1 (Cons 2 (Cons 3 Nil))
val abc = Cons "a" (Cons "b" (Cons "c" Nil))
```

There is support for a syntactic shorthand form for writing lists making the following equivalent to the above:

```
val oneTwoThree = [1, 2, 3]
val abc = ["a", "b", "c"]
```

## Folding lists with `foldl`

and `foldr`

Lists can be *folded* to construct a new value based on the items in the list: Given a function that can combine an accumulating value with the next value in the list and yield a new accumulating value, we may reduce the entire list.
An example of this is the sum function.
The accumulating value is the sum and the action performed on each element is simply adding it to the running total and returning it.
Folding with this function over the entire list then corresponds to adding together all elements.
It is written as follows:

```
val sum = \list -> foldl (\(acc:Int) -> \x -> acc + x) 0 list
```

The product of all the integers in a list is written like:

```
val product = \list -> foldl (\(acc : Int) -> \x -> acc * x) 1 list
```

The functions `foldl`

and its sibling `foldr`

both fold over a list (from the left and right, respectively), combining the elements of the list with a supplied function.
Their types are

```
foldl : (b -> a -> b) -> b -> List a -> b
foldr : (a -> b -> b) -> b -> List a -> b
```

The first argument to `foldl`

is a function that combines the accumulator value of type `b`

with an element of the list of type `a`

, producing a new accumulator value of type `b`

.
The second argument is the starting value for the accumulator – `0`

in the example with `sum`

; `1`

in the `prod`

example.
The third argument is the list of `a`

-values to be folded, and the return value is the final `b`

value.
For the right-handed sibling `foldr`

, the arguments are the same except that the accumulator function takes its argument in the reverse order.

One can think of `foldl`

and `foldr`

as functions that replace the list constructors `Cons`

and `Nil`

with, respectively, calls to the supplied accumulator function `f`

and the supplied base value (`0`

or `1`

in the examples above.)
If we define the helper function

```
val plus = \(x : Int) -> \(y : Int) -> x + y
```

then folding this over a list as the `sum`

function replaces all `Cons`

constructors with calls to `sum`

and the `Nil`

constructor with `0`

:

```
val suml = \list -> foldl plus 0 list
val sumr = \list -> foldr plus 0 list
val ns = Cons 1 (Cons 2 (Cons 3 Nil)) // or [1, 2, 3]
val sixl = suml ns
// {with foldl} = plus (plus (plus 0 1) 2) 3 = 6
val sixr = sumr ns
// {with foldr} = plus 1 (plus 2 (plus 3 0)) = 6
```

The order of the elements are not changed, but the direction that the `plus`

function is applied changes between folding with `foldl`

and `foldr`

.

## Choosing between `foldr`

and `foldl`

When we need to solve a problem with a fold, then we need to decide whether to use `foldr`

or `foldl`

.
The reason that we do not always use `foldr`

is that `foldl`

often has better performance than `foldr`

.
In most cases we can use the following rule of thumb to choose between them:

If the structure of the result of the fold is independent of the structure of the input list, then use

`foldl`

.If the structure of the result of the fold depends on the structure of the input list, then use

`foldr`

.

The first situation is typical for cases where the result is an aggregated value.
The following example calculates the length and average of a list of `Float`

s.

```
val lengthAndAverage = foldl
(\(l, avg) -> \n -> (l+1, ((Int::toFloat l) * avg + n) / (Int::toFloat (l+1))))
(0, 0.0)
val a = lengthAndAverage [60.0, 30.0, 120.0]
// = (3, 70.0)
```

Here the result is independent of the structure of the input list, in the sense that the result type is always `Tuple Float Float`

, and the result will be the same no matter how the input list is ordered.
Therefore `foldl`

is a safe way to get good performance in this example.

The second situation is typical for cases where the output is also a list. The following example filters away small integers from a list.

```
val removeSmallNumbers =
foldr (\n -> \acc -> if (n >= 10) Cons n acc else acc) Nil
val a = removeSmallNumbers [12, 3, 21, 4]
// = [12, 21]
```

If we had used `foldl`

instead of `foldr`

here, then the order of the result would have been reversed.

`List::head : List a -> Maybe a`

Returns the head (i.e. the first element) of the list, if any.
Otherwise returns `None`

.

### Examples

```
val a = List::head [0]
// = Some 0
val b = List::head []
// = None
```

`List::headOrDefault : a -> List a -> a`

Returns the head (i.e. the first element) of a list, if any. Otherwise returns the given default value.

### Examples

```
val a = List::headOrDefault 42 [0]
// = 0
val b = List::headOrDefault 42 []
// = 42
```

`List::tail : List a -> Maybe (List a)`

Returns the tail of a list (i.e. what remains when stripping away the first element), if any.
Otherwise, if the list is empty, return `None`

.

### Examples

```
val a = List::tail [0, 1]
// = Some [1]
val b = List::tail [0]
// = Some []
val c = List::tail []
// = None
```

`List::minimum : (a -> a -> Ordering) -> List a -> Maybe a`

Returns the minimum of a list, if any. Uses the ordering function provided as the first argument to compare elements.

### Examples

```
val a = List::minimum compareInt []
// = None
val b = List::minimum compareInt [1, 6, 0, 234, 2]
// = Some 0
```

`List::maximum : (a -> a -> Ordering) -> List a -> Maybe a`

Returns the maximum of a list, if any. Uses the ordering function provided as the first argument to compare elements.

### Examples

```
val a = List::maximum compareInt []
// = None
val b = List::maximum compareInt [1, 6, 0, 234, 2]
// = Some 234
```

`List::contains : a -> List a -> Bool`

Returns `True`

if the list contains the given value.
Otherwise it returns `False`

.

### Examples

```
val myList = [1, 2]
val oneVal = List::contains 1 myList
// = True
val threeVal = List::contains 3 myList
// = False
```

`List::sort : (a -> a -> Ordering) -> List a -> List a`

We can sort a list of elements if we know how to impose an order on them.
The function `List::sort`

accepts a function that orders elements and a list of elements and produces a sorted list:

### Examples

```
val sortAscending = List::sort compareInt
val sortDescending = List::sort (flip compareInt)
val xs = [2, 3, 1]
val xsAscending = sortAscending xs
// = [1, 2, 3]
val xsDescending = sortDescending xs
// = [3, 2, 1]
```

`List::isSorted : (a -> a -> Ordering) -> List a -> Bool`

The function `List::isSorted`

accepts a function that orders elements and a list of elements and produces True if the list is ordered.
Otherwise returns False.

### Examples

```
val a = List::isSorted compareInt []
// True
val b = List::isSorted compareInt [1, 3, 3, 6]
// True
val c = List::isSorted compareInt [1, 6, 3]
// False
```

`List::length : List a -> Int`

The `List::length`

function returns the number of elements in a list.

### Examples

```
val a = List::length ["a", "b", "c"]
// = 3
val b = List::length []
// = 0
```

`List::isEmpty : List a -> Boolean`

Returns `True`

if the list is empty. `False`

otherwise.

### Examples

```
val a = List::isEmpty ["a", "b", "c"]
// = False
val b = List::isEmpty [ [] ]
// = False
val c = List::isEmpty []
// = True
```

`List::map : (a -> b) -> List a -> List b`

To transform all elements in a list and produce a list with the transformed elements, we use the function `List::map`

to apply some function `f`

on all elements in a list.

`List::map`

takes a function that can convert elements of type `a`

into elements of type `b`

, a list of `a`

elements, and it produces a list of `b`

elements by applying the supplied function to each element in the list.

### Examples

```
// type of addOne is Int -> Int
val addOne = \x -> x + 1
// type of incrementList is List Int -> List Int
val incrementList = List::map addOne
val ms = [1, 2, 3]
val msInc = incrementList ms
// = [addOne 1, addOne 2, addOne 3]
// = [2, 3, 4]
```

`List::mapMaybe : (a -> Maybe b) -> List a -> List b`

The `List::mapMaybe`

function is a version of `List::map`

which takes a function into `Maybe b`

(also known as a *partial function*), and throws away the undefined values (i.e. the `None`

s).

### Examples

```
val a = List::mapMaybe (\n -> if (n > 100) (Some n) else None)
[140, 40, 103]
// = [140, 103]
val b = List::mapMaybe id [Some "a", None, Some "b"]
// = ["a", "b"]
```

`List::filter : (a -> Bool) -> List a -> List a`

The `List::filter`

function takes a predicate and a list, and returns a list consisting of the elements of the input list which satisfies the predicate.

### Examples

```
val a = List::filter (\n -> n < 10) [10, 1, 2, 100]
// = [1, 2]
```

`List::zipWith : (a -> b -> c) -> List a -> List b -> List c`

The `List::zipWith`

function generalises `List::map`

to binary functions.
It takes a binary function and two lists as arguments, and returns a list resulting from applying the function pairwise on the elements of the lists.
The resulting list always has the same length as the shortest input list, i.e., the last elements of the longest list are ignored.

### Examples

```
val a = List::zipWith (\(m: Int) -> \(n : Int) -> m + n)
[4, 5]
[10, 20]
// = [14, 25]
val b = List::zipWith (\(m : Int) -> \(n : Int) -> m + n)
[4, 5]
[10]
// = [14]
val c = List::zipWith (\(m : Int) -> \(n : Int) -> m + n)
[4]
[10, 20]
// = [14]
```

`List::zip : List a -> List b -> List (Tuple a b)`

The `List::zip`

function takes two lists as arguments, and returns a list of the elements pairwise together.
The resulting list always has the same length as the shortest input list.

### Examples

```
val a = List::zip [4, 5] [10, 20]
// = [(4, 10), (5, 20)]
val b = List::zip [4, 5] [10]
// = [(4, 10)]
val c = List::zip [4] [10, 20]
// = [(4, 10)]
```

`List::any : (a -> Bool) -> List a -> Bool`

Given a predicate and a list, `List::any`

returns `True`

if, and only if, there exists an element in the list which satisfies the predicate.

### Examples

```
val a = List::any (\n -> n > 4) [2, 10]
// = True
val b = List::any (\n -> n > 4) [2, 0]
// = False
val c = List::any (\n -> n > 4) []
// = False
```

`List::all : (a -> Bool) -> List a -> Bool`

Given a predicate and a list, `List::all`

returns `True`

if, and only if, all elements in the list satisfy the predicate.

### Examples

```
val a = List::all (\n -> n > 4) [5, 6]
// = True
val b = List::all (\n -> n > 4) [5, 3]
// = False
val c = List::all (\n -> n > 4) []
// = True
```

`List::first : (a -> Bool) -> List a -> Maybe a`

Returns the first element in the list which satisfies the predicate, if any.

### Examples

```
val a = List::first (\n -> n > 4) [3, 42, 100]
// = Some 42
val b = List::first (\n -> n > 4) [3, 2, 1]
// = None
```

`List::last : (a -> Bool) -> List a -> Maybe a`

Returns the last element in the list which satisfies the predicate, if any.

### Examples

```
val a = List::last (\n -> n > 4) [3, 42, 100]
// = Some 100
val b = List::last (\n -> n > 4) [3, 2, 1]
// = None
```

`List::append : List a -> List a -> List a`

Appends two lists.

### Examples

```
val a = List::append ["a"] ["b"]
// = ["a", "b"]
val b = List::append [] a
// = a
val c = List::append a []
// = a
```

`List::concat : List (List a) -> List a`

Flattens a list of lists into one list, by appending them to each other.

### Examples

```
val a = List::concat [ [1, 2], [3], [4] ]
// = [1, 2, 3, 4]
```

`List::concatMap : (a -> List b) -> List a -> List b`

Maps a list-returning function over a list and concatenates the results.

### Examples

```
val a = List::concatMap (\n -> [n, n+1, n+2]) [1, 2, 3]
// = [1, 2, 3, 2, 3, 4, 3, 4, 5]
```

`List::reverse : List a -> List a`

Reverses a list.

### Examples

```
val a = List::reverse [1, 2, 3]
// = [3, 2, 1]
```

`List::take : Int -> List a -> List a`

Given an integer, m, and a list, `List::take`

returns the first m elements of the list.
If the list has fewer than m elements, the whole list is returned.

### Examples

```
val a = List::take 2 ["a", "b", "c"]
// = ["a", b"]
val b = List::take 2 ["a"]
// = ["a"]
```

`List::takeWhile : (a -> Bool) -> List a -> List a`

Given a predicate and a list, ‘takeWhile’ takes the elements of the list as long as the predicate holds.

### Examples

```
val a = List::takeWhile (const True) ["a", "b", "c"]
// = ["a", b", "c"]
val b = List::takeWhile (\x -> x > 5) [6, 9, 5, 4, 8]
// = [6, 9]
```

`List::drop : Int -> List a -> List a`

Given an integer, m, and a list, `List::drop`

throws away the first m elements of the list, and returns the rest.
If the list has fewer than m elements, the empty list is returned.

### Examples

```
val a = List::drop 2 ["a", "b", "c"]
// = ["c"]
val b = List::drop 1 ["a"]
// = []
val c = List::drop 1 []
// = []
```