# 用 Scala 3 实现 Jaskell Parsec

Scala 3（项目名 Dotty）在 2020年底发布了 3.0.0-M3 。我从 M1 开始着手升级 Jaskell ，目前已经成功的在 M3 上实现了 Jaskell Parsec 库。

## 基础算子实现

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)

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))
}
}

package jaskell
import scala.util.{Try, Success, Failure}

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)

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

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

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

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
}
}

package sisp.parsers

import sisp.ast.{Element, Expression}

import scala.util.Try

class ExprParser extends Parsec[Char, Any]{
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
}

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)
}

}

## Type Classes 的其它场景

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 {
}
}
}

package sisp.ast

import scala.util.Try

class ListExpr extends Lambda {
}
Try 是 Scala 标准库的内置类型，它如此重要，所以我在尝试更为通用的 flip 实现，未来的版本，可能会允许任意的 Monad[Try[T]] 直接翻转为 Try[Monad[T]] 。