Small extensions to Scalaz and examples for exploring and teaching the software engineering benefits of defining algebraic data types as initial F-algebras.

This project has been deprecated in favor of the much more complete and mature https://github.com/slamdata/matryoshka.

To use Scalaµ in your project, add these lines to your build.sbt:

resolvers += "laufer@bintray" at "http://dl.bintray.com/laufer/maven"

libraryDependencies += "edu.luc.etl" %% "scalamu" % "0.4.2"

You can also just clone this project and play around with the example worksheets.

Scalaµ works with Scala 2.10 and 2.11 and uses Scalaz 7.2.0.

Natural numbers as the initial algebra for the Option endofunctor.

import scalaz._
import Scalaz._
import scalamu._

type Nat = µ[Option]

val zero = In[Option](None)
val succ = (n: Nat) => In[Option](Some(n))

val two   = succ(succ(zero))
val three = succ(two)

Conversion to Int as a catamorphism.

val toInt: Algebra[Option, Int] = {
  case None    => 0
  case Some(n) => n + 1
}

three cata toInt assert_=== 3

Conversion from Int as an anamorphism.

val fromInt: Coalgebra[Option, Int] = n => {
  require { n >= 0 }
  if   (n == 0) None
  else          Some(n - 1)
}

µ.unfold(7)(fromInt) cata toInt assert_=== 7

Addition as another catamorphism.

val plus: Nat => Algebra[Option, Nat] = m => {
  case None    => m
  case Some(n) => succ(n)
}

two cata plus(three) cata toInt assert_=== 5

Available here.

We recommend starting with this standalone example of arithmetic expressions.

We then recommend looking at the example worksheets in this order:

1. natf
2. natoption
3. natHigherKinded
4. mylist
5. orgchart

To run an example worksheet:

$ sbt test:console
:load examples/natf.sc

Here is a more advanced example of a simple imperative language interpreter implemented using Scalaµ.

TODO

• Understanding F-Algebras
• F-Algebras (Wikipedia)
• Haskell recursion patterns library reference