Created
January 15, 2017 04:28
-
-
Save friedbrice/559c344fd2dfd8fd51b3eebbfbb88fba to your computer and use it in GitHub Desktop.
Some ADTs in Scala.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
sealed trait Either[S, T] { | |
def fold[X]: (S => X) => (T => X) => X | |
def map[X]: (T => X) => Either[S, X] | |
def bind[X]: (T => Either[S, X]) => Either[S, X] | |
} | |
object Either { | |
def Left[S, T]: S => Either[S, T] = | |
s => new Either[S, T] { | |
def fold[X]: (S => X) => (T => X) => X = | |
f => _ => f(s) | |
def map[X]: (T => X) => Either[S, X] = | |
_ => Either.Left[S, X](s) | |
def bind[X]: (T => Either[S, X]) => Either[S, X] = | |
_ => Either.Left[S, X](s) | |
} | |
def Right[S, T]: T => Either[S, T] = | |
t => new Either[S, T] { | |
def fold[X]: (S => X) => (T => X) => X = | |
_ => f => f(t) | |
def map[X]: (T => X) => Either[S, X] = | |
f => Either.Right[S, X](f(t)) | |
def bind[X]: (T => Either[S, X]) => Either[S, X] = | |
k => k(t) | |
} | |
} | |
sealed trait Pair[S, T] { | |
def fold[X]: (S => T => X) => X | |
def map[X]: (T => X) => Pair[S, X] | |
def bind[X]: (T => Pair[S, X]) => Pair[S, X] | |
} | |
object Pair { | |
def apply[S, T]: S => T => Pair[S, T] = | |
s => t => new Pair[S, T] { | |
def fold[X]: (S => T => X) => X = | |
f => f(s)(t) | |
def map[X]: (T => X) => Pair[S, X] = | |
f => Pair(s)(f(t)) | |
def bind[X]: (T => Pair[S, X]) => Pair[S, X] = | |
k => k(t) | |
} | |
} | |
sealed trait Maybe[T] { | |
def fold[X]: X => (T => X) => X | |
def map[X]: (T => X) => Maybe[X] | |
def bind[X]: (T => Maybe[X]) => Maybe[X] | |
} | |
object Maybe { | |
def Nothing[T]: Maybe[T] = | |
new Maybe[T] { | |
def fold[X]: X => (T => X) => X = | |
x => _ => x | |
def map[X]: (T => X) => Maybe[X] = | |
_ => Maybe.Nothing | |
def bind[X]: (T => Maybe[X]) => Maybe[X] = | |
_ => Maybe.Nothing | |
} | |
def Just[T]: T => Maybe[T] = | |
t => new Maybe[T] { | |
def fold[X]: X => (T => X) => X = | |
_ => f => f(t) | |
def map[X]: (T => X) => Maybe[X] = | |
f => Maybe.Just(f(t)) | |
def bind[X]: (T => Maybe[X]) => Maybe[X] = | |
k => k(t) | |
} | |
} | |
sealed trait List[T] { | |
def fold[X]: (T => X => X) => X => X | |
def map[X]: (T => X) => List[X] | |
def bind[X]: (T => List[X]) => List[X] | |
} | |
object List { | |
def Nil[T]: List[T] | |
= new List[T] { | |
def fold[X]: (T => X => X) => X => X = | |
_ => x => x | |
def map[X]: (T => X) => List[X] = | |
_ => List.Nil | |
def bind[X]: (T => List[X]) => List[X] = | |
_ => List.Nil | |
} | |
def Cons[T]: T => List[T] => List[T] = | |
t => ts => new List[T] { | |
def fold[X]: (T => X => X) => X => X = | |
g => x => g(t)(ts.fold(g)(x)) | |
def map[X]: (T => X) => List[X] = | |
f => List.Cons(f(t))(ts.map(f)) | |
def bind[X]: (T => List[X]) => List[X] = | |
k => k(t).fold(List.Cons)(ts.bind(k)) | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
The constructors and extractors are analogous to the introduction rules and elimination rules of formal logics. I mean "analogous" in the strongest possible sense, i.e., they are the same, modulo a recasting of terminology.