用 Scala 3 实现 Jaskell Parsec
这是一个非常棒的升级，Scala 3提供了完整的 Typeclass 能力。借助 Type Lambda、Typeclass Trait 、Given 和 Extension，我们终于可以比较规范的建立组合子体系。
基础算子实现
现在，我们终于不需要将bind、then这些基础的函数式编程概念都绑定在 Parsec 定义中。现在，我参考 dotty 实现了 Functor -> Applicative -> Monad 定义。
在现代的 Haskell 中， Functor、Applicative、Monad 是顺序继承的。首先我们实现 Functor：
package jaskell
import scala.util.{Failure, Success, Try}
trait Functor[F[_]]:
def pure[A](x: A): F[A]
extension[A, B] (x: F[A])
/** The unit value for a monad */
def map(f: A => B): F[B]
def flatMap(f: A => F[B]): F[B]
given Functor[List] with
def pure[A](x: A) = List(x)
extension[A, B] (xs: List[A])
def map(f: A => B): List[B] =
xs.map(f) // List already has a `map` method
def flatMap(f: A => List[B]): List[B] = xs.flatMap(f)
这里的版本跟 dotty 官方那篇 typeclasses 教程里的实现不太一样，这是因为 flatMap 本身是一个极其重要的方法，Scala 的 for 语法直接依赖 flatMap 和 map。如果照搬 Haskell 的设计，在 Monad 中实现 flatMap（以及bind和do），那么 Scala 语法级别的 for yield 表达式就会显得很奇怪，而我还需要在 Applicative 实现中大量使用它。所以，我将 flatMap 和 map 放到了 Functor 中。
然后我们实现 Applicative：
package jaskell
import scala.util.{Try, Success}
trait Applicative[F[_]] extends Functor[F] {
extension[A, B] (fa: F[A => B])
def (fb: F[A]): F[B] = for {
f <- fa
a <- fb
} yield f(a)
def (fb: F[A => B]): F[A => B] =
for {
a <- fa
b try {
a(arg)
} catch {
_ => b(arg)
}
extension[A, B] (x: F[A])
def *>(bx: F[B]) = for {
_ <- x
b <- bx
} yield b
def <*(bx: F[B]) = for {
a <- x
_ C])
def liftA2(ax: F[A], bx: F[B]): F[C] = for {
f <- fx
a <- ax
b > Arg => Try[Result]] with {
def pure[T](arg: T): Arg => Try[T] = x => Success(arg)
extension[A, B] (fa: Arg => Try[A]) {
def map(f: A => B): Arg => Try[B] = arg => fa(arg).map(f)
def flatMap(fb: A => Arg => Try[B]): Arg => Try[B] = arg => fa(arg).flatMap(x => fb(x)(arg))
}
extension[A] (fa: Arg => Try[A]) {
def (fb: Arg => Try[A]): Arg => Try[A] = arg => fa(arg).orElse(fb(arg))
}
}
在 Parsec 实现中，经常要用到Applicative提供的运算符。它们可以极大的简化这些有条件约束的模式匹配和推导逻辑。
然后是 Monad 实现，很大程度上这个实现是一种“形式上的美感”，Scala 将Monad的功能已经糅合在语言和标准库中，我们可能并不会直观的体会到这个实现的作用：
package jaskell
import scala.util.{Try, Success, Failure}
trait Monad[F[_]] extends Applicative[F]:
extension [A, B](x: F[A])
def >>= (f: A=> F[B]): F[B] = {
x.flatMap(f)
}
/** The `map` operation can now be defined in terms of `flatMap` */
def map(f: A => B): F[B] = x.flatMap(f.andThen(pure))
def >> (f: A => B): F[B] = map(f)
given listMonad: Monad[List] with
def pure[A](x: A): List[A] =
List(x)
extension [A, B](xs: List[A])
def flatMap(f: A => List[B]): List[B] =
xs.flatMap(f) // rely on the existing `flatMap` method of `List`
given optionMonad: Monad[Option] with
def pure[A](x: A): Option[A] = Option(x)
extension [A, B](xo: Option[A])
def flatMap(f: A => Option[B]): Option[B] = xo match
case Some(x) => f(x)
case None => None
given tryMonad: Monad[Try] with
def pure[A](x: A) = Success(x)
extension [A, B](xt: Try[A])
def flatMap(f: A => Try[B]): Try[B] = xt.flatMap(f)
Given 语法可以为我们提供特定约束条件下的实现，例如我们可以通过 given ，为 Parsec 算子引入 Monad typeclasses 。
Parsec 实现
package jaskell.parsec
import scala.util.{Try, Success, Failure}
import scala.language.implicitConversions
import jaskell.Monad
trait Parsec[A, B] {
def apply(state: State[A]): Try[B]
def ?(state: State[A]): Try[B] = this.apply(state)
def !(state: State[A]): B = this.apply(state).get
def attempt: Parsec[A, B] = new Attempt(this)
def iterate(state: State[A]): Iterator[A, B] = new Iterator(this, state)
def (p: Parsec[A, B]): Parsec[A, B] = new Combine2(this, p)
}
given parsecConfig[E]: Monad[[T] =>> Parsec[E, T]] with {
def pure[A](x: A): Parsec[E, A] = new Pack[E, A](x)
extension [A, B](x: Parsec[E, A]) {
def flatMap(f: A => Parsec[E, B]): Parsec[E, B] = new Binder(x, f)
}
}
given textParserConfig[T]: Monad[[T] =>> Parsec[Char, T]] with {
def pure[A](x: A): Parsec[Char, A] = new Pack[Char, A](x)
extension [A, B](x: Parsec[Char, A]) {
def flatMap(f: A => Parsec[Char, B]): Parsec[Char, B] = new Binder(x, f)
}
extension [A](x: Parsec[Char, A]) {
def apply(content: String): Try[A] = x.apply(content.state)
def ?(content: String): Try[A] = x ? content.state
}
}
而 extension 可以在不修改原有类型的前提下，提供额外的行为和功能。在这里，我们可以将 Parsec 实现为一个特定的Monad，为其提供特有的 flatMap 实现，这样，我们就可以像在 Haskell 中一样，方便的利用 “，`>>=`运算符组合算子。
需要注意的是，Haskell中的实现方式于此不同，Haskell Parsec 库利用 Haskell 语言的 Curry 能力，自动拥有了强大的组合能力，如果要在 Scala 3中模拟，应该将 state 实现为一个 using 参数。要不要这么做，我还在思考和学习。
一旦有了正确的基础类型，组合子的使用就更加便利，例如 between 匹配，现在可以实现为：
package sisp.parsers
import jaskell.parsec.Atom.pack
import jaskell.parsec.Combinator.{between, sepBy1}
import jaskell.parsec.Txt.{ch, skipWhiteSpaces}
import jaskell.parsec.{Parsec, SkipWhitespaces, State}
import sisp.ast.{Element, Expression}
import scala.util.Try
class ExprParser extends Parsec[Char, Any]{
import jaskell.parsec.parsecConfig
val skip: SkipWhitespaces = skipWhiteSpaces
val elementParser = new Parser
val left = ch('(') *> skip
val right = skip *> ch(')')
lazy val parser =
left *> sepBy1(elementParser, skip) >=
{vals => pack(new Expression(vals))}
override def apply(s: State[Char]): Try[Element] = parser ? s
}
上例是 SISP Dotty 项目的 S 表达式算子，它将括号包围的代码（即LISP程序员熟知的 S 表达式形式）解释为一个表达式对象。这里我们充分利用了 Applicative 和 Bind 带来的便利。
我曾经想在 Scala 2 中实现类似的 Monad 定义，但是 Scala 2 的typeclass 仅支持一个类型参数，并且需要一组眼花缭乱的复杂技巧来实现，于是我很快放弃了。在 Scala 3 实现中，我同样遇到了类型参数的问题，Monad/Applicative/Fucntor定义强调的是对某一个目标类型的封装，而 Parsec 算子是一个一元函数，它需要有输入类型和输出类型两个类型参数。但是实际上我们仔细思考，会发现我们仅仅需要在输出类型上定义 Monad，输入类型在 Parsec 算子定义时已经确定，我们需要的是将输入和输出类型分离为两步单类型参数的定义。这时就需要利用 Scala 3 的 type lambda ：
given parsecConfig[E]: Monad[[T] =>> Parsec[E, T]] with {
def pure[A](x: A): Parsec[E, A] = new Pack[E, A](x)
extension [A, B](x: Parsec[E, A]) {
def flatMap(f: A => Parsec[E, B]): Parsec[E, B] = new Binder(x, f)
}
}
通过一个带类型参数的 given 实例， 我们将 Parsec 约束为一个单类型参数的 Monad 。这里我们仅需定义 flatMap 和 pure ，就可以令其自动拥有基础算子的各种功能。
Type Classes 的其它场景
当然，我们还可以利用这个功能做很多工作，例如在 JISP/SISP 实现中，我们需要将 `Seq[Try[T]]` 翻转为对应的 `Try[Seq[T]]` 。现在，我们可以直接给 Seq 类型一个 given 实例：
trait SeqU {}
given seqU: SeqU with {
extension[T] (seq: Seq[Try[T]])
def sequenceU: Try[Seq[T]] = {
val failure = seq.filter(_.isFailure)
if(failure.isEmpty){
return Success(seq.map(_.get))
} else {
return Failure(failure.head.failed.get)
}
}
}
在用到这个功能的地方，引入该实例，就可以将 sequenceU 作为对象方法使用：
package sisp.ast
import scala.util.Try
class ListExpr extends Lambda {
import jaskell.seqU
override def apply(env: Env, params: Seq[Any]): Try[Any] = {
(params map env.eval).sequenceU map {values => new Quote(new Expression(values))}
}
}
其实 sequenceU 这个名字，来自 cats 库中的同名方法。我写下这篇文章的时候，也感觉这个名字太长了点。所以在最新版的 jaskell dotty 中，这个方法改叫 flip 了。
Haskell 的 flip 有不同的含义，它用来交换二元函数的顺序。这个能力对于广泛使用中缀表达式和 Curry 的 Haskell 很有用，Scala 就不同，它更平凡，老老实实的用 lambda 就好了。
Try 是 Scala 标准库的内置类型，它如此重要，所以我在尝试更为通用的 flip 实现，未来的版本，可能会允许任意的 `Monad[Try[T]]` 直接翻转为 `Try[Monad[T]]` 。
About The Author
