Option.flix
/*
* Copyright 2019 Liam Palmer, Magnus Madsen
*
* Use of this source code is governed by the Apache 2.0 license
* that can be found in the LICENSE.md file.
*/
pub mod Option {
///
/// The Option type.
///
/// An option represents an optional value.
/// The constructor `None` represents an absent value,
/// whereas the constructor `Some(v)` represents the value `v`.
///
pub enum Option[t] with Eq, Order, ToString {
case None
case Some(t)
}
instance LowerBound[Option[t]] {
pub def minValue(_: Unit): Option[t] = None
}
instance PartialOrder[Option[t]] with PartialOrder[t] {
pub def lessEqual(x: Option[t], y: Option[t]): Bool = match (x, y) {
case (None, _) => true
case (Some(a), Some(b)) => PartialOrder.lessEqual(a, b)
case _ => false
}
}
instance JoinLattice[Option[t]] with JoinLattice[t] {
pub def leastUpperBound(x: Option[t], y: Option[t]): Option[t] = match (x, y) {
case (None, _) => y
case (_, None) => x
case (Some(a), Some(b)) => Some(JoinLattice.leastUpperBound(a, b))
}
}
instance MeetLattice[Option[t]] with MeetLattice[t] {
pub def greatestLowerBound(x: Option[t], y: Option[t]): Option[t] = match (x, y) {
case (None, _) => None
case (_, None) => None
case (Some(a), Some(b)) => Some(MeetLattice.greatestLowerBound(a, b))
}
}
instance Hash[Option[a]] with Hash[a] {
pub def hash(o: Option[a]): Int32 = match o {
case None => 1046527
case Some(y) => 919 * Hash.hash(y)
}
}
instance Functor[Option] {
pub def map(f: a -> b \ ef, o: Option[a]): Option[b] \ ef = Option.map(f, o)
}
instance Applicative[Option] {
pub def point(x: a): Option[a] = Option.point(x)
pub def ap(f: Option[a -> b \ ef], x: Option[a]): Option[b] \ ef = Option.ap(f, x)
// Same as the default implementation using `map` and `ap` but with less indirection.
redef map2(f: t1 -> t2 -> r \ ef, x1: Option[t1], x2: Option[t2]): Option[r] \ ef = Option.map2(f, x1, x2)
redef map3(f: t1 -> t2 -> t3 -> r \ ef, x1: Option[t1], x2: Option[t2], x3: Option[t3]): Option[r] \ ef = Option.map3(f, x1, x2, x3)
redef map4(f: t1 -> t2 -> t3 -> t4 -> r \ ef, x1: Option[t1], x2: Option[t2], x3: Option[t3], x4: Option[t4]): Option[r] \ ef = Option.map4(f, x1, x2, x3, x4)
redef map5(f: t1 -> t2 -> t3 -> t4 -> t5 -> r \ ef, x1: Option[t1], x2: Option[t2], x3: Option[t3], x4: Option[t4], x5: Option[t5]): Option[r] \ ef = Option.map5(f, x1, x2, x3, x4, x5)
}
instance Monad[Option] {
pub def flatMap(f: a -> Option[b] \ ef, x: Option[a]): Option[b] \ ef = Option.flatMap(f, x)
}
instance MonadZero[Option] {
pub def empty(): Option[a] = None
}
instance MonadZip[Option] {
pub def zipWith(f: (a, b) -> c \ ef, ma: Option[a], mb: Option[b]): Option[c] \ ef = Applicative.map2(f, ma, mb)
redef zip(ma: Option[a], mb: Option[b]): Option[(a, b)] = Applicative.map2((x, y) -> (x, y), ma, mb)
pub def zipWithA(f: (a, b) -> f[c] \ ef, x: Option[a], y: Option[b]): f[Option[c]] \ ef with Applicative[f] =
use Functor.{<$>};
match (x, y) {
case (Some(x1), Some(y1)) => Some <$> f(x1, y1)
case (_, _) => Applicative.point(None)
}
}
instance Foldable[Option] {
pub def foldLeft(f: (b, a) -> b \ ef, s: b, o: Option[a]): b \ ef = Option.foldLeft(f, s, o)
pub def foldRight(f: (a, b) -> b \ ef, s: b, o: Option[a]): b \ ef = Option.foldRight(f, o, s)
redef isEmpty(o: Option[a]): Bool = Option.isEmpty(o)
redef forAll(f: a -> Bool \ ef, o: Option[a]): Bool \ ef = Option.forAll(f, o)
redef exists(f: a -> Bool \ ef, o: Option[a]): Bool \ ef = Option.exists(f, o)
}
instance UnorderedFoldable[Option] {
pub def foldMap(f: a -> b \ ef, o: Option[a]): b \ ef with CommutativeMonoid[b] = Option.foldMap(f, o)
}
instance Traversable[Option] {
pub def traverse(f: a -> m[b] \ ef, t: Option[a]): m[Option[b]] \ ef with Applicative[m] =
use Applicative.{point};
use Functor.{map};
match t {
case None => point(None)
case Some(a) => f(a) |> map(Some)
}
redef sequence(t: Option[m[a]]): m[Option[a]] with Applicative[m] =
use Applicative.{point};
use Functor.{map};
match t {
case Some(ma) => map(Some, ma)
case None => point(None)
}
}
instance Filterable[Option] {
pub def filterMap(f: a -> Option[b] \ ef, o: Option[a]): Option[b] \ ef = Option.flatMap(f, o)
redef filter(f: a -> Bool \ ef, o: Option[a]): Option[a] \ ef = Option.filter(f, o)
}
instance Witherable[Option]
instance SemiGroup[Option[a]] with SemiGroup[a] {
pub def combine(x: Option[a], y: Option[a]): Option[a] = match (x, y) {
case (a, None) => a
case (None, b) => b
case (Some(x1), Some(y1)) => Some(SemiGroup.combine(x1, y1))
}
}
instance CommutativeSemiGroup[Option[a]] with CommutativeSemiGroup[a]
instance Monoid[Option[a]] with Monoid[a] {
pub def empty(): Option[a] = None
}
instance CommutativeMonoid[Option[a]] with CommutativeMonoid[a]
instance Iterable[Option[a]] {
type Elm = a
pub def iterator(rc: Region[r], o: Option[a]): Iterator[a, r, r] \ r = Option.iterator(rc, o)
}
instance ForEach[Option[a]] {
type Elm = a
pub def forEach(f: a -> Unit \ ef, o: Option[a]): Unit \ ef = Option.forEach(f, o)
}
instance Formattable[Option[a]] with Formattable[a] {
type Aef = Formattable.Aef[a]
pub def format(x: Option[a]): RichString \ Formattable.Aef[a] = match x {
case None => RichString.fromString("None")
case Some(v) => RichString.fromString("Some(") + Formattable.format(v) + RichString.fromString(")")
}
}
///
/// Returns the empty option variant `None`.
///
pub def empty(): Option[a] = None
///
/// Returns `true` iff `o` is `None`.
///
pub def isEmpty(o: Option[a]): Bool = match o {
case None => true
case Some(_) => false
}
///
/// Returns `true` iff `o` is `Some`.
///
pub def nonEmpty(o: Option[a]): Bool = not isEmpty(o)
///
/// Returns `v` if `o` is `Some(v).` Otherwise returns `d`.
///
pub def getWithDefault(d: a, o: Option[a]): a = match o {
case None => d
case Some(v) => v
}
///
/// Returns `v` if `o` is `Some(v)`. Otherwise aborts with a stack trace.
///
pub def getOrAbort(o: Option[a]): a \ Abort = match o {
case None => Abort.abortWithTrace("Option.getOrAbort(): called on None")
case Some(v) => v
}
///
/// Aborts with a stack trace if `o` is `None`.
///
pub def orAbort(o: Option[a]): Unit \ Abort = match o {
case None => Abort.abortWithTrace("Option.orAbort(): called on None")
case Some(_) => ()
}
///
/// Returns `o` if it is `Some(v)`. Otherwise returns `default`.
///
pub def withDefault(default: {default = Option[a]}, o: Option[a]): Option[a] = match o {
case None => default#default
case Some(_) => o
}
///
/// Returns `Some(dst)` if `o` is `Some(src)`. Otherwise returns `o`.
///
pub def replace(src: {src = a}, dst: {dst = a}, o: Option[a]): Option[a] with Eq[a] = match o {
case None => o
case Some(v) => Some(if (v == src#src) dst#dst else v)
}
///
/// Returns `true` if `o` is `Some(v)` and the predicate `f(v)` evaluates to `true`. Otherwise returns `false`.
///
pub def exists(f: a -> Bool \ ef, o: Option[a]): Bool \ ef = match o {
case None => false
case Some(v) => f(v)
}
///
/// Returns `true` if `o` is `Some(v)` and the predicate `f(v)` evaluates to `true` or if `o` is `None`.
///
/// Otherwise returns `false`.
///
pub def forAll(f: a -> Bool \ ef, o: Option[a]): Bool \ ef = match o {
case None => true
case Some(v) => f(v)
}
///
/// Returns `o` if `o` is `Some(v)` and the predicate `f(v)` is true. Otherwise returns `None`.
///
pub def filter(f: a -> Bool \ ef, o: Option[a]): Option[a] \ ef = match o {
case None => None
case Some(v) => if (f(v)) o else None
}
///
/// Returns `Some(f(v))` if `o` is `Some(v)`. Otherwise returns `None`.
///
pub def map(f: a -> b \ ef, o: Option[a]): Option[b] \ ef = match o {
case None => None
case Some(v) => Some(f(v))
}
///
/// Returns `Some(x)`.
///
pub def point(x: a): Option[a] = Some(x)
///
/// If both arguments are `Some`, return a `Some` containing the result of applying the function inside
/// `f` to the value inside `x`. Otherwise return `None`.
///
pub def ap(f: Option[a -> b \ ef], x: Option[a]): Option[b] \ ef =
match f {
case None => None
case Some(g) =>
match x {
case None => None
case Some(y) => Some(g(y))
}
}
///
/// Returns `f(v)` if `o` is `Some(v)`. Otherwise returns `None`.
///
pub def flatMap(f: a -> Option[b] \ ef, o: Option[a]): Option[b] \ ef = match o {
case None => None
case Some(v) => f(v)
}
///
/// Returns `1` if `o` is `Some(v)` and the predicate `f(v)` evaluates to `true`. Otherwise returns `0`.
///
pub def count(f: a -> Bool \ ef, o: Option[a]): Int32 \ ef = match o {
case None => 0
case Some(v) => if (f(v)) 1 else 0
}
///
/// Returns `v` if `o` is `Some(v)` else `0`.
///
pub def sum(o: Option[Int32]): Int32 =
Foldable.sum(o)
///
/// Returns `f(v)` if `o` is `Some(v)` else `0`.
///
pub def sumWith(f: a -> Int32 \ ef, o: Option[a]): Int32 \ ef =
Foldable.sumWith(f, o)
///
/// Returns `o` if `o` is `Some(v)` and the predicate `f(v)` evaluates to `true`. Otherwise returns `None`.
///
/// The function `f` must be pure.
///
pub def find(f: a -> Bool, o: Option[a]): Option[a] = match o {
case None => None
case Some(v) => if (f(v)) o else None
}
///
/// Returns `v` if `o` is `Some(v)`. Otherwise returns `None`.
///
pub def flatten(o: Option[Option[a]]): Option[a] = match o {
case None => None
case Some(v) => v
}
///
/// Returns the result of applying `combine` to all the elements in `o`, using `empty` as the initial value.
///
pub def fold(o: Option[a]): a with Monoid[a] = Foldable.fold(o)
///
/// Returns `f(z, v)` if `o` is `Some(v)`. Otherwise returns `z`.
///
pub def foldLeft(f: (b, a) -> b \ ef, z: b, o: Option[a]): b \ ef = match o {
case None => z
case Some(v) => f(z, v)
}
///
/// Returns `f(v, z)` if `o` is `Some(v)`. Otherwise returns `z`.
///
pub def foldRight(f: (a, b) -> b \ ef, o: Option[a], z: b): b \ ef = match o {
case None => z
case Some(v) => f(v, z)
}
///
/// Returns the result of mapping each element and combining the results.
///
pub def foldMap(f: a -> b \ ef, o: Option[a]): b \ ef with Monoid[b] =
foldLeft((acc, x) -> Monoid.combine(acc, f(x)), Monoid.empty(), o)
///
/// Returns `Some(v1 :: v2 :: ... :: vn)` if each of `xs_i` is `Some(v_i)`. Otherwise returns `None`.
///
pub def sequence(l: List[Option[a]]): Option[List[a]] =
def loop(ll, k) = match ll {
case Nil => k(Nil)
case None :: _ => None
case Some(x) :: xs => loop(xs, ks -> k(x :: ks))
};
loop(l, ks -> Some(ks))
///
/// Returns `Some(v1 :: v2 :: ... v :: vn)` if each of `f(l_i)` is `Some(v_i)`. Otherwise returns `None`.
///
pub def traverse(f: a -> Option[b] \ ef, l: List[a]): Option[List[b]] \ ef =
def loop(ll, k) = match ll {
case Nil => k(Nil)
case x :: xs =>
match f(x) {
case None => None
case Some(y) => loop(xs, ys -> k(y :: ys))
}
};
loop(l, ks -> Some(ks))
///
/// Returns `Some()` if each of `f(l_i)` is `Some(_)`. Otherwise returns `None`.
///
/// This function is the "forgetful" version of `traverse`, use it when you want the effect
/// of applying `f` to each element but do not care about collecting the results.
///
pub def traverseX(f: a -> Option[b] \ ef, l: List[a]): Option[Unit] \ ef = match l {
case Nil => Some()
case x :: xs =>
match f(x) {
case None => None
case Some(_) => traverseX(f, xs)
}
}
///
/// Returns the result of applying `f` to a start value `s` and the elements in `l`
/// going from left to right.
///
/// If at any step applying `f` fails (i.e. it produces a `None` value) the traversal
/// of `l` is short-circuited and `None` is returned.
///
/// If `f` is successfully applied to all the elements in `l` the result is of the form:
/// `Some(f(...f(f(s, x1), x2)..., xn))`.
///
pub def foldLeftM(f: (b, a) -> Option[b] \ ef, s: b, l: List[a]): Option[b] \ ef = match l {
case Nil => Some(s)
case x :: xs =>
match f(s, x) {
case Some(s1) => foldLeftM(f, s1, xs)
case None => None
}
}
///
/// Returns the result of applying `f` to a start value `s` and the elements in `l`
/// going from right to left.
///
/// If at any step applying `f` fails (i.e. it produces a `None` value) the traversal
/// of `l` is short-circuited and `None` is returned.
///
/// If `f` is successfully applied to all elements in `l` the result is of the form:
/// `Some(f(x1, ...f(xn-1, f(xn, s))...))`.
///
pub def foldRightM(f: (a, b) -> Option[b] \ ef, s: b, l: List[a]): Option[b] \ ef =
def loop(ll, k) = match ll {
case Nil => k(s)
case x :: xs =>
loop(
xs,
s1 -> match f(x, s1) {
case Some(s2) => k(s2)
case None => None
}
)
};
loop(l, s1 -> checked_ecast(Some(s1)))
///
/// Returns a one-element list of the value `v` if `o` is `Some(v)`. Otherwise returns the empty list.
///
pub def toList(o: Option[a]): List[a] = match o {
case None => Nil
case Some(v) => v :: Nil
}
///
/// Returns a one-element set of the value `v` if `o` is `Some(v)`. Otherwise returns the empty set.
///
pub def toSet(o: Option[a]): Set[a] with Order[a] = match o {
case None => Set.empty()
case Some(v) => Set.singleton(v)
}
///
/// Returns a singleton map with the mapping `k -> v` if `o` is `Some((k, v))`. Otherwise returns the empty map.
///
pub def toMap(o: Option[(k, v)]): Map[k, v] with Order[k] = match o {
case None => Map.empty()
case Some((k, v)) => Map.singleton(k, v)
}
///
/// Returns a map with elements of `s` as keys and `f` applied as values.
///
pub def toMapWith(f: a -> b, s: Option[a]): Map[a, b] with Order[a] =
Option.foldRight((x, acc) -> Map.insert(x, f(x), acc), s, Map.empty())
///
/// Returns the Option value `Ok(v)` if `o` is `Some(v)`. Otherwise returns `Err(e)`.
///
pub def toOk(e: e, o: Option[t]): Result[e, t] = match o {
case None => Err(e)
case Some(a) => Ok(a)
}
///
/// Returns the Option value `Err(e)` if `o` is `Some(e)`. Otherwise returns `Ok(d)`.
///
pub def toErr(d: t, o: Option[e]): Result[e, t] = match o {
case None => Ok(d)
case Some(e) => Err(e)
}
///
/// Returns the Validation value `Success(v)` if `o` is `Some(v)`. Otherwise lifts `e` into Validation's `Failure`.
///
pub def toSuccess(e: e, o: Option[t]): Validation[e, t] = match o {
case None => Validation.Failure(Nec.singleton(e))
case Some(a) => Validation.Success(a)
}
///
/// Returns `e` into Validation's `Failure` if `o` is `Some(e)`. Otherwise returns `Success(d)`.
///
pub def toFailure(d: t, o: Option[e]): Validation[e, t] = match o {
case None => Validation.Success(d)
case Some(e) => Validation.Failure(Nec.singleton(e))
}
///
/// Returns `Some((v1, v2))` if `o1` is `Some(v1)` and `o2` is `Some(v2)`. Otherwise returns `None`.
///
pub def zip(o1: Option[a], o2: Option[b]): Option[(a, b)] = match (o1, o2) {
case (None, _) => None
case (_, None) => None
case (Some(v1), Some(v2)) => Some((v1, v2))
}
///
/// Returns `(Some(v1), Some(v2))` if `o` is `Some((v1, v2))`. Otherwise returns `(None, None)`.
///
pub def unzip(o: Option[(a, b)]): (Option[a], Option[b]) = match o {
case None => (None, None)
case Some((v1, v2)) => (Some(v1), Some(v2))
}
///
/// Applies `f` to `v` if `o` is `Some(v)`. Otherwise does nothing.
///
pub def forEach(f: a -> Unit \ ef, o: Option[a]): Unit \ ef = match o {
case None => ()
case Some(v) => f(v)
}
///
/// Applies the binary function `f` to the values in `o1` and `o2`.
///
/// Returns `None` if either `o1` or `o2` are `None`.
///
pub def map2(f: (t1, t2) -> u \ ef, o1: Option[t1], o2: Option[t2]): Option[u] \ ef =
ap(map(f, o1), o2)
///
/// Applies the ternary function `f` to the values in `o1`, `o2` and `o3`.
///
/// Returns `None` if any of `o1`, `o2` and `o3` are `None`.
///
pub def map3(f: (t1, t2, t3) -> u \ ef, o1: Option[t1], o2: Option[t2], o3: Option[t3]): Option[u] \ ef =
ap(map2(f, o1, o2), o3)
///
/// Applies the 4-ary function `f` to the values in `o1`, `o2`, `o3` and `o4`.
///
/// Returns `None` if any of `o1`, `o2`, `o3` and `o4` are `None`.
///
pub def map4(f: (t1, t2, t3, t4) -> u \ ef, o1: Option[t1], o2: Option[t2], o3: Option[t3], o4: Option[t4]): Option[u] \ ef =
ap(map3(f, o1, o2, o3), o4)
///
/// Applies the 5-ary function `f` to the values in `o1`, `o2`, ... `o5`.
///
/// Returns `None` if any of `o1`, `o2`, ... `o5` are `None`.
///
pub def map5(f: (t1, t2, t3, t4, t5) -> u \ ef, o1: Option[t1], o2: Option[t2], o3: Option[t3], o4: Option[t4], o5: Option[t5]): Option[u] \ ef =
ap(map4(f, o1, o2, o3, o4), o5)
///
/// Applies the 6-ary function `f` to the values in `o1`, `o2`, ... `o6`.
///
/// Returns `None` if any of `o1`, `o2`, ... `o6` are `None`.
///
pub def map6(f: (t1, t2, t3, t4, t5, t6) -> u \ ef, o1: Option[t1], o2: Option[t2], o3: Option[t3], o4: Option[t4], o5: Option[t5], o6: Option[t6]): Option[u] \ ef =
ap(map5(f, o1, o2, o3, o4, o5), o6)
///
/// Applies the 7-ary function `f` to the values in `o1`, `o2`, ... `o7`.
///
/// Returns `None` if any of `o1`, `o2`, ... `o7` are `None`.
///
pub def map7(f: (t1, t2, t3, t4, t5, t6, t7) -> u \ ef, o1: Option[t1], o2: Option[t2], o3: Option[t3], o4: Option[t4], o5: Option[t5], o6: Option[t6], o7: Option[t7]): Option[u] \ ef =
ap(map6(f, o1, o2, o3, o4, o5, o6), o7)
///
/// Applies the 8-ary function `f` to the values in `o1`, `o2`, ... `o8`.
///
/// Returns `None` if any of `o1`, `o2`, ... `o8` are `None`.
///
pub def map8(f: (t1, t2, t3, t4, t5, t6, t7, t8) -> u \ ef, o1: Option[t1], o2: Option[t2], o3: Option[t3], o4: Option[t4], o5: Option[t5], o6: Option[t6], o7: Option[t7], o8: Option[t8]): Option[u] \ ef =
ap(map7(f, o1, o2, o3, o4, o5, o6, o7), o8)
///
/// Applies the 9-ary function `f` to the values in `o1`, `o2`, ... `o9`.
///
/// Returns `None` if any of `o1`, `o2`, ... `o9` are `None`.
///
pub def map9(f: (t1, t2, t3, t4, t5, t6, t7, t8, t9) -> u \ ef, o1: Option[t1], o2: Option[t2], o3: Option[t3], o4: Option[t4], o5: Option[t5], o6: Option[t6], o7: Option[t7], o8: Option[t8], o9: Option[t9]): Option[u] \ ef =
ap(map8(f, o1, o2, o3, o4, o5, o6, o7, o8), o9)
///
/// Applies the 10-ary function `f` to the values in `o1`, `o2`, ... `o10`.
///
/// Returns `None` if any of `o1`, `o2`, ... `o10` are `None`.
///
pub def map10(f: (t1, t2, t3, t4, t5, t6, t7, t8, t9, t10) -> u \ ef, o1: Option[t1], o2: Option[t2], o3: Option[t3], o4: Option[t4], o5: Option[t5], o6: Option[t6], o7: Option[t7], o8: Option[t8], o9: Option[t9], o10: Option[t10]): Option[u] \ ef =
ap(map9(f, o1, o2, o3, o4, o5, o6, o7, o8, o9), o10)
///
/// Returns an iterator over `o` with 1 element or an empty iterator if `o` is `None`.
///
pub def iterator(rc: Region[r], o: Option[a]): Iterator[a, r, r] \ r = match o {
case None => Iterator.empty(rc)
case Some(x) => Iterator.singleton(rc, x)
}
}