Skip to content

Instantly share code, notes, and snippets.

@prayagupa
Forked from ehoner/unparsers.scala
Created October 12, 2018 03:49
Show Gist options
  • Save prayagupa/121d9a38be6c0cdeef58eaff01a0cc06 to your computer and use it in GitHub Desktop.
Save prayagupa/121d9a38be6c0cdeef58eaff01a0cc06 to your computer and use it in GitHub Desktop.
WIP: This is a translation of the examples in haskell to scala through section 4.2.
// script can be loaded by ammonite (http://ammonite.io/)
import $plugin.$ivy.`org.spire-math::kind-projector:0.9.6`
import $ivy.`org.scalaz::scalaz-core:7.2.25`
import scalaz._
import Scalaz._
import scalaz.Maybe.Just
import scala.language.higherKinds
final case class Iso[A, B](fa: A => Maybe[B], fb: B => Maybe[A]) {
def inverse: Iso[B, A] = Iso(fb, fa)
def apply: A => Maybe[B] = fa
def unapply: B => Maybe[A] = inverse.apply
}
// This is a recursive type definition for list, unlike the scala.collection.List
// type List = Nil | Cons a (List a)
//
// A recursive type for scala would like below
// sealed trait List[A]
// final case class Cons[A](a: A, list: List[A]) extends List[A]
// final case object Nil extends List[Nothing]
def nil[A]: Iso[Unit, List[A]] = {
val fb: List[A] => Maybe[Unit] = {
case Nil => Just(())
case _ => Maybe.empty
}
Iso(_ => Just(List.empty), fb)
}
def cons[A]: Iso[(A, List[A]), List[A]] = {
val fa = (tuple: (A, List[A])) => Just(tuple._1 +: tuple._2)
val fb: List[A] => Maybe[(A, List[A])] = {
case Nil => Maybe.empty
case head :: tail => Just((head, tail))
}
Iso(fa, fb)
}
implicit val categoryForIso: Category[Iso] = new Category[Iso] {
override def id[A]: Iso[A, A] = Iso(Just[A], Just[A])
override def compose[A, B, C](f: Iso[B, C], g: Iso[A, B]): Iso[A, C] =
Iso(g.apply(_).flatMap(f.apply), f.unapply(_).flatMap(g.unapply))
}
/**
* Provided some Isomorphism,
*/
trait IsoFunctor[F[_]] {
def map[A, B](iso: Iso[A, B])(fa: F[A]): F[B]
}
// sec: 3.2 uncurried application (Apply.tuple2) without Apply.ap
trait ProductFunctor[F[_]] {
def product[A, B](fa: F[A], fb: F[B]): F[(A, B)]
}
/**
* @note: [[Applicative]] extends [[Applicative]] with a different type signature
*/
// Alternative extends ApplicativePlus
trait Syntax[F[_]] extends IsoFunctor[F] with ProductFunctor[F] with PlusEmpty[F] {
def pure[A](a: A)(implicit eq: Equal[A]): F[A]
def token: F[Char]
}
object Syntax {
def apply[F[_]](implicit ev: Syntax[F]): Syntax[F] = ev
}
// unified definition of parsing and printing
def many[F[_], A](f: F[A])(implicit S: Syntax[F], equal: Equal[A]): F[List[A]] = {
val empty: F[Unit] = S.pure(())
val nonEmpty: F[(A, List[A])] = S.product(f, many(f))
val first: F[List[A]] = S.map(nil[A])(empty)
val second: F[List[A]] = S.map(cons[A])(nonEmpty)
S.plus(first, second)
}
// condensed
def many0[F[_], A](f: F[A])(implicit S: Syntax[F], equal: Equal[A]): F[List[A]] =
S.plus(S.map(nil[A])(S.pure(())), S.map(cons[A])(S.product(f, many(f))))
/** section 4 */
final case class Parser[A](parse: String => List[(A, String)])
object Parser {
// Elements are defined individually for clarity purposes.
implicit val isoFunctor: IsoFunctor[Parser] = new IsoFunctor[Parser] {
override def map[A, B](iso: Iso[A, B])(fa: Parser[A]): Parser[B] = {
def parse(s: String): List[(B, String)] = for {
(a, s0) <- fa.parse(s)
b <- iso.apply(a).toOption
} yield (b, s0)
Parser(parse)
}
}
implicit val productFunctor: ProductFunctor[Parser] = new ProductFunctor[Parser] {
override def product[A, B](fa: Parser[A], fb: Parser[B]): Parser[(A, B)] = {
def parse(s: String): List[((A, B), String)] = for {
(x, s0) <- fa.parse(s)
(y, s1) <- fb.parse(s0)
} yield ((x, y), s1)
Parser(parse)
}
}
implicit val plusEmpty: PlusEmpty[Parser] = new PlusEmpty[Parser] {
override def empty[A]: Parser[A] = Parser(_ => List.empty)
override def plus[A](a: Parser[A], b: => Parser[A]): Parser[A] = {
def parse(s: String): List[(A, String)] = a.parse(s) ++ b.parse(s)
Parser(parse)
}
}
implicit val syntax: Syntax[Parser] = new Syntax[Parser] {
override def map[A, B](iso: Iso[A, B])(fa: Parser[A]): Parser[B] =
isoFunctor.map(iso)(fa)
override def product[A, B](fa: Parser[A], fb: Parser[B]): Parser[(A, B)] =
productFunctor.product(fa, fb)
override def empty[A]: Parser[A] = plusEmpty.empty
override def plus[A](a: Parser[A], b: => Parser[A]): Parser[A] =
plusEmpty.plus(a, b)
override def pure[A](a: A)(implicit eq: Equal[A]): Parser[A] = {
def parse(s: String): List[(A, String)] = List((a, s))
Parser(parse)
}
override def token: Parser[Char] = {
def parse(s: String): List[(Char, String)] =
if (s != null && s.nonEmpty) List((s.head, s.tail)) else List.empty
Parser(parse)
}
}
}
// <|> allows for speciyfing subsets of a constructor implementation rather than all at once
final case class Printer[A](print: A => Maybe[String])
object Printer {
implicit val isoFunctor: IsoFunctor[Printer] = new IsoFunctor[Printer] {
override def map[A, B](iso: Iso[A, B])(fa: Printer[A]): Printer[B] = {
def print(b: B): Maybe[String] = iso.unapply(b).flatMap(fa.print)
Printer(print)
}
}
implicit val productFunctor: ProductFunctor[Printer] = new ProductFunctor[Printer] {
override def product[A, B](fa: Printer[A], fb: Printer[B]): Printer[(A, B)] = {
def print(a: A, b: B): Maybe[String] = fa.print(a) <+> fb.print(b)
Printer((print _).tupled)
}
}
implicit val plusEmpty: PlusEmpty[Printer] = new PlusEmpty[Printer] {
override def empty[A]: Printer[A] = Printer(_ => Maybe.empty)
override def plus[A](a: Printer[A], b: => Printer[A]): Printer[A] = {
def print(in: A): Maybe[String] = a.print(in) <+> b.print(in)
Printer(print)
}
}
implicit val syntax: Syntax[Printer] = new Syntax[Printer] {
override def map[A, B](iso: Iso[A, B])(fa: Printer[A]): Printer[B] =
isoFunctor.map(iso)(fa)
override def product[A, B](fa: Printer[A], fb: Printer[B]): Printer[(A, B)] =
productFunctor.product(fa, fb)
override def empty[A]: Printer[A] = plusEmpty.empty
override def plus[A](a: Printer[A], b: => Printer[A]): Printer[A] =
plusEmpty.plus(a, b)
override def pure[A](a: A)(implicit eq: Equal[A]): Printer[A] = {
def print(a0: A): Maybe[String] = if (a0 === a) "".just else Maybe.empty
Printer(print)
}
override def token: Printer[Char] = Printer(_.toString.just)
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment