Skip to content

Instantly share code, notes, and snippets.

@runarorama
Created May 7, 2015 14:06
Show Gist options
  • Save runarorama/33986541f0f1ddf4a3c7 to your computer and use it in GitHub Desktop.
Save runarorama/33986541f0f1ddf4a3c7 to your computer and use it in GitHub Desktop.
Higher-kinded types encoded as path-dependent types
trait λ {
type α
}
trait Functor extends λ {
type α <: λ
def map[A,B](x: α { type α = A })(f: A => B): α { type α = B }
}
sealed trait ListRep extends λ { self =>
def isEmpty: Boolean
def uncons: Option[(α, ListRep { type α = self.α })]
def foldRight[B](z: B)(f: (α, B) => B): B
def toList: List[α] = foldRight(scala.List[α]())(_ :: _)
}
abstract class Nil extends ListRep {
val isEmpty = true
def uncons = None
def foldRight[B](z: B)(f: (α, B) => B) = z
}
abstract class Cons extends ListRep { self =>
def head: α
def tail: ListRep {
type α = self.α
}
val isEmpty = false
def uncons = Some((head, tail))
def foldRight[B](z: B)(f: (α, B) => B) =
f(head, tail.foldRight(z)(f))
}
object List extends Functor {
type α = ListRep
type List[A] = ListRep { type α = A }
def map[A,B](as: List[A])(f: A => B) =
as.foldRight(nil[B])((a, bs) => cons(f(a), bs))
def nil[A]: List[A] = new Nil {
type α = A
}
def cons[A](a: A, as: List[A]): List[A] = new Cons {
type α = A
val head = a
val tail = as
}
}
object HigherKinded {
def unzip[F <: Functor, A, B](F: F)(abs: F.α { type α = (A,B) })
: (F.α { type α = A }, F.α { type α = B }) =
(F.map(abs)(_._1), F.map(abs)(_._2))
}
object Test {
import List._
val xs: List[(Int, Int)] = cons((1,2), cons((2,3), nil))
def foo = HigherKinded.unzip(List)(xs)
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment