Free Algebra in Scala with Java Visitor Pattern

trait FreeConsoleOperation[A] {
def toReader: Reader[Unit, A]
}

//boiler plates

object FreeConsoleOperation {

case object ReadLine extends FreeConsoleOperation[String] {
override def toReader: Reader[Unit, String] = Reader(_ => scala.io.StdIn.readLine())
}

case class PrintLine(string: String) extends FreeConsoleOperation[Unit] {
override def toReader: Reader[Unit, Unit] = Reader(_ => println(string))
}

def readLine[A]: Free[FreeConsoleOperation, String] =
Suspend(ReadLine)

def printLine[A](s: String): Free[FreeConsoleOperation, Unit] =
Suspend(PrintLine(s))

val f: Free[FreeConsoleOperation, String] = for {
_ <- printLine("I interact with only console")
s <- readLine
} yield s

val translator = new (FreeConsoleOperation ~> Reader[Unit, ?]) {
def apply[A](a: FreeConsoleOperation[A]): Reader[Unit, A] = a.toReader
}

// Scalaz already has a monad instance for Reader, however, our free monad runner expect an instance for our in-house monad
implicit def readerMonad: Monad[Reader[Unit, ?]] = Reader.readerMonad[Unit]

def reader: Reader[Unit, String] = FreeMonad.runFree[FreeConsoleOperation, Reader[Unit, ?], String](f)(translator)

// reader.run("Bob") and you test your flow f nicely without any side effect. This is a rather simple
// way of saying that the tranlsated F should be pure like a Reader Monad that removes the side effect.
// The actual side effect may be handled out side. Something like, scalaz.IO(readLine()).map( reader.run) etc.
}
object FreeConsoleOperationWithVisitor { module =>
trait ScalazConsoleVisitor[A] {
def visit[F[_]](visitor: ScalazConsoleVisitor.Visitor[F]): F[A]
}

type ScalazConsoleVisistorFree[A] = Free[ScalazConsoleVisitor, A]

object ScalazConsoleVisitor {

trait Visitor[F[_]] extends (ScalazConsoleVisitor ~> F) {
def apply[A](fa: ScalazConsoleVisitor[A]): F[A] = fa.visit(this)

def readLine: F[String]

def printLine(string: String): F[Unit]

}

case object ReadLine extends ScalazConsoleVisitor[String] {
def visit[F[_]](visitor: FreeConsoleOperationWithVisitor.ScalazConsoleVisitor.Visitor[F]): F[String] = visitor.readLine
}

case class PrintLine(s: String) extends ScalazConsoleVisitor[Unit] {
def visit[F[_]](visitor: FreeConsoleOperationWithVisitor.ScalazConsoleVisitor.Visitor[F]): F[Unit] = visitor.printLine(s)
}
}

import ScalazConsoleVisitor._

val unit: ScalazConsoleVisistorFree[Unit] = Return[ScalazConsoleVisitor, Unit](())
def printLine(s: String): ScalazConsoleVisistorFree[Unit] = Suspend(PrintLine(s))
def readLine: ScalazConsoleVisistorFree[String] = Suspend(ScalazConsoleVisitor.ReadLine)

val f: Free[ScalazConsoleVisitor, String] = for {
_ <- printLine("I interact with only console")
s <- readLine
} yield s

// Scalaz already has a monad instance for Reader, however, our free monad runner expect an instance for our in-house monad
implicit def readerMonad: Monad[Reader[Unit, ?]] = Reader.readerMonad[Unit]

def reader: Reader[Unit, String] = FreeMonad.runFree[ScalazConsoleVisitor, Reader[Unit, ?], String](f)(
new Visitor[Reader[Unit, ?]] {
def readLine: Reader[Unit, String] = Reader(_ => scala.io.StdIn.readLine())
def printLine(string: String): Reader[Unit, Unit] = Reader(_ => print(string))
})
}

Let’s explain​

A use case where we use pattern matching is a free monad algebra where operations are encoded as data, and u generally have an interpreter that matches on each data and corresponding logic is written then and there itself. Potentially they (should) return a result under the effect F.

trait Visitor[F[_]] extends (ScalazConsoleVisitor ~> F) {
def apply[A](fa: ScalazConsoleVisitor[A]): F[A] =
fa.visit(this)
....

Subtype polymorphic dispatch and pattern matching

The above pattern boils down to selecting subtype polymorphic dispatch which requires one off vtable reference over pattern match which is encoded as a big if else statement in byte code that can question performance. More on this coming soon.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Afsal Thaj

Afsal Thaj

A software engineer and a functional programming enthusiast at Simple-machines, Sydney, and a hardcore hiking fan. https://twitter.com/afsalt2