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:

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

2. 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 Floats.

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 Nones).

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 []
//    = []