Last active
October 31, 2017 23:40
-
-
Save dtchepak/df9264a87d12c85682a8aad6b069049d to your computer and use it in GitHub Desktop.
Kotlin monoid attempt
This file contains hidden or 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
/** | |
* A type [T] with an associative binary operation. | |
* | |
* Must satisfy the associative property: | |
* `combine(combine(a, b), c) == combine(a, combine(b, c))` | |
*/ | |
interface Semigroup<T> { | |
fun combine(a: T, b: T): T | |
companion object { | |
fun <T> create(combiner: (T, T) -> T): Semigroup<T> = | |
object : Semigroup<T> { | |
override fun combine(a: T, b: T): T = combiner(a, b) | |
} | |
fun <T : Comparable<T>> min(): Semigroup<T> = create({ a, b -> if (a <= b) a else b }) | |
fun <T : Comparable<T>> max(): Semigroup<T> = create({ a, b -> if (a >= b) a else b }) | |
} | |
} | |
/** | |
* A [Semigroup] with an additional [empty] element such that: | |
* `combine(a, empty) == a == combine(empty, a)`. | |
*/ | |
interface Monoid<T> : Semigroup<T> { | |
val empty: T | |
companion object { | |
/** Create a monoid instance given an empty value and an associative [combiner] operation. */ | |
fun <T> create(empty: T, combiner: (T, T) -> T): Monoid<T> = | |
object : Monoid<T> { | |
override val empty: T = empty | |
override fun combine(a: T, b: T): T = combiner(a, b) | |
} | |
/** Given monoid instances for [F] and [S], create a monoid that works on [Pair]s of these types. */ | |
fun <F, S> pair(first: Monoid<F>, second: Monoid<S>): Monoid<Pair<F, S>> = | |
Monoid.create(first.empty to second.empty, | |
{ a, b -> first.combine(a.first, b.first) to second.combine(a.second, b.second) }) | |
/** Construct a monoid for a pair that has the same type for first and second elements. */ | |
fun <T> double(m: Monoid<T>): Monoid<Pair<T, T>> = Monoid.pair(m, m) | |
/** Given monoid instances for [F], [S] and [T], create a monoid that works on [Triple]s of these types. */ | |
fun <F, S, T> triple(first: Monoid<F>, second: Monoid<S>, third: Monoid<T>): Monoid<Triple<F, S, T>> = | |
Monoid.create(Triple(first.empty, second.empty, third.empty), | |
{ a, b -> | |
Triple(first.combine(a.first, b.first), | |
second.combine(a.second, b.second), | |
third.combine(a.third, b.third)) | |
}) | |
/** | |
* Construct a monoid from a product type with two fields, given a monoid that works on pairs | |
* and mappings to and from the type and a pair. | |
*/ | |
fun <F, S, R> twoProduct(monoid: Monoid<Pair<F, S>>, toPair: (R) -> Pair<F, S>, fromPair: (Pair<F, S>) -> R) = | |
Monoid.create(fromPair(monoid.empty), { a, b -> fromPair(monoid.combine(toPair(a), toPair(b))) }) | |
/** | |
* Construct a monoid from a product type with three fields, given a monoid that works on triples | |
* and mappings to and from the type and a triple. | |
*/ | |
fun <F, S, T, R> threeProduct(monoid: Monoid<Triple<F, S, T>>, toTriple: (R) -> Triple<F, S, T>, fromTriple: (Triple<F, S, T>) -> R) = | |
Monoid.create(fromTriple(monoid.empty), { a, b -> fromTriple(monoid.combine(toTriple(a), toTriple(b))) }) | |
/** Monoid for integer addition */ | |
val sum: Monoid<Int> by lazy { Monoid.create(0, Int::plus) } | |
/** Monoid for long addition */ | |
val sumLong: Monoid<Long> by lazy { Monoid.create(0L, Long::plus) } | |
/** Create a monoid from a [Semigroup] by making it work on nullable values, with `null` being the [empty] element */ | |
fun <T> fromSemigroup(sg: Semigroup<T>): Monoid<T?> = | |
Monoid.create<T?>(null, { a, b -> if (a != null && b != null) sg.combine(a, b) else null }) | |
/** Monoid that keeps track of the smallest value seen less than or equal to [startingMin] */ | |
fun <T : Comparable<T>> min(startingMin: T): Monoid<T> = create(startingMin, ::minOf) | |
/** Monoid that keeps track of the largest value seen greater than or equal to [startingMax] */ | |
fun <T : Comparable<T>> max(startingMax: T): Monoid<T> = create(startingMax, ::maxOf) | |
/** | |
* Monoid for list concatenation | |
* @see [List.plus] | |
*/ | |
fun <T> list(): Monoid<Iterable<T>> = Monoid.create(emptyList(), Iterable<T>::plus) | |
/** | |
* Monoid for map concatenation. | |
* @see [Map.plus] | |
*/ | |
fun <K, V> map(): Monoid<Map<K, V>> = Monoid.create(emptyMap(), { a, b -> a + b }) | |
} | |
} | |
/** Concatenates a list of values of a type [T] for which a [Monoid] exists. */ | |
fun <T> Monoid<T>.concat(items: Iterable<T>) = items.fold(empty, { acc, t -> combine(t, acc) }) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment