build.sbt

scalaVersion := "3.1.2-RC1"

MatchTypeParseEval.scala

import scala.compiletime.ops.string.{+, Substring, Length}
import scala.compiletime.ops.int

sealed trait HList {
  def :+:[T](t: T): T :+: this.type = new :+:(t, this)
}
final case class :+:[H, +T <: HList](h: H, t: T) extends HList
sealed trait HNil extends HList
case object HNil extends HNil

sealed trait Token
sealed trait NumValue[A <: Int] extends Token with Num
sealed trait Add extends Token
sealed trait Mul extends Token
sealed trait Space extends Token
sealed trait Start extends Token
sealed trait End extends Token

sealed trait Expr
sealed trait Num extends Expr
sealed trait NumAdd[A1 <: Num, A2 <: Num] extends Num
sealed trait NumMul[A1 <: Num, A2 <: Num] extends Num

@annotation.experimental
object MatchTypeParseEval {

  // https://zenn.dev/lotz/articles/85577e9d9059cd9e1245
  // https://en.wikipedia.org/wiki/Shunting-yard_algorithm
  type ShuntingYard[In <: HList] =
    ShuntingYard0[HNil, HNil, In]

  type ShuntingYard0[Out <: HList, Op <: HList, In <: HList] <: HList =
    (Op, In) match
      case (HNil, HNil) =>
        ReverseHList[Out]
      case (sym :+: op, HNil) =>
        ShuntingYard0[sym :+: Out, op, HNil]
      case (Mul :+: op, Add :+: in) =>
        ShuntingYard0[Mul :+: Out, op, Add :+: in]
      case (Add :+: op, Add :+: in) =>
        ShuntingYard0[Add :+: Out, op, Add :+: in]
      case (_, Mul :+: in) =>
        ShuntingYard0[Out, Mul :+: Op, in]
      case (_, Add :+: in) =>
        ShuntingYard0[Out, Add :+: Op, in]
      case (_, Start :+: in) =>
        ShuntingYard0[Out, Start :+: Op, in]
      case (Start :+: op, End :+: in) =>
        ShuntingYard0[Out, op, in]
      case (sym :+: op, End :+: in) =>
        ShuntingYard0[sym :+: Out, op, End :+: in]
      case (_, sym :+: in) =>
        ShuntingYard0[sym :+: Out, Op, in]


  // https://en.wikipedia.org/wiki/Reverse_Polish_notation
  type RPN[Symbols <: HList] =
    RPN0[HNil, Symbols]

  type RPN0[Stack <: HList, Symbols <: HList] =
    (Stack, Symbols) match
      case (x :+: HNil, HNil) =>
        x
      case (x1 :+: x2 :+: xs, Add :+: ys) =>
        RPN0[NumAdd[x1, x2] :+: xs, ys]
      case (x1 :+: x2 :+: xs, Mul :+: ys) =>
        RPN0[NumMul[x1, x2] :+: xs, ys]
      case (x, y :+: ys) =>
        RPN0[y :+: x, ys]

  type ReverseHList[A <: HList] =
    ReverseHList0[HNil, A]

  type ReverseHList0[Acc <: HList, Src <: HList] <: HList=
    Src match
      case HNil =>
        Acc
      case x :+: xs =>
        ReverseHList0[x :+: Acc, xs]

  type ReverseStr[A <: String] =
    ReverseLoop["", A]

  type ReverseLoop[Acc <: String, Src <: String] <: String =
    Length[Src] match
      case 0 =>
        Acc
      case _ =>
        ReverseLoop[Substring[Src, 0, 1] + Acc, Substring[Src, 1, Length[Src]]]

  type StringToHList[A <: String] =
    StringToHList0[HNil, ReverseStr[A]]

  type StringToHList0[+Acc <: HList, Src <: String] <: HList =
    Length[Src] match
      case 0 =>
        Acc
      case _ =>
        StringToHList0[Substring[Src, 0, 1] :+: Acc, Substring[Src, 1, Length[Src]]]

  type StrToToken[A <: String] =
    A match {
      case "0" => NumValue[0]
      case "1" => NumValue[1]
      case "2" => NumValue[2]
      case "3" => NumValue[3]
      case "4" => NumValue[4]
      case "5" => NumValue[5]
      case "6" => NumValue[6]
      case "7" => NumValue[7]
      case "8" => NumValue[8]
      case "9" => NumValue[9]
      case "+" => Add
      case "*" => Mul
      case "(" => Start
      case ")" => End
      case " " => Space
    }

  type HListToTokens[A <: HList] <: HList =
    A match {
      case x :+: xs =>
        StrToToken[x] :+: HListToTokens[xs]
      case HNil =>
        HNil
    }

  type RemoveSpace[A <: HList] <: HList =
    A match {
      case Space :+: xs =>
        RemoveSpace[xs]
      case x :+: xs =>
        x :+: RemoveSpace[xs]
      case HNil =>
        HNil
    }

  type Eval[A <: Expr] <: Int =
    A match {
      case NumValue[a] => a
      case NumAdd[a1, a2] => int.+[Eval[a1], Eval[a2]]
      case NumMul[a1, a2] => int.*[Eval[a1], Eval[a2]]
    }

  type Run[A <: String] =
    A match {
      case _ =>
        Eval[AST[A]]
    }

  type AST[A <: String] =
    A match {
      case _ =>
        RPN[
          ShuntingYard[
            RemoveSpace[
              HListToTokens[
                StringToHList[A]
              ]
            ]
          ]
        ]
    }

  summon[ReverseStr["abc"] =:= "cba"]

  summon[StringToHList["123"] =:= ("1" :+: "2" :+: "3" :+: HNil)]

  summon[
    AST[
      "1 + 2 * (3 + 4)"
    ] =:= NumAdd[
      NumMul[
        NumAdd[
          NumValue[4],
          NumValue[3]
        ],
        NumValue[2]
      ],
      NumValue[1]
    ]
  ]

  summon[Run["1 + 2 * (3 + 4)"] =:= 15]

  summon[Run["1 + (2 + 3 * 4) * (5 + 6) + 7 + 8 * 9 + 5"] =:= 239]

  summon[
    RPN[
      NumValue[3] :+:
      NumValue[1] :+:
      Add :+:
      NumValue[5] :+:
      Mul :+:
      HNil
    ] =:= NumMul[
      NumValue[5],
      NumAdd[
        NumValue[1],
        NumValue[3],
      ],
    ]
  ]

  summon[
    ShuntingYard[
      9 :+:
      Mul :+:
      Start :+:
      1 :+:
      Add :+:
      2 :+:
      End :+:
      HNil
    ] =:= (
      9 :+:
      1 :+:
      2 :+:
      Add :+:
      Mul :+:
      HNil
    )
  ]

  summon[
    ReverseHList[
      1 :+: 2 :+: 3 :+: 4 :+: HNil
    ] =:= (
      4 :+: 3 :+: 2 :+: 1 :+: HNil
    )
  ]
}