Last active
April 5, 2020 00:04
-
-
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.
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
// 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 | |
*/ | |
} |
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
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