cat
Basic category concepts
Functions: composition, identity, unit, constant, flip, curry, uncurry.
Types: Void, option (Maybe), product (Pair), coproduct (Either), Identity, and Const.
Types
Const
type from Haskell.
data Const c a = Const c
Only the first parameter affects the type, the second is ignore.
In gleam, we say that a
is a phantom type
.
Examples
let x: Const(Int, Bool) = Const(7)
let y: Const(String, String) = Const("abc")
pub type Const(c, a) {
Const(c)
}
Constructors
-
Const(c)
Canonical implementation of a coproduct
(sum type).
data Either a b = Left a | Right b
Examples
let check_positive = fn(x: Int) -> Either(Int, String) {
case x >= 0 {
True -> Left(x)
False -> Right("negative number")
}
}
check_positive(12)
// -> Left(12)
check_positive(-3)
// -> Right("negative number")
pub type Either(a, b) {
Left(a)
Right(b)
}
Constructors
-
Left(a)
-
Right(b)
Identity
type from Haskell
newtype Identity a = Identity a
Examples
Identity(8)
Identity("abc")
pub type Identity(a) {
Identity(a)
}
Constructors
-
Identity(a)
Maybe
type from Haskell (Option
in gleam).
data Maybe = Nothing | Just a
// Equivalent: Sum type between `unit` and `a`
type Maybe = Either () a
Examples
let safe_div = fn(a, b) {
case b != 0.0 {
True -> Just(a /. b)
False -> Nothing
}
}
safe_div(3.0, 4.0)
// -> Just(0,75)
safe_div(3.0, 0.0)
// -> Nothing
pub type Maybe(a) {
Nothing
Just(a)
}
Constructors
-
Nothing
-
Just(a)
Type for reverse functions
.
type Op r a = a -> r
Examples
let o = Op(fn(x) { x % 2 == 1 })
o.apply(6)
// -> False
pub type Op(r, a) {
Op(apply: fn(a) -> r)
}
Constructors
-
Op(apply: fn(a) -> r)
Canonical implementation of a product
(tuple).
Examples
let even_to_string = fn(x: Int) -> Pair(String, Bool) {
Pair(int.to_string(x), x % 2 == 0)
}
even_to_string(82).fst
// -> "82"
even_to_string(82).snd
// -> True
even_to_string(83).snd
// -> False
pub type Pair(a, b) {
Pair(fst: a, snd: b)
}
Constructors
-
Pair(fst: a, snd: b)
Encapsulates a function.
type Reader r a = r -> a
Examples
let r = Reader(fn(x) { x % 2 == 1 })
r.apply(6)
// -> False
pub type Reader(r, a) {
Reader(apply: fn(r) -> a)
}
Constructors
-
Reader(apply: fn(r) -> a)
State type.
Examples
let count: State(Int, Int) = State(fn(c) { #(c, c + 1) })
let current = 4
count.run(current)
// -> #(4, 5)
pub type State(s, a) {
State(run: fn(s) -> #(a, s))
}
Constructors
-
State(run: fn(s) -> #(a, s))
Encapsulates a pair whose first component is a value
of arbitrary type a and the second component is a string
.
Used to embellish
the return values of functions.
Examples
// Original function
f = fn(x) {x * 2}
// Embellished function
f = fn(x) {Writer(x * 2, "doubled ")}
pub type Writer(a) {
Writer(a, String)
}
Constructors
-
Writer(a, String)
Values
pub fn absurd(arg: Void) -> a
A function that can never
be called. It is polymorphic in the return type.
pub fn compose(g: fn(b) -> c, f: fn(a) -> b) -> fn(a) -> c
Given a function f
that takes an argument of type A and returns a B, and another function g
that takes a B and returns a C, you can compose
them by passing the result of f to g
.
(∘) :: (b -> c) -> (a -> b) -> (a -> c)
(g ∘ f) x = g (f x)
Properties of composition:
- Associativity h ∘ (g ∘ f) == (h ∘ g) ∘ f == h ∘ g ∘ f
- Identity see
id
for more info
Examples
let f = fn(x: Int) { int.to_string(x) }
let g = fn(s: String) { s == "28" }
let h = compose(g, f)
// -> h takes an int, transforms it into a string, then compares it to "28" and returns a bool
pub fn coproduct_factorizer(
i: fn(a) -> c,
j: fn(b) -> c,
) -> fn(Either(a, b)) -> c
Produces the factorizing function from a candidate
c with two injections
i and j to the best coproduct (either).
Property: i and j can be reconstructed
from the canonical coproduct e
With m = coproduct_factorizer(i, j), we have:
- i(x) = m(Left(x))
- j(x) = m(Right(x))
Examples
// Given the candidate #(Int, Bool) with two injections from Int and Bool
let i = fn(x: Int) {#(x, True)}
let j = fn(x: Bool) {#(9, x)}
// We show that Either(Int, Bool) is a better coproduct by finding the mapping m:
let m = coproduct_factorizer(i, j)
m(Left(2))
// -> #(2, True)
m(Right(False))
// -> #(9, False)
pub fn curry(f: fn(a, b) -> c) -> fn(a) -> fn(b) -> c
Transforms a function that takes 2 arguments
into a function that takes one argument
and returns a partial function
.
Examples
let map_123 = [1, 2, 3] |> curry(list.map)
map_123(fn(x) { x + 1 })
// -> [2, 3, 4]
map_123(fn(x) { x * 2 })
// -> [2, 4, 6]
pub fn fish(
m1: fn(a) -> Writer(b),
m2: fn(b) -> Writer(c),
) -> fn(a) -> Writer(c)
Composition
for the embellished functions that return the Writer type.
(>=>) :: (a -> Writer b) -> (b -> Writer c) -> (a -> Writer c)
m1 >=> m2 = \x ->
let (y, s1) = m1 x
(z, s2) = m2 y
in (z, s1 ++ s2)
Examples
let up_case = fn(s: String) { Writer(string.uppercase(s), "upCase ") }
let to_words = fn(s: String) { Writer(string.split(s, " "), "toWords ") }
let process = fish(up_case, to_words)
process("Anna has apples")
// -> Writer(["ANNA", "HAS", "APPLES"], "upCase toWords ")
pub fn flip(f: fn(a, b) -> c) -> fn(b, a) -> c
flip
function.
Examples
let f = fn(x: Int, y: Bool) { int.to_string(x) <> " " <> bool.to_string(y) }
flip(f)(True, 23)
// -> "23 True"
pub fn id(x: a) -> a
The identity function
is a unit of composition
.
id :: a -> a
id a = a
It follows the identity conditions:
- f ∘ id == f
- id ∘ f == f
Examples
id(3)
// -> 3
id("abc")
// -> "abc"
pub fn maybe_compose(
m1: fn(a) -> Maybe(b),
m2: fn(b) -> Maybe(c),
) -> fn(a) -> Maybe(c)
Composition
for the Maybe type
Examples
let safe_reciprocal = fn(x) {
case x != 0.0 {
True -> Just(1.0 /. x)
False -> Nothing
}
}
let safe_root = fn(x) {
case x >=. 0.0 {
True -> Just(x |> float.square_root() |> result.unwrap(0.0))
False -> Nothing
}
}
let safe_reciprocal_root = maybe_compose(safe_reciprocal, safe_root)
// -> a function that calculates sqrt(1/x)
safe_reciprocal_root(0.25)
// -> Just(2.0)
safe_reciprocal_root(0.0)
// -> Nothing
safe_reciprocal_root(-2.0)
// -> Nothing
pub fn maybe_id(x: a) -> Maybe(a)
The idenitity morphism
for the Maybe type.
Examples
maybe_id(25)
// -> Just(25)
maybe_id(Nothing)
// -> Just(Nothing)
pub fn maybe_to_option(m: Maybe(a)) -> option.Option(a)
Converts from Maybe
to gleam Option
.
Examples
maybe_to_option(Nothing)
// -> None
maybe_to_option(Just(2))
// -> Some(2)
pub fn option_to_maybe(o: option.Option(a)) -> Maybe(a)
Converts from gleam Option
to Maybe
.
Examples
option_to_maybe(None)
// -> Nothing
option_to_maybe(Some(2))
// -> Just(2)
pub fn pair_to_tuple(p: Pair(a, b)) -> #(a, b)
Converts from Pair
to gleam Tuple
.
Examples
pair_to_tuple(Pair(2, True))
// -> #(2, True)
pub fn product_factorizer(
p: fn(c) -> a,
q: fn(c) -> b,
) -> fn(c) -> Pair(a, b)
Produces the factorizing function from a candidate
c with two projections
p and q to the best product (tuple / pair).
Property: p and q can be reconstructed
from the canonical product
With m = product_factorizer(p, q), we have:
- p(x) = m(x).fst
- q(x) = m(x).snd
Examples
// Given the candidate Int with two projections to Int and Bool
let p = fn(x: Int) {x}
let q = fn(_: Int) {True}
// We show that Pair(Int, Bool) is a better product by finding the mapping m:
let m = product_factorizer(p, q)
m(7)
// -> Pair(7, True)
pub fn tuple_to_pair(t: #(a, b)) -> Pair(a, b)
Converts from gleam Tuple
to Pair
.
Examples
tuple_to_pair(#(2, True))
// -> Pair(2, True)
pub fn uncurry(g: fn(a) -> fn(b) -> c) -> fn(a, b) -> c
Transforms a function that takes one argument
and returns a partial function
into a function that takes `2 arguments.
Examples
let add_partial = fn(x) { fn(y) { x + y } }
let add = uncurry(add_partial)
add(2, 5)
// -> 7
add(1, 1)
// -> 2