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 [0] = Some 0
  /// head [] = None
  ///
  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] = 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 [1]
  /// tail [0] = 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] [10]
  ///   = [14]
  ///
  /// zipWith (\m -> \n -> m + n) [4] [10, 20]
  ///   = [14]
  ///
  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], [3], [4]]
  ///   = [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 []) = [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 [5]) (NonEmpty 10 [20]) = NonEmpty 14 [25]
  /// zipWith (\m -> \n -> m + n) (NonEmpty 4 [5]) (NonEmpty 10 []) = NonEmpty 14 []
  /// zipWith (\m -> \n -> m + n) (NonEmpty 4 []) (NonEmpty 10 [20]) = 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 [2]) (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 [10]) = True
  /// any (\n -> n > 4) (NonEmpty 2 [0]) = 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 [6]) = True
  /// all (\n -> n > 4) (NonEmpty 5 [3]) = 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 [2]) [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 [1]
    ///
    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 [1]
    ///
    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 add : Period -> Period -> Period = prim__Period_add

  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 add : Duration -> Duration -> Duration = prim__Duration_add

  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 addDuration : Duration -> Instant -> Instant = prim__Instant_addDuration

  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

  val addPeriod : Period -> Date -> Date = prim__Date_addPeriod
}

//////////////////////
// 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 })

  val addDuration : Duration -> Time -> Time = prim__Time_addDuration
}

//////////////////////
// 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 addPeriod : Period -> ZonedDateTime -> ZonedDateTime = prim__ZonedDateTime_addPeriod

  val addDuration : Duration -> ZonedDateTime -> ZonedDateTime = prim__ZonedDateTime_addDuration

  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 {
  /// A unit test assertion that always passes
  val pass : UnitTest = prim__Test_pass

  /// A unit test assertion that always fails. The argument is used as
  /// the assertion failure message.
  val <a> fail : a -> UnitTest = prim__Test_fail

  /// A unit test assertion that always fails. The first argument is
  /// presented as the expected value, and the second argument is
  /// presented as what was actually found.
  val <a, b> expected : a -> b -> UnitTest = prim__Test_expected

  /// Run a unit test as part of a test suite. The provided string is
  /// the test name, used in printed reports and in development tools.
  val unitTest : String -> (Unit -> UnitTest) -> Test = prim__Test_unitTest

  /// Group tests together into a named suite. This does not affect
  /// whether they pass or fail, but it can make the results of
  /// running many tests easier to understand. The first argument is
  /// the name of the test suite.
  val suite : String -> List Test -> Test = prim__Test_suite

  /// Contstruct a test based on some external data provided by the
  /// testing system. The first argument is a key used to select the
  /// appropriate external data source, and the second is a function
  /// that builds a test from the found data.
  ///
  /// Beware: if the external data doesn't have the type expected by
  /// the testing function, then CSL will crash while running tests!
  val <a> withData : String -> (a -> Test) -> Test = prim__Test_withData

  /// Given a data source name that provides a list of test data, use
  /// the provided test construction function to transform each test
  /// datum into a unit test name and a unit test. The resulting test
  /// suite runs one test for each item of input data and is named
  /// identically to the test data source.
  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)

  /// Assert that some condition is true. If not, the test fails.
  val assert : Bool -> UnitTest =
    \ True -> pass
    | False -> fail "Assertion failed"

  /// Assert that some condition is false. If not, the test fails.
  val assertFalse = \b -> Test::assert (not b)

  /// Assert that two values are equal. If then are not, then the
  /// first one is reported as the expected value, and the second is
  /// reported as the received value.
  val <a: Ord> assertEqual : a -> a -> UnitTest =
    \wanted -> \got ->
      (\True -> pass | False -> expected wanted got)
      (equal wanted got)

  /// Use a custom predicate to assert the equality of two values. If
  /// the assertion fails, then the first value is presented as the
  /// desired value, while the second is presented as the received
  /// value.
  val <a, b> assertEqualBy : (a -> b -> Bool) -> a -> b -> UnitTest =
    \predicate -> \wanted -> \got ->
      (\True -> pass | False -> expected wanted got)
      (predicate wanted got)

  /// Assert that the difference between two floats is less than 0.0000001.
  val assertEqualEpsilon : Float -> Float -> UnitTest =
    \wanted -> \got ->
      assertEqualBy (\(x : Float) -> \y -> Math::fabs (x - y) < 0.0000001)
        wanted
        got

  /// Run a test with a freshly-constructed agent. The provided string
  /// is used in two ways: it names the agent internally, which can
  /// lead to better test failure messages in many CSL backends, and
  /// multiple invocations with the same string will result in the
  /// same agent.
  val withAgent : String -> (Agent -> Test) -> Test = prim__Test_withAgent

  /// Run a test with a pair of freshly-constructed agents. The
  /// provided strings are used in two ways: they name the agents
  /// internally, which can lead to better test failure messages in
  /// many CSL backends, and multiple invocations with the same strings
  /// will result in the same agents.
  val with2Agents : Tuple String String -> (Tuple Agent Agent -> Test) -> Test =
    \(name1, name2) -> \f ->
      withAgent name1 \agent1 -> withAgent name2 \agent2 ->
        f (agent1, agent2)

  /// Run a scenario test under a given name.
  val runScenario : String -> Scenario -> Test = prim__Test_runScenario
}

module Scenario {
  /// Apply an event to the current contract. If the event cannot be
  /// applied, the scenario test fails.
  val event : Event -> Scenario::Step = prim__Scenario_event

  /// Assert that the contract is fulfilled, meaning that it is
  /// considered acceptable if no more events occur. Note that this
  /// does not rule out further events - they are optional.
  val isFulfilled : Scenario::Step = prim__Scenario_isFulfilled

  /// Assert that the contract is not fulfilled, meaning that further
  /// events are mandatory.
  val isNotFulfilled : Scenario::Step = prim__Scenario_isNotFulfilled

  /// Run a sequence of scenario steps in order.
  val steps : List Scenario::Step -> Scenario::Step = prim__Scenario_steps

  // Run the given scenario step. If it succeeds, the contract under
  // test has its state rolled back as if the step had never
  // occurred. If it fails, then the test fails.
  val withRollback : Scenario::Step -> Scenario::Step = prim__Scenario_withRollback

  // Run the given scenario step. If it fails, then the contract under
  // test has its state rolled back as if the step had never
  // occurred. If it succeeds, then the test fails with the provided
  // message.
  val expectFailure : String -> Scenario::Step -> Scenario::Step = prim__Scenario_expectFailure

  /// Compute a scenario step from the list of events that have been applied thus far.
  val withHistory : (List Event -> Scenario::Step) -> Scenario::Step = prim__Scenario_withHistory

  /// Run a unit test assertion as part of a scenario test.
  val unitTest : String -> (Unit -> UnitTest) -> Scenario::Step =  prim__Scenario_unitTest

  /// Assert that the history of events thus far satisfies some
  /// condition. If not, the scenario test fails with the provided
  /// message.
  val eventsSatisfy : String -> (List Event -> Bool) -> Scenario::Step = \message -> \predicate ->
    withHistory \events ->
      unitTest message \() ->
        if (predicate events)
          Test::pass
        else
          Test::fail message

  /// Assert that an event can be applied without applying it.
  val canApplyEvent : Event -> Scenario::Step = \e ->
    withRollback (event e)

  /// Assert that an event cannot be applied.
  val cannotApplyEvent : Event -> Scenario::Step = \e ->
    withRollback (expectFailure "Cannot apply event" (event e))
}