在Scala貓中遞歸算術表達式的自由單子組

Question

我想使用Scala cats庫和以下tutorial doc來定義一個簡單的算術表達式求值程序。

目標是以模塊化的方式定義DSL，可以單獨定義整數值和附加值。

我有以下代碼：

package examples 
import cats._ 
import cats.data._ 
import cats.free._ 
import cats.free.Free._ 
import scala.language.higherKinds 

object FreeExpr { 

    sealed trait ValueF[A] 
    case class IntValue(n: Int) extends ValueF[Int] 

    class Value[F[_]](implicit I: Inject[ValueF, F]) { 
    def intVal(n:Int): Free[F,Int] = inject[ValueF,F](IntValue(n)) 
    } 

    object Value { 
    implicit def value[F[_]](implicit I: Inject[ValueF,F]): Value[F] = new Value[F] 
    } 

    sealed trait ArithF[A] 
    case class Add[A](x: A, y: A) extends ArithF[A] 

    class Arith[F[_]](implicit I: Inject[ArithF, F]) { 
    def add[A](x: A, y: A) : Free[F,A] = 
    Free.inject[ArithF,F](Add(x,y)) 
    } 

    object Arith { 
    implicit def arith[F[_]](implicit I: Inject[ArithF,F]): Arith[F] = new Arith[F] 
    } 

    type Expr[A] = Coproduct[ArithF, ValueF, A] 
    type Result[A] = Id[A] 

    object ArithId extends (ArithF ~> Result) { 
    def apply[A](fa: ArithF[A]) = fa match { 
     case Add(x,y) => ??? // for { m <- x; n <- y } yield (m + n) 
    } 
    } 

    object ValueId extends (ValueF ~> Result) { 
    def apply[A](fa: ValueF[A]) = fa match { 
     case IntValue(n) => Monad[Id].pure(n) 
    } 
    } 

    val interpreter: Expr ~> Result = ArithId or ValueId 

    def expr1(implicit value : Value[Expr], 
        arith : Arith[Expr]): Free[Expr, Int] = { 
    import value._, arith._ 
    for { 
     n <- intVal(2) 
     m <- add(n, n) 
    } yield m 
    } 

    lazy val run1 = expr1.foldMap(interpreter) 

} 

前面的代碼編譯，因爲我評論的「應用」爲添加的情況下的定義。我最初以爲的解決方案是被註釋掉的代碼，但是編譯器回報：

[error] ...FreeExpr.scala:40: value flatMap is not a member of type parameter A 
[error]  case Add(x,y) => for { m <- x; n <- y } yield (m + n) 
[error]         ^

你知道什麼纔是我需要的代碼改變來定義一個模塊化的方式DSL和解釋？

Answer 1

的問題，就是Add結果類型太籠統，在case Add(x,y) => ...值x和y有型A，而不是M[A]。

我發現了兩種可能的解決方案。

一種是改變的Add定義爲case class Add(x:Int,y:Int)和解釋的定義是

object ArithId extends (ArithF ~> Result) { 
    def apply[A](fa: ArithF[A]) = fa match { 
     case Add(x,y) => x + y 
    } 
} 

我加入這個解決了這一要點：之前的解決方案的FreeExprInt.scala

的一個問題是結果類型固定爲Int，它可能更有趣，至少可以是Semigroup。

我試圖使用case class Add[A: Semigroup](x: A, y: A)來定義它，但似乎編譯器有一些問題來處理第二個隱式參數列表。

可能的解決方法是明確添加證據。我將這個解決方案添加到另一個要點：FreeExprExplicit.scala

儘管這兩種解決方案都有效，但我不太滿意，因爲我更喜歡更通用的解決方案，其結果類型可以是任何A。

我被建議看看無標記的最終樣式（Alternatives to GADTs），但我還沒有實現它。