Skip to content

Instantly share code, notes, and snippets.

@johnynek
Last active April 5, 2020 00:04
Show Gist options
  • Save johnynek/de9816f26f2c54c4f33a5890ed0bfab9 to your computer and use it in GitHub Desktop.
Save johnynek/de9816f26f2c54c4f33a5890ed0bfab9 to your computer and use it in GitHub Desktop.
a dotty implementation of safe get using match types. This was done on 0.23.0-RC1. The first implementation, when the list is itself an opaque type, does not compile, the second, where List is the standard list, does compile.
// 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 OList[A] = Fix[[X] =>> OrNull[(A, X)]]
object OList {
def empty[A]: OList[A] = fix(null)
extension {
def [A](head: A) :: (self: OList[A]): OList[A] =
fix((head, self))
@annotation.tailrec
def [A, B] (self: OList[A]).foldLeft(init: B)(fn: (B, A) => B): B =
unfix(self) match {
case null => init
case (headA, tail) => tail.foldLeft(fn(init, headA))(fn)
}
def [A, B] (self: OList[A]).map(fn: A => B): OList[B] =
unfix(self) match {
case null => OList.empty
case (headA, tail) => fn(headA) :: tail.map(fn)
}
@annotation.tailrec
def [A] (self: OList[A]).get(n: Int): Option[A] =
unfix(self) match {
case null => None
case (head, tail) =>
if (n <= 0) Some(head)
else tail.get(n - 1)
}
}
}
object LtType {
import scala.compiletime.S
type Lt[N <: Int] <: Int =
N match {
case 0 => Nothing
case 1 => 0
case S[n] => n | Lt[n]
}
opaque type SList[n <: Int, A] = OList[A]
def empty[A]: SList[0, A] = OList.empty[A]
extension {
def [N <: Int, A](head: A) :: (self: SList[N, A]): SList[S[N], A] =
head :: (self: OList[A])
def [N <: Int, A](self: SList[N, A]).apply(n: Lt[N]): A =
(self: OList[A]).get(n: Int).get
}
val list3: SList[3, Int] = 1 :: 2 :: 3 :: empty
val one = list3(0: Lt[3])
/* line 72 fails with:
[error] -- [E007] Type Mismatch Error: /home/oscarboykin/oss/dotty-example-project/src/main/scala/OList.scala:72:18
[error] 72 | val one = list3(0: Lt[3])
[error] | ^^^^^^^^
[error] | Found: (2 : Int) | ((1 : Int) | LtType.Lt[(1 : Int)])
[error] | Required: LtType.Lt[N]
[error] |
[error] | where: N is a type variable with constraint <: Int
[error] one error found
[error] (Compile / compileIncremental) Compilation failed
[error] Total time: 1 s, completed Apr 4, 2020 1:57:13 PM
*/
}
object LtType {
import scala.compiletime.S
type Lt[N <: Int] <: Int =
N match {
case 0 => Nothing
case 1 => 0
case S[n] => n | Lt[n]
}
opaque type SList[n <: Int, A] = List[A]
def empty[A]: SList[0, A] = List.empty[A]
extension {
def [N <: Int, A](head: A) :: (self: SList[N, A]): SList[S[N], A] =
head :: (self: List[A])
def [N <: Int, A](self: SList[N, A]).apply(n: Lt[N]): A =
(self: List[A])(n: Int)
}
val list3: SList[3, Int] = 1 :: 2 :: 3 :: empty
val one = list3(0: Lt[3])
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment