NonEmptyList¶
A non-empty list in CSL is represented by the type NonEmptyList a, where a is the type of the values in the list.
For example, a non-empty list of integers, of type Int, has the type NonEmptyList Int.
A non-empty list consists of an element followed by the rest of the list – which may itself be empty.
type NonEmptyList a
| NonEmpty a (List a)
Some examples of non-empty lists:
val oneTwoThree = NonEmpty 1 [2, 3]
val abc = NonEmpty "a" ["b", "c"]
Use in contracts¶
Non-empty lists are primarily useful when writing recursive contracts, helping to satisfy the guardnedness condition. In some cases, nesting recursive contracts can lead to issues when the base case for the inner recursion is not associated with an event.
The following abstract example illustrates the problem.
contract rec innerLoop =
\ Nil -> success
| Cons _ ys -> <*> Event then innerLoop ys
contract rec outerLoop =
\ Nil -> success
| Cons x xs -> innerLoop x then outerLoop xs
contract entrypoint unguardedExample = \(args: List (List String)) ->
outerLoop args
This code does not satisfy the guardnedness property; that is, not every recursive call is prefixed with an event.
For instance, if we were to instantiate the unguardedExample with [[], [1, 2]], following the structure of the contracts leads us to a recursive call to outerLoop that is indeed unguarded, since the innerLoop [] call immediately returns with success.
CSL detects this as a problem, and will not accept the above code.
However, if we already know that all inner lists are non-empty, we can use NonEmptyList for the inner list type, resulting in the following guard-safe code.
contract innerLoop = \NonEmpty _ rest -> let
contract rec loop =
\ Nil -> success
| Cons _ xs -> <*> Event then loop xs
in <*> Event then loop rest
contract rec outerLoop =
\ Nil -> success
| Cons x xs -> innerLoop x then outerLoop xs
contract entrypoint example = \(args: List (NonEmptyList Int)) ->
outerLoop args
Variants of this technique have proven useful in building prototypes of the financial contracts library.
NonEmptyList::toList : NonEmptyList a -> List a¶
Turns a non-empty list into an ordinary list.
Examples¶
val a = NonEmptyList::toList (NonEmpty 1 [])
// = [1]
val b = NonEmptyList::toList (NonEmpty 1 [2, 3])
// = [1, 2, 3]
NonEmptyList::fromList : List a -> Maybe (NonEmptyList a)¶
Converts a list a non-empty list, if the given list is not empty.
Otherwise it returns None.
Examples¶
val a = NonEmptyList::fromList []
// = None
val b = NonEmptyList::fromList [1, 2, 3]
// = Some (NonEmpty 1 [2, 3])
NonEmptyList::singleton : a -> NonEmptyList a¶
Creates a non-empty list with one element.
Examples¶
val a = NonEmptyList::singleton 1
// = NonEmpty 1 []
val b = NonEmptyList::singleton "a"
// = NonEmpty "a" []
NonEmptyList::head : NonEmptyList a -> a¶
Returns the head (i.e. the first element) of the non-empty list.
Examples¶
val a = NonEmptyList::head (NonEmpty 0 [])
// = 0
val b = NonEmptyList::head (NonEmpty 1 [2, 3])
// = 1
NonEmptyList::tail : NonEmptyList a -> List a¶
Returns the tail of a non-empty list (i.e. what remains when stripping away the first element).
Examples¶
val a = NonEmptyList::tail (NonEmpty 0 [])
// = []
val b = NonEmptyList::tail (NonEmpty 1 [2, 3])
// = [2, 3]
NonEmptyList::minimum : (a -> a -> Ordering) -> NonEmptyList a -> a¶
Returns the minimum of a non-empty list. Uses the ordering function provided as the first argument to compare elements.
Examples¶
val a = NonEmptyList::minimum compareInt (NonEmpty 0 [])
// = 0
val b = NonEmptyList::minimum compareInt (NonEmpty 1 [6, 0, 234, 2])
// = 0
NonEmptyList::maximum : (a -> a -> Ordering) -> NonEmptyList a -> a¶
Returns the maximum of a non-empty list. Uses the ordering function provided as the first argument to compare elements.
Examples¶
val a = NonEmptyList::maximum compareInt (NonEmpty 0 [])
// = 0
val b = NonEmptyList::maximum compareInt (NonEmpty 1 [6, 0, 234, 2])
// = 234
NonEmptyList::contains : a -> NonEmptyList a -> Bool¶
Returns True if the non-empty list contains the given value.
Otherwise it returns False.
Examples¶
val myList = NonEmpty 0 [1, 2]
val oneVal = NonEmptyList::contains 1 myList
// = True
val threeVal = NonEmptyList::contains 3 myList
// = False
NonEmptyList::sort : (a -> a -> Ordering) -> NonEmptyList a -> NonEmptyList a¶
We can sort a non-empty list of elements if we know how to impose an order on them.
The function NonEmptyList::sort accepts a function that orders elements and a list of elements and produces a sorted list:
Examples¶
val sortAscending = NonEmptyList::sort compareInt
val sortDescending = NonEmptyList::sort (flip compareInt)
val xs = NonEmpty 2 [3, 1]
val xsAscending = sortAscending xs
// = NonEmpty 1 [2, 3]
val xsDescending = sortDescending xs
// = NonEmpty 3 [2, 1]
NonEmptyList::isSorted : (a -> a -> Ordering) -> NonEmptyList a -> Bool¶
The function NonEmptyList::isSorted accepts a function that orders elements and a non-empty list of elements and produces True if the list is ordered.
Otherwise returns False.
Examples¶
val a = NonEmptyList::isSorted compareInt (NonEmpty 1 [3, 3, 6])
// True
val b = NonEmptyList::isSorted compareInt (NonEmpty 1 [6, 3])
// False
NonEmptyList::length : NonEmptyList a -> Int¶
The NonEmptyList::length function returns the number of elements in a non-empty list.
Examples¶
val a = NonEmptyList::length (NonEmpty "a" ["b", "c"])
// = 3
val b = NonEmptyList::length (NonEmpty 1 [])
// = 1
NonEmptyList::map : (a -> b) -> NonEmptyList a -> NonEmptyList b¶
To transform all elements in a non-empty list and produce a list with the transformed elements, we use the function NonEmptyList::map to apply some function f on all elements in a list.
NonEmptyList::map takes a function that can convert elements of type a into elements of type b, a non-empty list of a elements, and it produces a non-empty 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 NonEmptyList Int -> NonEmptyList Int
val incrementList = NonEmptyList::map addOne
val ms = NonEmpty 1 [2, 3]
val msInc = incrementList ms
// = NonEmpty addOne 1 [addOne 2, addOne 3]
// = NonEmpty 2 [3, 4]
NonEmptyList::zipWith : (a -> b -> c) -> NonEmptyList a -> NonEmptyList b -> NonEmptyList c¶
The NonEmptyList::zipWith function is like ‘NonEmptyList::map’ for two-argument functions.
It takes a binary function and two non-empty lists as arguments, and returns a non-empty 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 = NonEmptyList::zipWith (\(m: Int) -> \(n : Int) -> m + n)
(NonEmpty 4 [5])
(NonEmpty 10 [20])
// = NonEmpty 14 [25]
val b = NonEmptyList::zipWith (\(m : Int) -> \(n : Int) -> m + n)
(NonEmpty 4 [5])
(NonEmpty 10 [])
// = NonEmpty 14 []
val c = NonEmptyList::zipWith (\(m : Int) -> \(n : Int) -> m + n)
(NonEmpty 4 [])
(NonEmpty 10 [20])
// = NonEmpty 14 []
NonEmptyList::zip : NonEmptyList a -> NonEmptyList b -> NonEmptyList (Tuple a b)¶
The NonEmptyList::zip function takes two non-empty 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 = NonEmptyList::zip (NonEmpty 4 [5, 6]) (NonEmpty 10 [20, 30, 40])
// = NonEmpty (4, 10) [(5, 20), (6, 30)]
val b = NonEmptyList::zip (NonEmpty "a" ["b"]) (NonEmpty 0 [])
// = [("a", 0)]
NonEmptyList::any : (a -> Bool) -> NonEmptyList a -> Bool¶
Given a predicate and a non-empty list, NonEmptyList::any returns True if, and only if, there exists an element in the list which satisfies the predicate.
Examples¶
val a = NonEmptyList::any (\n -> n > 4) (NonEmpty 2 [10])
// = True
val b = NonEmptyList::any (\n -> n > 4) (NonEmpty 2 [0])
// = False
NonEmptyList::all : (a -> Bool) -> NonEmptyList a -> Bool¶
Given a predicate and a non-empty list, NonEmptyList::all returns True if, and only if, all elements in the list satisfy the predicate.
Examples¶
val a = NonEmptyList::all (\n -> n > 4) (NonEmpty 5 [6])
// = True
val b = NonEmptyList::all (\n -> n > 4) (NonEmpty 5 [3])
// = False
NonEmptyList::first : (a -> Bool) -> NonEmptyList a -> Maybe a¶
Returns the first element in the non-empty list which satisfies the predicate, if any.
Examples¶
val a = NonEmptyList::first (\n -> n > 4) (NonEmpty 3 [42, 100])
// = Some 42
val b = NonEmptyList::first (\n -> n > 4) (NonEmpty 3 [2, 1])
// = None
NonEmptyList::last : (a -> Bool) -> NonEmptyList a -> Maybe a¶
Returns the last element in the list which satisfies the predicate, if any.
Examples¶
val a = NonEmptyList::last (\n -> n > 4) (NonEmpty 3 [42, 100])
// = Some 100
val b = NonEmptyList::last (\n -> n > 4) (NonEmpty 3 [2, 1])
// = None
NonEmptyList::cons : a -> NonEmptyList a -> NonEmptyList a
Adds a new element at the start of a non-empty list.
Examples¶
val a = NonEmptyList::cons "a" (NonEmpty "b" [])
// = NonEmpty "a" ["b"]
NonEmptyList::append : NonEmptyList a -> NonEmptyList a -> NonEmptyList a¶
Appends two non-empty lists.
Examples¶
val a = NonEmptyList::append (NonEmpty "a" []) (NonEmpty "b" [])
// = NonEmpty "a" ["b"]
val b = NonEmptyList::append (NonEmpty "a" ["b", "c"]) (NonEmpty "d" [])
// = NonEmpty "a" ["b", "c", "d"]
NonEmptyList::concat : NonEmptyList (NonEmptyList a) -> NonEmptyList a¶
Flattens a non-empty list of non-empty lists into one non-empty list.
Examples¶
val a = NonEmptyList::concat (NonEmpty (NonEmpty 1 [2]) [NonEmpty 3 [], NonEmpty 4 []])
// = NonEmpty 1 [2, 3, 4]
NonEmptyList::concatMap : (a -> NonEmptyList b) -> NonEmptyList a -> NonEmptyList b¶
Maps a non-empty-list-returning function over a non-empty list and concatenates the results.
Examples¶
val a = NonEmptyList::concatMap (\n -> NonEmpty n [n+1, n+2]) (NonEmpty 1 [2, 3])
// = (NonEmpty 1 [2, 3, 2, 3, 4, 3, 4, 5])