Skip to content

Instantly share code, notes, and snippets.

@xuwei-k
Forked from johnynek/dotty_list.scala
Created January 12, 2020 13:43
Show Gist options
  • Save xuwei-k/a17540d0304cd55dca4947d7de0ee456 to your computer and use it in GitHub Desktop.
Save xuwei-k/a17540d0304cd55dca4947d7de0ee456 to your computer and use it in GitHub Desktop.
Implementation of linked list using dotty features (opaque type, union types, extension methods, type lambda).
// unfortunately
// opaque type Fix[F[_]] = F[Fix[F]]
// won't work (no recursion in opaque type), but this implementation is safe, but scary due to asInstanceOf
object FixImpl {
type Fix[F[_]]
inline def fix[F[_]](f: F[Fix[F]]): Fix[F] = f.asInstanceOf[Fix[F]]
inline def unfix[F[_]](f: Fix[F]): F[Fix[F]] = f.asInstanceOf[F[Fix[F]]]
}
import FixImpl._
type OrNull[A <: AnyRef] = A | Null
// List[A] = null | (A, null) | (A, (A, null)) | (A, (A, (A, null))) | ...
opaque type List[A] = Fix[[X] =>> OrNull[(A, X)]]
object List {
def empty[A]: List[A] = fix(null)
}
given ListOps {
def (head: A) ::[A](self: List[A]): List[A] =
fix((head, self))
def (self: List[A]) isEmpty[A] = unfix(self) == null
def (self: List[A]) headOption[A] = {
unfix(self) match {
case null => None
case (a, _) => Some(a)
}
}
@annotation.tailrec
def (self: List[A]) foldLeft[A, B](init: B)(fn: (B, A) => B): B =
unfix(self) match {
case null => init
case (a, rest) => rest.foldLeft(fn(init, a))(fn)
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment