# CSL standard library source code¶

// CSL standard library
////////////////////////

/////////
// Errors
/////////

/// error : RuntimeError -> a
val error = prim__error

//////////////////////
// General combinators
//////////////////////

/// The identity function.  'id' simply returns the input.
///
/// Examples:
/// id 4 = 4
/// id "a" = "a"
///
val <a> id : a -> a = \x -> x

/// The constant function.  'const x' is a function which returns 'x', no matter what input it is given.
///
/// Examples:
/// const "a" "b" = "a"
///
val <a, b> const : a -> b -> a = \x -> \_ -> x

/// Flips the order of the arguments for a binary function.
///
/// Examples:
/// flip (\x -> \y -> x) "a" "b" = "b"
///
val <a, b, c> flip : (a -> b -> c) -> (b -> a -> c) = \f -> \y -> \x -> f x y

/// Composes two unary functions.
///
/// Examples:
/// comp (\x -> x + 5) (\y -> y * 12) 5 = (\x -> x + 5) 60 = 65
///
val <a, b, c> comp : (a -> b) -> (c -> a) -> c -> b = \f -> \g -> \x -> f (g x)

/// 'via f g x y' transforms 'x' and 'y' using unary function 'f' and applies the results to binary function 'g'.
///
/// Examples:
/// via fst compareInt (1, 3.15) (2, 0.75) = Less
/// via snd compareInt (1, 3.15) (2, 0.75) = Greater
///
val <a, b, c> via : (a -> b) -> (b -> b -> c) -> (a -> a -> c) =
\f -> \g -> \x -> \y -> g (f x) (f y)

/// Returns the smaller of the two last arguments, using the comparison function
/// provided as the first argument.
///
/// Examples:
/// min compareInt 8 9 = 8
/// min compareFloat 4.233 3.11 = 3.11
///
val <a> min : (a -> a -> Ordering) -> a -> a -> a =
\cmp -> \el1 -> \el2 -> if (cmp el1 el2 = Less) el1 else el2

/// Returns the larger of the two last arguments, using the comparison function
/// provided as the first argument.
///
/// Examples:
/// max compareInt 8 9 = 9
/// max compareFloat 4.233 3.11 = 4.233
///
val <a> max : (a -> a -> Ordering) -> a -> a -> a =
\cmp -> \el1 -> \el2 -> if (cmp el1 el2 = Greater) el1 else el2

//////////////////////
// Bool
//////////////////////

/// The 'not' function returns the opposite value of its input.
///
/// Examples:
/// not True = False
/// not False = True
///
val not : Bool -> Bool =
\ True -> False
| False -> True

//////////////////////
// Pair
//////////////////////

/// The first projection.
///
/// Examples:
/// fst (0, "a") = 0
///
val <a, b> fst : Tuple a b -> a = \(x, _) -> x

/// The second projection.
///
/// Examples:
/// snd (0, "a") = "a"
///
val <a, b> snd : Tuple a b -> b = \(_, y) -> y

//////////////////////
// Maybe
//////////////////////

/// The 'maybe' function takes a default value, a function, and a 'Maybe' value.
/// The default value is returned if the 'Maybe' value is 'None', otherwise the
/// result of applying the function to the value inside the 'Some' is returned.
///
/// Examples:
/// maybe 0 (\x -> x + 5) (Some 2) = 7
/// maybe 0 (\x -> x + 5) None = 0
///
val <a, b> maybe : b -> (a -> b) -> Maybe a -> b = \default -> \f ->
\ None   -> default
| Some x -> f x

/// The 'fromMaybe' function extracts the value from a 'Maybe', using the
/// default value for the 'None' case.
///
/// Examples:
/// fromMaybe 0 (Some 5) = 5
/// fromMaybe 0 None = 0
///
/// fromMaybe : a -> Maybe a -> a
val <a> fromMaybe : a -> Maybe a -> a = flip maybe id

module Maybe {
/// Lift any function to a function in 'Maybe'.
///
/// Examples:
/// map (\m -> m * 2) (Some 5) = Some 10
/// map (\m -> m * 2) None = None
///
val <a, b> map : (a -> b) -> Maybe a -> Maybe b = \f ->
\ None -> None
| Some x -> Some (f x)

/// Lift any binary function to a function in 'Maybe'.
///
/// Examples:
/// map2 (\x -> \y -> x + y) (Some 7) (Some 5) = Some 12
/// map2 (\x -> \y -> x + y) (Some 7) None = None
/// map2 (\x -> \y -> x + y) None (Some 5) = None
/// map2 (\x -> \y -> x + y) None None = None
///
val <a, b, c> map2 : (a -> b -> c) -> Maybe a -> Maybe b -> Maybe c = \f ->
\ None -> const None
| Some x ->
\ None -> None
| Some y -> Some (f x y)

/// Returns 'True' if the input is a 'Some', returns 'False' otherwise.
///
/// Examples:
/// isSome (Some 2) = True
/// isSome None = False
///
val <a> isSome : Maybe a -> Bool =
\ None -> False
| Some _ -> True

/// Returns 'True' if, and only if, the given 'Maybe' has a value, and this value satisfies
/// the given predicate.
///
/// Examples:
/// any (\n -> n > 4) (Some 5) = True
/// any (\n -> n > 4) (Some 2) = False
/// any (\n -> n > 4) None = False
///
val <a> any : (a -> Bool) -> Maybe a -> Bool = \pred -> maybe False pred

/// Returns 'True' if the given 'Maybe' has no value, or it has a value which
/// satisfies the given predicate.
///
/// Examples:
/// all (\x -> x >= 1) None = True
/// all (\x -> x >= 1) (Some 2) = True
/// all (\x -> x >= 1) (Some 0) = False
///
val <a> all : (a -> Bool) -> Maybe a -> Bool = \pred -> maybe True pred

/// Apply the function 'f' to the value 'a' if
/// the Maybe is 'Some a', 'None' otherwise.
/// 'f' must return a 'Maybe' type.
///
/// Examples:
/// bind (\x -> Some (x + 1)) None = None
/// bind (\x -> None) (Some 1) = None
/// bind (\x -> Some (x + 1)) (Some 1) = Some 2
///
val <a, b> bind : (a -> Maybe b) -> Maybe a -> Maybe b = \f ->
\ None -> None
| Some x -> f x

}

//////////////////////
// Ordering
//////////////////////

val compareInt : Int -> Int -> Ordering = \(x : Int) -> \y ->
if (x < y) Less else if (x = y) Equal else Greater

val compareFloat : Float -> Float -> Ordering = \(x : Float) -> \y ->
if (x < y) Less else if (x = y) Equal else Greater

val compareInstant : Instant -> Instant -> Ordering = \(x : Instant) -> \y ->
if (x < y) Less else if (x = y) Equal else Greater

val compareDate : Date -> Date -> Ordering = \(x: Date) -> \y ->
if (x < y) Less else if (x = y) Equal else Greater

val compareTime : Time -> Time -> Ordering = \(x: Time) -> \y ->
if (x < y) Less else if (x = y) Equal else Greater

module Ordering {

/// Ordering combinator 'twoStep' takes two functions comparing a given type.
/// When comparing concrete arguments, if the first comparison function
/// returns 'Equal', the second one is used to decide the comparison.
///
/// Examples:
/// twoStep
///   (\(x1, x2) -> \(y1, y2) -> compareInt x1 y1)
///   (\(x1, x2) -> \(y1, y2) -> compareFloat x2 y2)
///   (5, 99.9) (7, 15.599) = Less
/// type R { a : Float, b: Int}
/// twoStep
///   (\x -> \y -> compareFloat (x.a) (y.a))
///   (\x -> \y -> compareInt (x.b) (y.b))
///   R {a = 3.14, b = 6} R {a = 3.14, b = 2} = Greater
///
val <a> twoStep : (a -> a -> Ordering) -> (a -> a -> Ordering) -> a -> a -> Ordering =
\ord1 -> \ord2 -> \v1 -> \v2 -> let
val res1 = ord1 v1 v2
in if (res1 = Equal) (ord2 v1 v2) else res1

/// Ordering combinator 'lexicographic' builds an ordering function for a binary tuple.
/// It takes two arguments, comparison functions for the first and the second element of the tuple,
/// and returns a lexicographic comparison on the tuples.
///
/// Examples:
/// lexicographic compareInt compareFloat (5, 99.9) (7, 15.599) = Less
/// lexicographic compareInt compareFloat (5, 17.0) (5, 16.9) = Greater
///
val <a, b> lexicographic : (a -> a -> Ordering) -> (b -> b -> Ordering) -> Tuple a b -> Tuple a b -> Ordering =
\ord1 -> \ord2 ->
twoStep (\v1 -> \v2 -> ord1 (fst v1) (fst v2)) (\v1 -> \v2 -> ord2 (snd v1) (snd v2))

}

//////////////////////
// List
//////////////////////

val <a, b> foldl : (b -> a -> b) -> b -> List a -> b = prim__foldl

val <a, b> foldr : (a -> b -> b) -> b -> List a -> b = prim__foldr

module List {

/// Returns the head (i.e. the first element) of the list, if any.  Otherwise
/// returns 'None'.
///
/// Examples:
/// head  = Some 0
///
val <a> head : List a -> Maybe a =
\ Nil -> None
| Cons x _ -> Some x

/// Returns the head (i.e. the first element) of a list, if any.  Otherwise
/// returns the given default value.
///
/// Examples:
/// headOrDefault 42  = 0
/// headOrDefault 42 [] = 42
///
val <a> headOrDefault : a -> List a -> a = \default -> \xs -> fromMaybe default (head xs)

/// 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:
/// tail [0, 1] = Some 
/// tail  = Some []
/// tail [] = None
///
val <a> tail : List a -> Maybe (List a) =
\ Nil -> None
| Cons _ xs -> Some xs

/// Returns the minimum of a list, if any. Uses the ordering function provided
/// as the first argument to compare elements.
///
/// Examples:
/// minimum compareInt [] = None
/// minimum compareInt [1, 6, 0, 234, 2] = Some 0
val <a> minimum : (a -> a -> Ordering) -> List a -> Maybe a = \cmp -> \lst ->
Maybe::map2 (foldl (min cmp)) (head lst) (tail lst)

/// Returns the maximum of a list, if any. Uses the ordering function provided
/// as the first argument to compare elements.
///
/// Examples:
/// maximum compareInt [] = None
/// maximum compareInt [1, 6, 0, 234, 2] = Some 234
val <a> maximum : (a -> a -> Ordering) -> List a -> Maybe a = \cmp -> \lst ->
Maybe::map2 (foldl (max cmp)) (head lst) (tail lst)

/// Returns 'True' if the list contains the given value.
/// Otherwise it returns 'False'.
///
/// Examples:
/// contains 5 [] = False
/// contains 3.5 [0.0, 3.5, 7.0] = True
///
val <a: Ord> contains : a -> List a -> Bool = prim__List_contains

/// The 'sort' function takes an ordering function and a list,
/// and returns an ordered list.
///
/// Examples:
/// sort compareInt [4, 2, 3]
///   = [2, 3, 4]
///
val <a> sort : (a -> a -> Ordering) -> List a -> List a = prim__List_sort

/// The 'isSorted' function takes an ordering function and a list,
/// and returns True, if the list is ordered. Otherwise returns 'False'.
///
/// Examples:
/// isSorted compareInt []
///  = True
/// isSorted compareInt [1, 3, 3, 6]
///  = True
/// isSorted compareInt [1, 6, 3]
///  = False
///
val <a> isSorted : (a -> a -> Ordering) -> List a -> Bool = \ordering -> \lst -> let
val step =
\ (False, _) as acc -> const acc
| (True, None) -> (\curr -> (True, Some curr))
| (True, Some prev) -> \curr -> let
val unexpectedOrder = ordering prev curr = Greater
in (not unexpectedOrder, Some curr)
in fst (foldl step (True, None) lst)

/// The 'length' function returns the number of elements in a list.
/// Examples:
/// length ["a", "b", "c"] = 3
/// length [] = 0
///
val <a> length : List a -> Int = foldl (\n -> \_ -> n + 1) 0

/// 'isEmpty' returns True if a list is empty. False otherwise.
///
/// Examples
/// isEmpty [1, 2, 3]
///    = False
///
val <a> isEmpty : List a -> Bool =
\ Nil -> True
| _ -> False

/// 'map f xs' is the list obtained by applying the function f on each of the
/// elements in the list 'xs'.
///
/// Examples:
/// map (\n -> n * 2) [1, 2, 3]
///   = [2, 4, 6]
///
val <a, b> map : (a -> b) -> List a -> List b =
\f -> foldr (\x -> \ys -> Cons (f x) ys) Nil

/// The 'mapMaybe' function is a version of 'map' which takes a partial function,
/// and throws away the undefined value (i.e. the 'None's).
///
/// Examples:
/// mapMaybe (\n -> if (n > 100) (Some n) else None) [140, 40, 103]
///   = [140, 103]
///
/// mapMaybe id [Some "a", None, Some "b"]
///   = ["a", "b"]
///
val <a, b> mapMaybe : (a -> Maybe b) -> List a -> List b =
\f -> foldr (\x -> \acc -> maybe acc (\y -> Cons y acc) (f x)) Nil

/// The '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:
/// filter (\n -> n < 10) [10, 1, 2, 100]
///   = [1, 2]
///
val <a> filter : (a -> Bool) -> List a -> List a =
\f -> foldr (\y -> \ys -> if (f y) Cons y ys else ys) Nil

/// The 'zipWith' function generalises '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.
///
/// Examples:
/// zipWith (\m -> \n -> m + n) [4, 5] [10, 20]
///   = [14, 25]
///
/// zipWith (\m -> \n -> m + n) [4, 5] 
///   = 
///
/// zipWith (\m -> \n -> m + n)  [10, 20]
///   = 
///
val <a, b, c> zipWith : (a -> b -> c) -> List a -> List b -> List c = \f ->
let val step = \a -> \g ->
\ Nil -> Nil
| Cons b bs -> Cons (f a b) (g bs)
in foldr step (\_ -> Nil)

/// The '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:
/// zip [1,2] ["a", "b"]
///   = [(1, "a"), (2, "b")]
///
/// zip [] ["a"]
///   = []
///
/// zip [(1,"a"), (2,"b")] [True, False]
///   = [((1,"a"),True), ((2,"b"), False)]
///
val <a, b> zip : List a -> List b -> List (Tuple a b) = List::zipWith (\a -> \b -> (a, b))

/// Given a predicate and a list, 'any' returns 'True' if, and only if, there
/// exists an element in the list which satisfies the predicate.
///
/// Examples:
/// any (\n -> n > 4) [2, 10] = True
/// any (\n -> n > 4) [2, 0] = False
/// any (\n -> n > 4) [] = False
///
val <a> any : (a -> Bool) -> List a -> Bool =
\pred -> foldl (\b -> \x -> b || pred x) False

/// Given a predicate and a list, 'all' returns 'True' if, and only if, all
/// elements in the list satisfy the predicate.
///
/// Examples:
/// all (\n -> n > 4) [5, 6] = True
/// all (\n -> n > 4) [5, 3] = False
/// all (\n -> n > 4) [] = True
///
val <a> all : (a -> Bool) -> List a -> Bool =
\pred -> foldl (\b -> \x -> b && pred x) True

/// Returns the first element in the list which satisfies the predicate,
/// if any.
///
/// Examples:
/// first (\n -> n > 4) [3, 42, 100]
///   = Some 42
///
/// first (\n -> n > 4) [3, 2, 1]
///   = None
///
val <a> first : (a -> Bool) -> List a -> Maybe a =
\pred -> foldr (\x -> \acc -> if (pred x) (Some x) else acc) None

/// Returns the last element in the list which satisfies the predicate,
/// if any.
///
/// Examples:
/// last (\n -> n > 4) [3, 42, 100]
///   = Some 100
///
/// last (\n -> n > 4) [3, 2, 1]
///   = None
///
val <a> last : (a -> Bool) -> List a -> Maybe a =
\pred -> foldl (\acc -> \x -> if (pred x) (Some x) else acc) None

/// Appends two lists.
///
/// Examples:
/// append ["a"] ["b"]
///   = ["a", "b"]
///
/// append [] ys = ys
///
/// append xs [] = xs
///
val <a> append : List a -> List a -> List a =
\xs -> \ys -> foldr (\x -> \acc -> Cons x acc) ys xs

/// Flattens a list of lists into one list, by appending them to each other.
///
/// Examples:
/// concat [[1, 2], , ]
///   = [1, 2, 3, 4]
///
val <a> concat : List (List a) -> List a = foldr List::append Nil

/// Maps a list-returning function over a list and concatenates the results.
///
/// Examples:
/// concatMap (\n -> [n, n+1, n+2]) [1, 2, 3]
///   = [1, 2, 3, 2, 3, 4, 3, 4, 5]
///
val <a, b> concatMap : (a -> List b) -> List a -> List b =
\f -> foldr (\x -> \acc -> List::append (f x) acc) Nil

/// Reverses a list.
///
/// Examples:
/// reverse [1, 2, 3]
///   = [3, 2, 1]
///
val <a> reverse : List a -> List a = foldl (\xs -> \x -> Cons x xs) Nil

/// Given an integer, m, and a list, 'take' returns the first m elements of
/// the list.  If the list has fewer than m elements, the whole list is
/// returned.
///
/// Examples:
/// take 2 ["a", "b", "c"]
///   = ["a", "b"]
///
/// take 2 ["a"]
///   = ["a"]
///
val <a> take : Int -> List a -> List a = \(m : Int) -> \xs ->
let val f = \x -> \rest -> \n ->
if (n <= 0) Nil
else Cons x (rest (n - 1))
in foldr f (const Nil) xs m

/// Given a predicate, p, and a list, 'takeWhile' takes the elements of the
/// list as long as the predicate holds.
///
/// Examples:
/// takeWhile (const True) ["a", "b", "c"]
///   = ["a", "b", "c"]
///
/// takeWhile (\x -> x > 5) [6, 9, 5, 4, 8]
///   = [6, 9]
///
val <a> takeWhile : (a -> Bool) -> List a -> List a = \pred ->
foldr (\el -> \acc -> if (pred el) (Cons el acc) else []) []

/// Given an integer, m, and a 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:
/// drop 2 ["a", "b", "c"]
///   = ["c"]
///
/// drop 1 ["a"] = []
///
/// drop 1 [] = []
///
val <a> drop : Int -> List a -> List a =
\(m : Int) -> \xs ->
let val f = \_ -> \rest -> \n -> \xs1 ->
if (n <= 0) xs1
else rest (n - 1) (fromMaybe Nil (List::tail xs1))
in foldr f (const (const Nil)) xs m xs
}

//////////////////////
// NonEmptyList
//////////////////////

module NonEmptyList {

/// Turns a non-empty list into an ordinary list.
///
/// Examples:
///
/// toList (NonEmpty 1 []) = 
/// toList (NonEmpty 1 [2, 3]) = [1, 2, 3]
val <a> toList : NonEmptyList a -> List a = \NonEmpty x xs -> Cons x xs

/// Converts a list into a non-empty list, if the given list is not empty.
/// Otherwise it returns 'None'.
///
/// Examples:
///
/// fromList [] = None
/// fromList [1, 2, 3] = Some (NonEmpty 1 [2, 3])
val <a> fromList : List a -> Maybe (NonEmptyList a) =
\ Nil -> None
| Cons hd rest -> Some (NonEmpty hd rest)

/// Creates a non-empty list with one element.
///
/// Examples:
///
/// singleton 5 = NonEmpty 5 []
/// singleton "a" = NonEmpty "a" []
val <a> singleton: a -> NonEmptyList a = \x -> NonEmpty x []

/// Returns the head (i.e. the first element) of the non-empty list.
///
/// Examples:
///
/// head (NonEmpty 0 []) = 0
/// head (NonEmpty 1 [2, 3]) = 1
val <a> head : NonEmptyList a -> a = \NonEmpty x _ -> x

/// Returns the tail of a non-empty list (i.e. what remains when stripping away the first element).
///
/// Examples:
///
/// tail (NonEmpty 0 []) = []
/// tail (NonEmpty 1 [2, 3]) = [2, 3]
val <a> tail : NonEmptyList a -> List a = \NonEmpty _ xs -> xs

/// Returns the minimum of a non-empty list.
/// Uses the ordering function provided as the first argument to compare elements.
///
/// Examples:
///
/// minimum compareInt (NonEmpty 0 []) = 0
/// minimum compareInt (NonEmpty 1 [6, 0, 234, 2]) = 0
val <a> minimum : (a -> a -> Ordering) -> NonEmptyList a -> a = \cmp -> \NonEmpty h _ as nel ->
fromMaybe h (List::minimum cmp (toList nel))

/// Returns the maximum of a non-empty list.
/// Uses the ordering function provided as the first argument to compare elements.
///
/// Examples:
///
/// maximum compareInt (NonEmpty 0 []) = 0
/// maximum compareInt (NonEmpty 1 [6, 0, 234, 2]) = 234
val <a> maximum : (a -> a -> Ordering) -> NonEmptyList a -> a = \cmp -> \NonEmpty h _ as nel ->
fromMaybe h (List::maximum cmp (toList nel))

/// Returns 'True' if the non-emptylist contains the given value.
/// Otherwise it returns 'False'.
///
/// Examples:
/// contains 5 (NonEmpty 0 []) = False
/// contains 3.5 (NonEmpty 0.0 [3.5, 7.0]) = True
///
val <a: Ord> contains : a -> NonEmptyList a -> Bool = \el -> comp (List::contains el) toList

/// The 'sort' function takes an ordering function and a non-empty list,
/// and returns an ordered non-empty list.
///
/// Examples:
/// sort compareInt (NonEmpty 4 [2, 3]) = NonEmpty 2 [3, 4]
///
val <a> sort : (a -> a -> Ordering) -> NonEmptyList a -> NonEmptyList a = \ordering -> \NonEmpty hs _ as lst ->
fromMaybe (NonEmpty hs []) (fromList (List::sort ordering (toList lst)))

/// The 'isSorted' function takes an ordering function and a non-empty list,
/// and returns True if the list is ordered. Otherwise, it returns 'False'.
///
/// Examples:
/// isSorted compareInt (NonEmpty 1 [3, 3, 6]) = True
/// isSorted compareInt (NonEmpty 1 [6, 3]) = False
///
val <a> isSorted : (a -> a -> Ordering) -> NonEmptyList a -> Bool = \ordering ->
comp (List::isSorted ordering) toList

/// The 'length' function returns the number of elements in a non-empty list.
/// Examples:
/// length (NonEmpty "a" ["b", "c"]) = 3
/// length (NonEmpty 1 []) = 1
///
val <a> length : NonEmptyList a -> Int = comp List::length toList

/// 'map f xs' is the list obtained by applying the function f on each of the
/// elements in the non-empty list 'xs'.
///
/// Examples:
/// map (\n -> n * 2) (NonEmpty 1 [2, 3]) = NonEmpty 2 [4, 6]
///
val <a, b> map : (a -> b) -> NonEmptyList a -> NonEmptyList b =
\f -> \NonEmpty x xs -> NonEmpty (f x) (List::map f xs)

/// The 'zipWith' function is like '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.
///
/// Examples:
/// zipWith (\m -> \n -> m + n) (NonEmpty 4 ) (NonEmpty 10 ) = NonEmpty 14 
/// zipWith (\m -> \n -> m + n) (NonEmpty 4 ) (NonEmpty 10 []) = NonEmpty 14 []
/// zipWith (\m -> \n -> m + n) (NonEmpty 4 []) (NonEmpty 10 ) = NonEmpty 14 []
///
val <a, b, c> zipWith : (a -> b -> c) -> NonEmptyList a -> NonEmptyList b -> NonEmptyList c = \f ->
\NonEmpty x xs -> \NonEmpty y ys -> NonEmpty (f x y) (List::zipWith f xs ys)

/// The 'zip' function takes two non-empty lists as arguments, and returns a
/// non-empty list of the elements pairwise together.
/// The resulting list always has the same length as the shortest input list.
///
/// Examples:
/// zip (NonEmpty 1 ) (NonEmpty "a" ["b"]) = NonEmpty (1, "a") [(2, "b")]
/// zip (NonEmpty 4 [5, 6]) (NonEmpty 10 [20, 30, 40]) = NonEmpty (4, 10) [(5, 20), (6, 30)]
///
val <a, b> zip : NonEmptyList a -> NonEmptyList b -> NonEmptyList (Tuple a b) = zipWith (\a -> \b -> (a, b))

/// Given a predicate and a non-empty list, 'any' returns 'True' if, and only if, there
/// exists an element in the list which satisfies the predicate.
///
/// Examples:
/// any (\n -> n > 4) (NonEmpty 2 ) = True
/// any (\n -> n > 4) (NonEmpty 2 ) = False
///
val <a> any : (a -> Bool) -> NonEmptyList a -> Bool =
\pred -> comp (List::any pred) toList

/// Given a predicate and a non-empty list, 'all' returns 'True' if, and only if, all
/// elements in the list satisfy the predicate.
///
/// Examples:
/// all (\n -> n > 4) (NonEmpty 5 ) = True
/// all (\n -> n > 4) (NonEmpty 5 ) = False
///
val <a> all : (a -> Bool) -> NonEmptyList a -> Bool =
\pred -> comp (List::all pred) toList

/// Returns the first element in the non-empty list which satisfies the predicate,
/// if any.
///
/// Examples:
/// first (\n -> n > 4) (NonEmpty 3 [42, 100]) = Some 42
/// first (\n -> n > 4) (NonEmpty 3 [2, 1]) = None
///
val <a> first : (a -> Bool) -> NonEmptyList a -> Maybe a =
\pred -> comp (List::first pred) toList

/// Returns the last element in the non-empty list which satisfies the predicate,
/// if any.
///
/// Examples:
/// last (\n -> n > 4) (NonEmpty 3 [42, 100]) = Some 100
/// last (\n -> n > 4) (NonEmpty 3 [2, 1]) = None
///
val <a> last : (a -> Bool) -> NonEmptyList a -> Maybe a =
\pred -> comp (List::last pred) toList

/// Adds a new element at the start of a non-empty list.
///
/// Examples:
/// cons "a" (NonEmpty "b" []) = NonEmpty "a" ["b"]
///
val <a> cons : a -> NonEmptyList a -> NonEmptyList a = \x -> \ys -> NonEmpty x (toList ys)

/// Appends two non-empty lists.
///
/// Examples:
/// append (NonEmpty "a" []) (NonEmpty "b" []) = NonEmpty "a" ["b"]
/// append (NonEmpty "a" ["b", "c"]) (NonEmpty "d" []) = NonEmpty "a" ["b", "c", "d"]
///
val <a> append : NonEmptyList a -> NonEmptyList a -> NonEmptyList a =
\NonEmpty x xs -> \ys -> NonEmpty x (List::append xs (toList ys))

/// Flattens a non-empty list of non-empty lists into one non-empty list.
///
/// Examples:
/// concat (NonEmpty (NonEmpty 1 ) [NonEmpty 3 [], NonEmpty 4 []]) = NonEmpty 1 [2, 3, 4]
///
val <a> concat : NonEmptyList (NonEmptyList a) -> NonEmptyList a = \NonEmpty (NonEmpty x xs) ys ->
NonEmpty x (List::concat (Cons xs (List::map toList ys)))

/// Maps a non-empty-list-returning function over a non-empty list and concatenates the results.
///
/// Examples:
/// concatMap (\n -> NonEmpty n [n+1, n+2]) (NonEmpty 1 [2, 3]) = (NonEmpty 1 [2, 3, 2, 3, 4, 3, 4, 5])
///
val <a, b> concatMap : (a -> NonEmptyList b) -> NonEmptyList a -> NonEmptyList b =
\f -> \NonEmpty x xs ->
(\NonEmpty fx fxs -> NonEmpty fx (List::append fxs (List::concatMap (comp toList f) xs))) (f x)

/// Returns the final (i.e. last) element of a non-empty list.
///
/// Examples:
/// final (NonEmpty 1 [2, 3]) = 3
///
val <a> final : NonEmptyList a -> a = \NonEmpty x xs -> fromMaybe x (List::last (const True) xs)

/// Reverses a non-empty list.
///
/// Examples:
/// reverse (NonEmpty 1 [2, 3]) = NonEmpty 3 [2, 1]
///
val <a> reverse : NonEmptyList a -> NonEmptyList a = \xs -> fromMaybe xs (fromList (List::reverse (toList xs)))

}

//////////////////////
// Map
//////////////////////

module Map {
/// Returns a new empty map.
///
val <k, v> empty : Map k v = prim__Map_empty

/// Returns true iff the given map is empty.
///
/// Example:
///
///   Map::isEmpty Map::empty = true
val isEmpty = prim__Map_isEmpty

/// Returns a new map that contains, in addition to the keys
/// already present in the argument map, the given key/value.
///
/// Examples:
/// val noElms = Map::empty
/// val oneElm = Map::insert 1 "One" noElms
/// val twoElms = Map::insert 2 "Two" oneElm
///
val <k : Ord, v> insert : k -> v -> Map k v -> Map k v = prim__Map_insert

/// Fold over the key/value pairs in a map.
///
val <k : Ord, v, a> fold : (k -> v -> a -> a) -> a -> Map k v -> a = prim__Map_fold

/// The 'toList' function returns a list of tuples (key, value) of elements of the map.
///
/// Example:
///
/// Map::toList (Map::fromList [(1, "A"), (2, "B")]) = [(2, "B"), (1, "A")]
///
val <k : Ord, v> toList : Map k v -> List (Tuple k v) = fold (\k -> \v -> Cons (k, v)) []

/// Returns a new map with the given key removed.
///
/// Examples:
/// val myMap = Map::insert 1 "One" Map::empty
/// val myEmptyMap = Map::remove 1 myMap
/// //             = Map::empty
/// val myMap2 = Map::remove 2 myMap
/// //         = myMap
///
val <k : Ord, v> remove : k -> Map k v -> Map k v = prim__Map_remove

/// Returns the value at the given key, if the key is in the map.
/// Otherwise it returns 'None'.
///
/// Examples:
/// val myMap = Map::insert 1 "One" Map::empty
/// val oneVal = Map::lookup 1 myMap
/// //         = Some "One"
/// val twoVal = Map::lookup 2 myMap
/// //         = None
///
val <k : Ord, v> lookup : k -> Map k v -> Maybe v = prim__Map_lookup

/// Returns the value at the given key, if the key is in the map.
/// Otherwise returns the given default value.
///
/// Examples:
/// val myMap = Map::insert 1 "One" Map::empty
/// val oneVal = Map::lookupOrDefault "Nothing" 1 myMap
///          = "One"
/// val twoVal = Map::lookupOrDefault "Nothing" 2 myMap
///         = "Nothing"
///
val <k : Ord, v> lookupOrDefault : v -> k -> Map k v -> v = \default -> \key -> \map ->
fromMaybe default (lookup key map)

/// Constructs a map that contains the elements in the given list.
///
/// Examples:
/// val prices = Map::fromList [("hammer", 10), ("saw", 12), ("axe", 15)]
///
val <k : Ord, v> fromList : List (Tuple k v) -> Map k v = \theList ->
let
val auxFun : Map k v -> Tuple k v -> Map k v = \accMap -> \(key, value) ->
Map::insert key value accMap
in
foldl auxFun Map::empty theList
}

//////////////////////
// Set
//////////////////////

module Set {
/// Returns a new empty set.
///
val <v> empty : Set v = prim__Set_empty

/// Returns a new set that contains, in addition to the elements
/// already present in the argument set, the given element.
///
/// Examples:
/// val emptySet = Set::empty
/// val oneElm = Set::insert 1 emptySet
/// val twoElms = Set::insert 2 oneElm
///
val <v : Ord> insert : v -> Set v -> Set v = prim__Set_insert

/// Returns a new set with the given element removed.
///
/// Examples:
/// val mySet = Set::insert 1 Set::empty
/// val myEmptySet = Set::remove 1 mySet
/// //             = Set::empty
/// val mySet2 = Set::remove 2 mySet
/// //         = mySet
///
val <v : Ord> remove : v -> Set v -> Set v = prim__Set_remove

/// Fold over the elements in a set.
///
/// Examples:
/// val sumElems = Set::fold (\x -> \sum -> x + sum) 0
/// val s = sumElems (Set::fromList [1, 2, 3])
/// //    = 6
///
val <v : Ord, a> fold : (v -> a -> a) -> a -> Set v -> a = prim__Set_fold

/// Returns 'True' if the set contains the given value.
/// Otherwise it returns 'False'.
///
/// Examples:
/// val mySet = Set::insert 1 Set::empty
/// val oneVal = Set::contains 1 mySet
/// //         = True
/// val twoVal = Set::contains 2 mySet
/// //         = False
///
val <v : Ord> contains : v -> Set v -> Bool = prim__Set_contains

/// Take the union of two sets.
///
/// Examples:
/// val setA = Set::fromList [1, 2]
/// val setB = Set::fromList [2, 3]
/// val setC = Set::union setA setB
/// //       = Set::fromList [1, 2, 3]
///
val <v : Ord> union : Set v -> Set v -> Set v = Set::fold Set::insert

/// Take the intersection of two sets.
///
/// Examples:
/// val setA = Set::fromList [1, 2]
/// val setB = Set::fromList [2, 3]
/// val setC = Set::intersection setA setB
/// //       = Set::singleton 2
///
val <v : Ord> intersection : Set v -> Set v -> Set v =
\l -> \r -> Set::fold (\x -> \s ->
if (Set::contains x r) Set::insert x s
else s) Set::empty l

/// Take the difference between two sets.
///
/// Examples:
/// val setA = Set::fromList [1, 2]
/// val setB = Set::fromList [2, 3]
/// val setC = Set::difference setA setB
/// //       = Set::fromList 
///
val <v : Ord> difference : Set v -> Set v -> Set v = Set::fold Set::remove

/// Constructs a set with the elements in the given list.
///
/// Examples:
/// val prices = Set::fromList [10, 12, 15]
///
val <v : Ord> fromList : List v -> Set v = foldl (flip Set::insert) Set::empty

/// Constructs a singleton set with just one element.
///
/// Examples:
/// val s = Set::singleton 1
/// //    = Set::fromList 
///
val <v : Ord> singleton : v -> Set v = \x -> Set::fromList [x]

/// Converts a set to a list.  The ordering is unspecified and may change.
///
/// Examples:
/// val l = [1, 2, 3, 1, 2]
/// val l2 = Set::toList (Set::fromList l)
/// //     = [1, 2, 3]
///
val <v : Ord> toList : Set v -> List v = Set::fold Cons Nil

/// Returns the size of a set.
///
/// Examples:
/// val a = Set::size Set::empty
/// //    = 0
/// val b = Set::size (Set::fromList [1, 1, 2])
/// //    = 2
///
val <v : Ord> size : Set v -> Int = Set::fold (\_ -> \x -> x + 1) 0
}

//////////////////////
// Period
//////////////////////

module Period {
val components : Period -> Components = prim__Period_components

val fromComponents : Components -> Period = prim__Period_fromComponents

val from : Int -> Int -> Int -> Period = \(y : Int) -> \(m : Int) -> \(d : Int) ->
Period::fromComponents (Period::Components { years = y, months = m, days = d })

val between : Date -> Date -> Period = prim__Period_between

val negated : Period -> Period = prim__Period_negated
}

//////////////////////
// Duration
//////////////////////

module Duration {
val components : Duration -> Components = prim__Duration_components

val fromComponents : Components -> Duration = prim__Duration_fromComponents

val from : Int -> Int -> Duration =
\(secs : Int) -> \(millis : Int) ->
Duration::fromComponents (Duration::Components { seconds = secs, milliseconds = millis })

val fromMinutes : Int -> Duration = \(minutes : Int) -> Duration::from (minutes*60) 0
val fromHours : Int -> Duration = \(hours : Int) -> Duration::from (hours * 60 * 60) 0
val fromDays : Int -> Duration = \(days : Int) -> Duration::from (days * 24 * 60 * 60) 0

val betweenInstants : Instant -> Instant -> Duration = prim__Duration_betweenInstants

val betweenTimes : Time -> Time -> Duration = prim__Duration_betweenTimes

val negated : Duration -> Duration = prim__Duration_negated
}

//////////////////////
// Instant
//////////////////////

module Instant {
val components : Instant -> Components = prim__Instant_components

val fromComponents : Components -> Instant = prim__Instant_fromComponents

val from : Int -> Int -> Instant = \(s : Int) -> \(ms : Int) ->
Instant::fromComponents (Instant::Components { second = s, millisecond = ms })

val addSeconds : Int -> Instant -> Instant = \(secs : Int) ->
Instant::addDuration (Duration::fromComponents (Duration::Components { seconds = secs, milliseconds = 0 }))

val addDays : Int -> Instant -> Instant = \(days : Int) ->
Instant::addSeconds (days * 24 * 60 * 60)
}

//////////////////////
// Year
//////////////////////

module Year {
/// Maps a year to its representation as an integer.
///
val toInt : Year -> Int = prim__Year_toInt

/// Constructs a year from its integer representation.
/// Valid range is -999999999 to 999999999.
/// Year numbers outside this range results in an error.
///
val fromInt : Int -> Year = prim__Year_fromInt

/// Checks whether a year is a leap year.
///
/// Examples:
/// val leap2000 = Year::isLeapYear (Year::fromInt 2000)
/// //           = True
/// val leap2013 = Year::isLeapYear (Year::fromInt 2013)
/// //           = False
///
val isLeapYear : Year -> Bool = prim__Year_isLeapYear

/// Returns the number of days in the given year.
///
/// Examples:
/// val days2000 = Year::length (Year::fromInt 2000)
/// //           = 366
/// val days2013 = Year::length (Year::fromInt 2013)
/// //           = 365
///
val length : Year -> Int = \(y : Year) -> if (Year::isLeapYear y) 366 else 365
}

//////////////////////
// Month
//////////////////////

module Month {
val toInt : Month -> Int =
\ January -> 1
| February -> 2
| March -> 3
| April -> 4
| May -> 5
| June -> 6
| July -> 7
| August -> 8
| September -> 9
| October -> 10
| November -> 11
| December -> 12

val firstDayOfMonth : Bool -> Month -> Int = \(isLeap : Bool) ->
let val leap = if (isLeap) 1 else 0 in
\ January -> 1
| February -> 32
| March -> 60 + leap
| April -> 91 + leap
| May -> 121 + leap
| June -> 152 + leap
| July -> 182 + leap
| August -> 213 + leap
| September -> 244 + leap
| October -> 274 + leap
| November -> 305 + leap
| December -> 335 + leap

val firstMonthOfQuarter : Month -> Month =
\ January -> January
| February -> January
| March -> January
| April -> April
| May -> April
| June -> April
| July -> July
| August -> July
| September -> July
| October -> October
| November -> October
| December -> October
}

//////////////////////
// YearMonth
//////////////////////

module YearMonth {
val components : YearMonth -> Components = prim__YearMonth_components

val fromComponents : Components -> YearMonth = prim__YearMonth_fromComponents

val from : Int -> Month -> YearMonth =
\(y : Int) -> \(m : Month) ->
YearMonth::fromComponents (YearMonth::Components { year = Year::fromInt y, month = m })

val lengthOfMonth : YearMonth -> Int = prim__YearMonth_lengthOfMonth

val isValidDay : Int -> YearMonth -> Bool =
\(day : Int) -> \(ym : YearMonth) ->
1 <= day && day <= YearMonth::lengthOfMonth ym
}

//////////////////////
// Date
//////////////////////

module Date {
val components : Date -> Components = prim__Date_components

val fromComponents : Components -> Date = prim__Date_fromComponents

val from : Int -> Month -> Int -> Date = \(y : Int) -> \(m : Month) -> \(d : Int) ->
Date::fromComponents (Date::Components { year = Year::fromInt y, month = m, day = d })

val epochDay : Date -> Int = prim__Date_epochDay

val dayOfWeek : Date -> DayOfWeek = prim__Date_dayOfWeek

}

//////////////////////
// Time
//////////////////////

module Time {
val components : Time -> Components = prim__Time_components

val fromComponents : Components -> Time = prim__Time_fromComponents

val from : Int -> Int -> Int -> Int -> Time =
\(h : Int) -> \(m : Int) -> \(s : Int) -> \(ms : Int) ->
Time::fromComponents (Time::Components { hour = h, minute = m, second = s, millisecond = ms })

}

//////////////////////
// DateTime
//////////////////////

type DateTime {
date : Date,
time : Time
}

module DateTime {
val addPeriod : Period -> DateTime -> DateTime = \(p : Period) -> \(dt : DateTime) ->
DateTime { use dt with date = Date::addPeriod p dt.date }
}

//////////////////////
// ZonedDateTime
//////////////////////

module ZonedDateTime {
val components : ZonedDateTime -> ComponentsWithOffset = prim__ZonedDateTime_components

val fromComponents : Components -> ZonedDateTime = prim__ZonedDateTime_fromComponents

val fromComponentsWithOffset : ComponentsWithOffset -> ZonedDateTime = prim__ZonedDateTime_fromComponentsWithOffset

val from : Date -> Time -> String -> ZonedDateTime =
\(d : Date) -> \(t : Time) -> \(z : String) ->
ZonedDateTime::fromComponents (ZonedDateTime::Components { date = d, time = t, zone = z })

val fromStrict : Date -> Time -> String -> ZoneOffset -> ZonedDateTime =
\(d : Date) -> \(t : Time) -> \(z : String) -> \(zo : ZoneOffset) ->
ZonedDateTime::fromComponentsWithOffset
(ZonedDateTime::ComponentsWithOffset
{ date = d
, time = t
, zone = z
, offset = zo
})

val fromInstant : Instant -> String -> ZonedDateTime = prim__ZonedDateTime_fromInstant

val withEarlierOffsetAtOverlap : ZonedDateTime -> ZonedDateTime = prim__ZonedDateTime_withEarlierOffsetAtOverlap

val withLaterOffsetAtOverlap : ZonedDateTime -> ZonedDateTime = prim__ZonedDateTime_withLaterOffsetAtOverlap

val instant : ZonedDateTime -> Instant = prim__ZonedDateTime_instant
}

//////////////////////
// ZoneOffset
//////////////////////

module ZoneOffset {
val fromSeconds : Int -> ZoneOffset = prim__ZoneOffset_fromSeconds

val toSeconds : ZoneOffset -> Int = prim__ZoneOffset_toSeconds
}

//////////////////////
// DayCount
//////////////////////

module DayCount {
val yearFraction : YearFraction -> Float = prim__yearFraction
}

//////////////////////
// Int
//////////////////////

module Int {
/// Converts an Int to a Float.
///
/// Examples:
///
/// Int::toFloat 4 = 4.0
///
val toFloat : Int -> Float = prim__Int_toFloat

/// Converts an Int to a String.
///
/// Examples:
///
/// Int::toString 4 = "4"
///
val toString : Int -> String = prim__Int_toString
}

//////////////////////
// Float
//////////////////////

module Float {
/// Converts a Float to an Int.
///
/// Examples:
///
/// Float::toInt 4.0 = 4
/// Float::toInt 1234.5678 = 1234
/// Float::toInt -1234.5678 = -1234
///
val toInt : Float -> Int = prim__Float_toInt
}

//////////////////////
// String
//////////////////////

module String {
/// Appends two string.
///
/// Examples:
///
/// String::append "Hello, " "World!" = "Hello, World!"
///
val append : String -> String -> String = prim__String_append

/// 'isEmpty' returns True if a string is the empty string. False otherwise.
///
/// Examples
/// String::isEmpty "" = True
/// String::isEmpty "abc" = False
///
val isEmpty = \(s: String) -> s = ""
}

//////////////////////
// Bool, continued
//////////////////////

/// The equal function returns 'True' if the two elements provided to it are equal, and 'False' otherwise.
///
/// Examples:
/// equal 5 6 = False
/// equal (3.14, 5) (3.14, 2 + 3) = True
///
val <a: Ord> equal : a -> a -> Bool = \x -> \y -> Set::contains x (Set::fromList [y])

//////////////////////
// Mathematical functions
//////////////////////

module Math {
/// Get the absolute value of an 'Int'.
val abs : Int -> Int = \x -> if (x < 0) 0 - x else x

/// Get the absolute value of a 'Float'.
val fabs : Float -> Float = \x -> if (x < 0.0) 0.0 - x else x

/// The power function.
///
/// Examples:
///
/// Math::pow 4.0 3.0 = 64.0
///
val pow : Float -> Float -> Float = prim__Math_pow

/// Square root.
///
/// Examples:
///
/// Math::sqrt 9.0 = 3.0
///
val sqrt : Float -> Float = \x -> Math::pow x 0.5

/// Rounds the number to an arbitrary decimal point using the given rounding mode
///
/// Examples:
///
/// Math::round 123.45 1 HalfUp ==> 123.5
///
val round : Float -> Int -> RoundingMode -> Float = prim__Math_round

/// Rounds the number towards positive infinity.
///
/// Examples:
///
/// Math::ceiling 1.3 = 2.0
/// Math::ceiling -1.3 = -1.0
///
val ceiling : Float -> Float = \x -> Math::round x 0 Ceiling

/// Rounds the number towards negative infinity.
///
/// Examples:
///
/// Math::floor 1.8 = 1.0
/// Math::floor -1.8 = -2.0
///
val floor : Float -> Float = \x -> Math::round x 0 Floor
}

//////////////////////
// Signed data
//////////////////////

module Signed {
/// Check if a 'Signed' is signed by a given 'PublicKey'
val <a> checkSignature : PublicKey -> Signed a -> Bool = prim__Signed_checkSignature

/// Extract the message contained within a 'Signed'
val <a> message : Signed a -> a = prim__Signed_message
}

//////////////////////
// Testing
//////////////////////

module Test {
val pass : UnitTest = prim__Test_pass

val <a> fail : a -> UnitTest = prim__Test_fail

val <a, b> expected : a -> b -> UnitTest = prim__Test_expected

val unitTest : String -> (Unit -> UnitTest) -> Test = prim__Test_unitTest

// Group tests together into a named suite.
val suite : String -> List Test -> Test = prim__Test_suite

val <a> withData : String -> (a -> Test) -> Test = prim__Test_withData

val <a> suiteWithData : String -> (a -> Tuple String (Unit -> UnitTest)) -> Test =
\name -> \testCase ->
withData name \cases ->
suite name
(List::map (\data -> let val (subName, body) = testCase data in unitTest subName body) cases)

val assert : Bool -> UnitTest =
\ True -> pass
| False -> fail "Assertion failed"

val <a: Ord> assertEqual : a -> a -> UnitTest =
\wanted -> \got ->
(\True -> pass | False -> expected wanted got)
(equal wanted got)

val <a, b> assertEqualBy : (a -> b -> Bool) -> a -> b -> UnitTest =
\predicate -> \wanted -> \got ->
(\True -> pass | False -> expected wanted got)
(predicate wanted got)

val assertEqualEpsilon : Float -> Float -> UnitTest =
\wanted -> \got ->
assertEqualBy (\(x : Float) -> \y -> Math::fabs (x - y) < 0.0000001)
wanted
got
}