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])

NonEmptyList::final : NonEmptyList a -> a

Returns the final (i.e. last) element of a non-empty list.

Examples

val a = NonEmptyList::final (NonEmpty 1 [2, 3])
//    = 3

NonEmptyList::reverse : NonEmptyList a -> NonEmptyList a

Reverses a non-empty list.

Examples

val a = NonEmptyList::reverse (NonEmpty 1 [2, 3])
//    = NonEmpty 3 [2, 1]