arrow-recursion-data / arrow.recursion / hylo

hylo

fun <F, A, B> A.hylo(alg: Algebra<F, B>, coalg: Coalgebra<F, A>, FF: Functor<F>): B

Combination of cata and ana.

An implementation of merge-sort:

import arrow.Kind
import arrow.recursion.Algebra
import arrow.recursion.Coalgebra
import arrow.recursion.hylo
import arrow.typeclasses.Functor

// boilerplate that @higherkind generates
class ForTree private constructor()
typealias TreeOf<A, B> = Kind<TreePartialOf<A>, B>
typealias TreePartialOf<A> = Kind<ForTree, A>

// A simple binary tree
sealed class Tree<A, B> : TreeOf<A, B> {
 class Empty<A, B> : Tree<A, B>()
 class Leaf<A, B>(val a: A) : Tree<A, B>()
 class Branch<A, B>(val l: B, val r: B) : Tree<A, B>()

 companion object {
   fun <A> functor(): Functor<TreePartialOf<A>> = object : Functor<TreePartialOf<A>> {
     override fun <C, B> Kind<TreePartialOf<A>, C>.map(f: (C) -> B): Kind<TreePartialOf<A>, B> = when (val t = this as Tree<A, C>) {
       is Empty -> Empty()
       is Leaf -> Leaf(t.a)
       is Branch -> Branch(f(t.l), f(t.r))
     }
   }
 }
}

infix fun List<Int>.merge(other: List<Int>): List<Int> = when {
 this.isEmpty() -> other
 other.isEmpty() -> this
 else ->
   if (first() > other.first()) (listOf(other.first()) + (this merge other.drop(1)))
   else (listOf(first()) + (this.drop(1) merge other))
}

fun main() {
 val unfold: Coalgebra<TreePartialOf<Int>, List<Int>> = {
   when {
     it.isEmpty() -> Tree.Empty()
     it.size == 1 -> Tree.Leaf(it.first())
     else -> (it.size / 2).let { half ->
       Tree.Branch<Int, List<Int>>(it.take(half), it.drop(half))
     }
   }
 }
 val fold: Algebra<TreePartialOf<Int>, List<Int>> = {
   (it as Tree<Int, List<Int>>).let { t ->
     when (t) {
       is Tree.Empty -> emptyList()
       is Tree.Leaf -> listOf(t.a)
       is Tree.Branch -> t.l merge t.r
     }
   }
 }

 (0..1000).shuffled().also(::println).hylo(fold, unfold, Tree.functor()).also(::println)
}

Note: Not stack-safe. Use hyloM with a stack-safe monad, like Eval

Do you like Arrow?

Arrow Org
<