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 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::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::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::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::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 []
// = []
List::equalsWith : (a -> b -> Bool) -> List a -> List b -> Bool
¶
Given an equality relation and two lists, List::equalsWith
returns True
if, and only if, all the pairwise matched elements of the lists satisfy the given relation, and the two lists are of equal lengths.
This can be used to used to compare structural equality of lists.
Examples¶
val a = List::equalsWith (\(m : Int) -> \n -> m = n) [1] [1]
// = True
val b = List::equalsWith (\(m : Int) -> \n -> m = n) [1] [2]
// = False
val c = List::equalsWith (\(m : Int) -> \n -> m = n) [1] []
// = False
List::Int::equals : List Int -> List Int -> Bool
¶
Structural equality relation for List Int
.
Examples¶
val a = List::Int::equals [1] [1]
// = True
val b = List::Int::equals [1] [2]
// = False
val c = List::Int::equals [1] []
// = False
List::Float::equals : List Float -> List Float -> Bool
¶
Structural equality relation for List Float
.
Examples¶
val a = List::Float::equals [1.0] [1.0]
// = True
val b = List::Float::equals [1.0] [2.0]
// = False
val c = List::Float::equals [1.0] []
// = False
List::String::equals : List String -> List String -> Bool
¶
Structural equality relation for List String
.
Examples¶
val a = List::String::equals ["foo"] ["foo"]
// = True
val b = List::String::equals ["foo"] ["bar"]
// = False
val c = List::String::equals ["foo"] []
// = False
List::DateTime::equals : List DateTime -> List DateTime -> Bool
¶
Structural equality relation for List DateTime
.
Examples¶
val a = List::DateTime::equals [#2018-02-08T10:00:00Z#] [#2018-02-08T10:00:00Z#]
// = True
val b = List::DateTime::equals [#2018-02-08T10:00:00Z#] [#2017-12-24T12:00:00Z#]
// = False
val c = List::DateTime::equals [#2018-02-08T10:00:00Z#] []
// = False