Having Fun with Monoid in Scalaz Seven

It's been some times since my last blog on Scalaz Seven that talks about Functor. You may have guessed that my second post on the series would be Applicative Functor. Well, sorry, I can't write in order yet, I prefer to talk about Monoid in Scalaz Seven instead. OK Let's have fun.

Having Fun With |+|

To start with, let's have some fun with |+| operator.

Let's start

scala> 6 |+| 7

res0: Int = 13

Well, not that interesting. It's just an addition. What about

scala> 6 + "9"

res2: String = 69

scala> 6 |+| "9"

<console>:14: error: type mismatch;

 found   : java.lang.String("9")

 required: Int

       6 |+| "9"

Not bad. |+| somehow protects you from adding integer to String. OK, not bad, but, not that fun. What about this:


scala> some(6) |+| some(9)
res9: Option[Int] = Some(15)

All right, that starts to be interesting. Give me more:

scala> some(6) |+| some(9) |+| some(10)
res10: Option[Int] = Some(25)


scala> some(6) |+| some(9) |+| some(10) |+| none[Int] |+| some(6)
res11: Option[Int] = Some(31)

Not bad at all. Want something more than that. Some String ?

scala> "Hello" |+| "World"

res25: java.lang.String = HelloWorld

scala> some("Hello") |+| some("World")

res26: java.lang.String = Some(HelloWorld)


What else do you have ? List ?


scala> List(2,4) |+| List(4, 5)
res28: List[Int] = List(2, 4, 4,5)

Cool. Boolean?


scala> val b = true
b: Boolean = true


scala> val c = true
c: Boolean = true


scala> b |+| c
<console>:24: error: value |+| is not a member of Boolean
       b |+| c
         ^

Ouch. Why ? Well, because |+| can be interpreted in conjunction or disjunction (note that, actually this works in Scalaz 6, not sure if scalaz seven will make it work as in scalaz 6). To fix this, let's do the following:


scala> val a = Conjunction(true)
a: scalaz.package.@@[Boolean,scalaz.Tags.Conjunction] = true


scala> val b = Conjunction(true)
b: scalaz.package.@@[Boolean,scalaz.Tags.Conjunction] = true


scala> val c = Conjunction(false)
c: scalaz.package.@@[Boolean,scalaz.Tags.Conjunction] = false


scala> a |+| b
res34: scalaz.package.@@[Boolean,scalaz.Tags.Conjunction] = true


scala> a |+| c
res35: scalaz.package.@@[Boolean,scalaz.Tags.Conjunction] = false


scala> a |+| b |+| c
res36: scalaz.package.@@[Boolean,scalaz.Tags.Conjunction] = false

All right. That makes sense. What about Disjunction ? Well, just do the same.

scala> val e = Disjunction(true)
e: scalaz.package.@@[Boolean,scalaz.Tags.Disjunction] = true


scala> val f = Disjunction(true)
f: scalaz.package.@@[Boolean,scalaz.Tags.Disjunction] = true


scala> val g = Disjunction(false)
g: scalaz.package.@@[Boolean,scalaz.Tags.Disjunction] = false


scala> val h = Disjunction(false)
h: scalaz.package.@@[Boolean,scalaz.Tags.Disjunction] = false


scala> e |+| f
res37: scalaz.package.@@[Boolean,scalaz.Tags.Disjunction] = true


scala> e |+| h
res38: scalaz.package.@@[Boolean,scalaz.Tags.Disjunction] = true


scala> g |+| h
res39: scalaz.package.@@[Boolean,scalaz.Tags.Disjunction] = false

OK. That's cool, but it starts to be boring. Doesn't it? Give me something more spectacular.  What about Tuple?  All right, what about Tuple?

scala> (6, "Hello", List(4, 2)) |+| (7, "Hello", List(5))
res40: (Int, java.lang.String, List[Int]) = (13,HelloHello,List(4, 2, 5))

So, |+| actually "sums" each corresponding element of two tuples. That's quite cool. What if they are nested? Will it work ?

scala> (some(6), some("Hello"), (some(5), some(3))) |+| 
        (some(7), none[String], (some(6), none[Int]))

res43: (Option[Int], Option[java.lang.String], (Option[Int], Option[Int])) = 

(Some(13),Some(Hello),(Some(11), Some(3)))


Fantastic! Pretty cool.

[ I heard somebody there "you see, this Scalaz guy loves using funny operator. This time, they use |+|. OMG, That's not readable". All right, all right. You can actually change all |+| above with its alias called mappend, hope you're happier now].

Monoid and Semigroup Behind the Scene


Behind the scene, what happen is that Scalaz offers a quite simple but powerful abstraction, called Monoid. Believe me, Monoid is something quite simple: it's a type class with two functions: append and zero: 

1     
2      trait Monoid[A] { 
3        val zero: A 
4        def append(s1 : A, s2 : => A):A
5      } 

With the following contract (or a law, if you wish)


zero append x = x
x append zero = x
(x append y) append z = x append (y append z)


Scalaz provides several instances of Monoid (we have seen some of them in action above):

• Int, Short, BigInt, BigDecimal, Byte, Short ...
• Boolean conjunction and disjunction
• List and Stream
• String
• Either.LeftProjection and Either.RightProjection.
• ...

What about Option and Tuple ? Actually, Scalaz also provides some derived Monoid, like:

• Option[A] is a monoid if A is monoid 
• Tuple[A, B, C, D] is a monoid if A, B, C, and D is monoid
• Map [A,B] is a monoid if B is a monoid
• ...

Map is an interesting example. Let's try this:

scala> val m = Map("UO" -> BigDecimal(40.2),

     |              "US" -> BigDecimal(50.1),

     |              "YR" -> BigDecimal(10.1))

scala> val n = Map("UO" -> BigDecimal(10.2),

     |              "US" -> BigDecimal(40.0),

     |              "YZ" -> BigDecimal(10.5))

scala> m |+| n

res47: scala.collection.immutable.Map[java.lang.String,scala.math.BigDecimal] = Map(UO -> 50.4, US -

> 90.1, YZ -> 10.5, YR -> 10.1)

As you can see, |+| adds every corresponding element in m and n. If there's no corresponding element, for example "YR" in m and "YZ" in n, then it just puts the element in the result map.

All examples so far use append function of Monoid, but not zero. A type class with only append is called Semigroup. The function zero is useful when we want to fold a list of monoid, for example using suml function also provided by scalaz:

scala> val xs = List(some(2,4), some(1, 3), some(2, 10))

xs: List[Option[(Int, Int)]] = List(Some((2,4)), Some((1,3)), Some((2,10)))

scala> xs.suml

res48: Option[(Int, Int)] = Some((5,17))

Conclusion
Scalaz provides a cool thing called Semigroup and Monoid. With that, we can benefit the operator |+| and sum for their instances like Integer, String, List, and so on. But the main benefit is that Scalaz provides implementation of Monoid for Option, Tuple, and Map. You don't need to know what Monoid or Semigroup are to benefit all this. But, why should you avoid them ? It's a very simple stuff.

I hope you enjoy this very express introduction to Scalaz Seven Monoid. Who said Scalaz is complex ?
 I'm preparing more on this subject. So, stay tuned.

Scalaz Seven Functor Feels like Seven Samurai

Jason Zaugg and all his scalaz folks are working on scalaz seven at the moment. Although they have started quite a couple of times ago, I only had a chance to play with the library only today.

In case you don't know scalaz, it's actually a popular but often misunderstood library written in scala. It's not haskell standard library ported to scala, but it's highly inspired by the haskell standard library though. I recommend you to have a look here scalaz . One recommendation: take your time, don't be hurry to understand, otherwise you will end up associate scalaz to banana [1], to rabbit [2], or to ejb2 [3]. Of course, scalaz is not ready for production, because you know ... you cannot persist a scalaz object using Hibernate.

I start with one of the simplest scalaz type class, called Functor. It sounds scarry, right ? Don't worry, think of Functor as a way to lift a function that maps A to B to something that map "container" of A to "container" of B. If you have a function that maps, from int to int, say, a functor allows mapping from List of integer to a list of integer by mapping each element of the list.

Say, you have a function incr:

val incr:Int=>Int= x => x + 1

a Functor[List] allows you to map every element in a list using that function like this:

val xs = List(5, 6, 7)

Functor[List].map(xs, incr)   // 6, 7, 8

Well, yeah, is that all? No ! I can also have this:

val eitX:Either[String, Int] = Right(6)

val eitY:Either[String, Int] = Left("Err")

Functor[Either].map(eitX, incr) // Right(7)

Functor[Either].map(eitY, incr) // Left("Err")

It starts to be interesting right, because you don't have map for Either in Scala standard library. Fine, is it great ?  No, it sucks. Function[Either] or Function[List] suck. We don't want it. Fortunately, scalaz comes wi th some magics that simplify the thing

(wait a minute? Scalaz ? Simplifies something? You must be kidding ?)

With the super complex highly intelligent Scalaz (as it is perceived  by many), indeed life is simpler, we can directly write:

val eitX:Either[String, Int] = Right(6)

val eitY:Either[String, Int] = Left("Err")

eitX.map(incr)             // Right(7)
eitY.map(incr)             // Left("Err")

That works, because Either, List, Option are instances of Functor (you know, the container that allows you to lift a function).

Is that all ? No. There are something even more interesting. Imagine if we have a List of Option, is it a functor ? Oh yes, it turns out that the composition of functors is a functor. Let's check:

val listCompOpt = Functor[List].compose(Functor[Option])

val ys = List(Some(1), Some(3), None, Some(6))
val zs = listCompOpt.map(ys)(incr)  // List(Some(2), Some(4), None, Some(7))

Yeah! What about the product ?

val listOptProdF = Functor[List].product(Functor[Option])

val ts = (List(1,2),Some(1))

val us = (List(3,7, 2, 1),None)

listOptProdF.map(ts)(incr)   // (List(2, 3),Some(2))

listOptProdF.map(us)(incr)   // (List(4, 8, 3, 2),None)

Oh, Cool.

OK, to finish this post, scalaz-seven (at least the version I was playing with) provides a couple of interesting functions like strengthL, strengthR, and fpair.

Here they are:

val xEit:Either[String, Int] = Right(3)

val yEit:Either[String, Int] = Right(4)

println(xEit.strengthL("Help"))    // Right("Help",4)

println(yEit.strengthL("Help"))    // Right(("Help",3))

val xOpt:Option[Int] = Some(4)

val yOpt:Option[Int] = None

println(xOpt.strengthR("my godness"))   // Some(4, "my godness") println(yOpt.strengthR("My godness"))  // None

println(xOpt.fpair)     // Some(4,4)
println(xEit.fpair)     // Right(3,3)

I  hope to be able to come with other posts in this series. No promise, but stay tuned.

----------------
[1] Banana in this article context is not a scala or a java library, it is a fruit name. In case you're not familiar with it, check this article. You may wonder how could one wrongly associate scalaz with banana. Well, that may happen, who knows.

[2] Rabbit in this article context is not a scala or a java library, not even a cool javascript library, it is a name of an animal. Again, wikipedia is helpful in case you're not familiar with it. Well, again, it may happen that you associate scalaz to rabbit, who knows.

[3] EJB2 is a server side component, usually managed by the application server. It is used mainly in enterprise application, and by the way the 'E' is Enterprise. You should not wonder why you might associate scalaz to EJB2, it happened !

Semantic Tableaux in Less than 90 Lines of Scala

This week challenge for me was to write a code that can check a propositional logic formula like
(¬(p ⋀ q) ↔ (¬p  ∨ ¬q)) ∧ ( ¬r ∧ q)  and check if the formula is valid or satisfiable. A formula is valid when it is always true under any interpretations of all its atoms. A formula is satisfiable when there is some interpretation of its atoms that can make the proposition true.

The complete code for this post is available here.

Semantic Tableaux
For example, p ⋀ q is satisfiable, since if p and q are both true, then the formula is true. (p  ∨ ¬p)  ⋀ (q ∨ ¬q) is valid, because regardless the interpretation of p and q, the formula is always true.

One way to implement the satisfiability and validity check is by creating truth table. But, the use of truth table is always exponential in number of atoms. There is fortunately a simple technique to check the validity and satisfiability a propositional logic formula. The technique is called Semantic Tableaux. I need to get my logic book I used back to the time of 2nd year of university (Ben-Ari, 1992 ) to remind me how it works. Basically, there are 9 rules, 5 α rules, and 4 β rules.

The following are the 9 rules:

α Rules

α	α1	α2
¬ ¬A	A
A1 ∧ A2	A1	A2
¬(A1 ∨ A2)	¬A1	¬A2
¬(A1 → A2)	A1	¬A2
(A1 ↔ A2)	A1 → A2	A2 → A1

β Rules

β	β1	β2
B1 ∨ B2	B1	B2
¬(B1 ∧ B2)	¬B1	¬B2
B1 → B2	¬B1	B2
¬(B1 ↔ B2)	¬(B1 → B2)	¬(B2 → B1)

I will not explain the Semantic Tableaux algorithms in detail. You can check a more detail in (Ben-Ari ) or in (Issawi, 92). Here is an example of tableau creation for ¬(p ⋀ q) ↔ (¬p  ∨ ¬q) :

Code 
Ok, let's start coding now.  The target is to have the following application working:

object Run { 
    def main(args:Array[String]):Unit = { 
      import Formulas._ 
      val formula1 = (¬('r) ∧ 'q) ∧ (¬('p ∧ 'q) ↔ (¬('p) ∨ ¬('q) )) 
      println(isSatisfiable(formula1) + "," + isValid(formula1)) // true, false 
 
      val formula2 = ¬('p ∧ 'q) ↔ (¬('p) ∨ ¬('q) ) 
      println(isSatisfiable(formula2) + "," + isValid(formula2)) // true, true 
    } 
  }

I used a sealed class Formula to represent all formulas. Atom, Conjunction, Disjunction, Implication, Equivalence, and Xor are classes that extends the trait. In addition, I introduced class  ¬ to represent the negation. Here is how it looks like.

sealed abstract class Formula  
case class Atom(symbol:Symbol) extends Formula 
case class Conjunction(p:Formula, q:Formula) extends Formula 
case class Disjunction(p:Formula, q:Formula) extends Formula 
case class Implication(p:Formula, q:Formula) extends Formula 
case class Equivalence(p:Formula, q:Formula) extends Formula 
case class Xor(p:Formula,q:Formula) extends Formula 
case class ¬(p:Formula) extends Formula

Note that Atom class takes a symbol as its property, so that it allows us to write Atom('p) for example.

I let the Formula class empty in the example above just to make the examples clear. The content of the class is actually the boolean operation to a formula, like ∧,∨, →, ↔, and ⊕. I benefit from Scala that allows special characters to be used as function name. Here is the class Formula looks like:

sealed abstract class Formula { 
  def ∧(q:Formula) = Conjunction(this, q) 
 
  def ∨(q:Formula) = Disjunction(this,q) 
 
  def →(q:Formula) = Implication(this,q) 
 
  def ↔(q:Formula) = Equivalence(this,q) 
 
  def ⊕(q:Formula) = Xor(this, q) 
}

With this, we can write(Atom('p) → Atom('q)) ∨ Atom(r). Not bad, but better to have directly ('p → 'q) ∨ r . For that purpose, implicit comes to rescue:

implicit def symbolToAtom(sym:Symbol) = Atom(sym)

We can now define how the validity and satisfiability work. This code illustrates the example of the application for testing our program:

object Run { 
    def main(args:Array[String]):Unit = { 
      import Formulas._ 
      val formula1 = (¬('r) ∧ 'q) ∧ (¬('p ∧ 'q) ↔ (¬('p) ∨ ¬('q) )) 
      println(isSatisfiable(formula1) + "," + isValid(formula1)) // true, false 
 
      val formula2 = ¬('p ∧ 'q) ↔ (¬('p) ∨ ¬('q) ) 
      println(isSatisfiable(formula2) + "," + isValid(formula2)) // true, true 
    } 
  }

Now let's see the implementation of the 9 rules (you remember 5 α rules, and 4 β rules ?). It's quite simple actually. An application of rule actually retuns a list of leaf, and a leaf is actually a list of formula. Here it is:

  type Leaf = Set[Formula] 
 
  def applyRule(f:Formula):List[Leaf] = 
    f match { 
      case f if isLiteral(f) => List(Set(f)) 
 
      case ¬(¬(a)) => List(Set(a)) 
 
      case Conjunction(a,b) => List(Set(a,b)) 
 
      case ¬(Disjunction(a,b)) => List(Set(¬(a), ¬(b))) 
 
      case ¬(Implication(a,b)) => List(Set(a, ¬(b))) 
 
      case Disjunction(a,b) => List(Set(a), Set(b)) 
 
      case ¬(Conjunction(a,b)) => List(Set(¬(a)), Set(¬(b))) 
 
      case (Implication(a,b)) => List(Set(¬(a)), Set(b)) 
 
      case Equivalence(a,b) => List( Set(a,b) , Set(¬(a), ¬(b))) 
 
      case ¬(Equivalence(a,b)) => List(Set(a,¬(b)),Set(¬(a), b)) 
  }

Nothing should be surprising except the case f if isLiteral(f) => List(Set(f)).  Just disregard this line at the moment, it's only useful in semantic tableau generation. Another surprise maybe for the equivalence rules.  The two equivalence rules in the code above are actually equivalent to the one in the rule table (leave as an exercise :-) ). Note how close the rules definition to its coding implementation. Isn't it nice ?

The most interesting part is of course the implementation of semantic tableau generation. In this naive implementation, the semantic tableau generation is embarrassingly simple, barely 10 lines of codes.

    def semanticTableau(f:Formula):List[Leaf] = { 
 
      def combine(rec:List[Leaf], f:Formula):List[Leaf] = 
               for ( a <- applyRule(f); b <- rec) yield (a ++ b) 
 
      def openLeaf(leaf:Leaf):List[Leaf] = 
        if (leaf forall isLiteral) 
          List(leaf) 
        else 
          leaf.foldLeft(List(Set.empty:Leaf))(combine) flatMap(openLeaf) 
 
      openLeaf(Set(f)) 
    }

Although short, the code is actually very dense. As you can see, the generation of semantic tableau above uses an auxiliary method openLeaf that does exactly that: opening a leaf. Opening a leaf is a recursive function that stops when all formulas in the leaf is a literal. A literal is either an atom or a negation of an atom. The else part is much more complex. But here is the idea: for each formula in a leaf, we apply one of the 9 rules defined above. The result of the application is combined using the combine function above. This will end up with a list of Leaf. For each leaf, then we recursively calls openLeaf using flatMap. This may be unclear, but try to play with the codes, hopefully it'll be clearer.

Finally, we need to implement validity and satisfiability check. A formula is f said to be valid if the semantic tableau for ¬f is closed. A semantic tableau is closed when all its leaves are closed, and finally a leaf is closed when it contains a formula in form of p and ¬p. Here is the implementation:

    def isClosedLeaf(f:Leaf):Boolean = 
      if (f.isEmpty) false 
      else { 
        (f.head match { 
           case Atom(_)    => f.tail.exists( _ == ¬(f.head)) 
           case ¬(Atom(a)) => f.tail.exists( _ == Atom(a)) 
           case _ => false 
         })  || isClosedLeaf(f.tail) 
      } 
 
    def isOpenLeaf(f:Leaf) = !isClosedLeaf(f) 
 
    def isValid(f:Formula):Boolean = semanticTableau(¬(f)) forall isClosedLeaf 
 
    def isSatisfiable(f:Formula):Boolean = semanticTableau(f) exists isOpenLeaf

We're done.

Summary
In this post, I showed my weekend hacking to implement naive satisfiability and validity checking of a propositional formula using semantic tableau. The implementation uses intensively Scala concepts like operator overriding, implicit, and fold and flatMap. All this concepts are helpful to implement the semantic tableaux techniques in relatively short Scala codes (less than 90 lines).  The use of operator helps readibility of the implementation (imagine how it looks like if I didn't use operators ∧,∨, →, ↔, and ⊕).

Reference
Ben-Ari, M (1992) Mathematical Logic for Computer Science. Prentice Hall.

Fix from Fold

My two previous posts, Fold Right from Fold Left and Folding Stream with Scala are actually my interpretation to (Hutton, 1999) paper. Now, I would like to continue with another paper (Pope, 2010 ?) that also talks about fold. Note that, Pope's work cites of  Hutton's work.

This post ends my fold trilogy. It has been an exciting and fun to play with.  I would love to continue with scalaz Fold (Foldr, Foldl, FoldMap Foldable are interesting), but I think I have to stop having fun :-)

Yet Another dropWhile Implementation

In Folding Stream with Scala , I implemented dropWhile using fold using (Hutton, 1999) paper. Pope proposes two more implementations, both work very well with infinite stream.

First, a reminder of fold implementation:

def foldr[A, B](combine:(A, =>B) => B, base:B)(xs:Stream[A]): B = { 
    if (xs.isEmpty) base 
    else combine(xs.head, foldr(combine, base)(xs.tail)) 
  } 

And here is the solution:

  def dwHo[A](pred:A=>Boolean, xs:Stream[A]):Stream[A]=>Stream[A] = { 
    val id =(s:Stream[A])=>s 
    val tail= (s:Stream[A])=>s.tail 
 
    def combine(next:A, rec: =>Stream[A]=>Stream[A]) = { 
     if (pred(next)) (rec compose tail) 
     else id 
    } 
    foldr(combine, id)(xs) 
  }

Example:

  scala> val xs = Stream.range(20, 120) 
  xs: scala.collection.immutable.Stream[Int] = Stream(20, ?) 
  scala> dwHo( (_:Int)<100, xs)(xs).toList 
  res33: List[Int] = List(100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119) 

It also works with infinite Stream:

scala> val ys = Stream.from(1) 
ys: scala.collection.immutable.Stream[Int] = Stream(1, ?) 
scala> dwHo( (_:Int)<5, ys)(ys).take(10).toList 
res38: List[Int] = List(5, 6, 7, 8, 9, 10, 11, 12, 13, 14)

Under the hood, here is what happen:

foldr combine id [1..] 
 =combine 1 (foldr combine id [2..]) = 
 =(foldr combine id [2..]) . tail 
 =(combine 2 (foldr combine id [3..]) . tail 
 =(foldr combine id [3..]) .tail . tail 
 =(combine 3 (foldr combine id [4..]) . tail . tail 
 =(foldr combine id [4..]) .tail . tail . tail 
 =(combine 4 (foldr combine id [5..]) . tail . tail . tail 
 =(foldr combine id [5..]) . tail . tail . tail . tail 
 =(combine 5 (foldr combine id [6..]) . tail . tail . tail 
 =id . tail . tail . tail . tail

And (id.tail.tail.tail.tail)[1..] = [5..].

Fix from Fold
The most interesting part of the (Pope, 2010) is not on dropWhile though, but on an implementation of a function using fold. The function is called fix, also known as Y combinator. Check this page to have an idea of what fix function is.

Basically, using fix, we can encode recursion function. The following is an example of factorial function using fix in haskell:

Prelude> :m Control.Monad.Fix 
Prelude Control.Monad.Fix> fix (\rec n -> if n == 0 then 1 else n * rec (n-1)) 5  

120
In Scala, fix function is implemented in a much trickier way. The difficulties come from the Scala strictness. Here is the implementation of fix I found after googling a little bit:

def fix[A](f: (A=>A)=>(A=>A)): A=>A = f(fix(f))(_)

Example:
scala> fix[Long](f=>x=> if (x == 0) 1 else x * f(x - 1))(5)

res5: Long = 120

One question that may arise is whether fold can be implemented using fix. Well, apparently, yes, after all, it's a recursion, but I haven't tried it yet. A more interesting question would be if fix can be implemented using fold. The answer is yes, and that's the essence of (Pope, 2010) article. Here is the implementation of fix using foldr in Scala:

def fix[A](f: (A=>A)=>(A=>A)): A=>A = { 
  def combine( a:(A=>A)=>(A=>A), b: =>A=>A):A=>A = f(b)(_) 
  foldr(combine, null)(Stream.continually(null)) 
}

Give a try:

scala> fix[Long](f=>x=> if (x == 0) 1 else x * f(x - 1))(5) 
res6: Long = 120

Youpi..., isn't it awesome? This shows how expressive fold is, since it can now be used to implement (any?) recursion functions.

References

• Hutton G (1999) A tutorial on the universality and expressiveness of fold. Available from http://www.cs.nott.ac.uk/~gmh/fold.pdf 

• Pope B (2010 ?)  Getting a Fix from the Right Fold. Available from: http://www.haskell.org/wikiupload/1/14/TMR-Issue6.pdf . There is one other dropWhile solution in this paper that I dumped here: https://gist.github.com/1195982.

Fold Again: Fold Left using Fold Right

In my previous post, I have shown how fold can be used to implement other collection methods, like filter, map, length, reverse, or even dropWhile and break.

We wonder now whether it is possible to implement fold left using fold right. The article (Hutton, 1999) shows indeed that it is possible. The objective of this post is then to show it in Scala and discuss a little bit about fold universality.

Before implementing fold left using fold right, let's implement something simpler. Let's implement suml, a function that is similar to sum we discussed in the previous post. Instead of summing from right to left, we want suml to sum from left to right.

The following illustrates the difference between sum and suml:

   1 sum(Stream(1, 2, 3, 4))= 1 + (2 + (3 + 4))
   2 suml(Stream(1, 2, 3, 4))= (((1 + 2) + 3) + 4)
   3 

As described in (Hutton, 1999), it turns out that we can't directly implement suml using fold. What possible is to define suml_ that returns a function Int=> Int. Here is the implementation:

   1 def suml_(xs:Stream[Int]) = {
   2     def combine(x:Int, g: =>Int=>Int) = (acc:Int)=>g(acc +x)
   3     foldr(combine, (x:Int)=>x)(xs)
   4 }
   5 def sum(xs:Stream[Int])=suml_(xs)(0)

When suml_(Stream(1, 3, 4, 5)) is called, it returns actually

((_:Int) + 5) compose ((_:Int) + 4) 

compose ((_:Int) + 3) compose ((_:Int)+ 1) 

compose ( (x:Int)=>x)

Note that, the returned function is actually an Int=>Int function, and when it receives 0 as its input, it returns (((1 + 3) + 4) + 5) = 13. Also note a special function, the identity function (x:Int)=>x.

OK, Great. What about foldl? Well, it is the generalization of suml above. Here is the foldl implementation:

   1 def foldl_[A,B](f: (A,B)=>B, xs:Stream[A]) = {
   2    def combine(x: A, g: =>B=>B) = (acc:B)=> g(f(x,acc)) 
   3    foldr(combine, (a:B)=>a)(xs)
   4 }
   5 def foldl[A,B](f:(A,B)=>B, base:B, xs:Stream[A]) = foldl_(f,xs)(base)
   6 

Let's give a shot:

   1 scala> foldl( (_:Int) + (_:Int), 0, Stream(1, 3, 4, 5))
   2 res1: Int = 13
   3 
   4 scala> foldl( (_:Int) * (_:Int), 1, Stream(1, 3, 4, 5))
   5 res2: Int = 60

Excellent. But, all this looks like a magic, right? Is there a systematic way to derive a implementation of a function using fold? Fortunately, yes. Here we come to the most interesting part of (Hutton, 1999).

Fold Universality and  Fusion Property of Fold

Two  important concepts explained in (Hutton, 1999) is fold universality and fusion property of fold.

The fold universality states that the two Scala code below are equivalent:
Code 1

   1 def g[A,B](xs: Stream[A], f:(A, B)=>B, v:B): B = 
   2   if (xs.isEmpty) v else 
   3   f(xs.head, g(xs.tail, f, v))

Code 2

   1 def g[A,B](xs:Stream[A], f:(A,B)=>B, v:B) = foldr(f,v)(xs)
   2 

Or more concise, in haskell symbols:

   1 g[]     = v
   2                       <=>   g = fold f v
   3 g(x:xs) = f x (g xs)    

And the fusion property of fold states the following:

1 h w = v
2                          => h . fold g w = fold f v
3 h(g x y) = f x (h y)

Let's have examples.

First, let's see how universal property of fold is useful to derive an implementation of a function using fold.

We will start with the recursive definition of foldl:

1 foldl     [] f v  = v
2 foldl (x:xs) f v  = foldl xs f (f v x) 

In scala:

1 def foldl[A,B](xs:Stream[A], f:(B,A)=>B, v:B): B = {
2    if (xs.isEmpty) v
3    else foldl(xs.tail, f, f(v, xs.head))
4 }

Unfortunately, foldl does not match directly with universal property definition. We need then an auxiliary method foldl_ :

1 def foldl_[A,B](xs:Stream[A]) = foldl[A,B](xs:Stream[A], (_:(B,A)=>B), (_:B))

That is, foldl function without the last two parameters.

We're ready to use universal property now:
foldl_ [] = v
foldl_ (x:xs) = f x (foldl_ xs)

Here, v is the identity function =id.

{Functions}
foldl_ (x:xs) g a = f x (foldl_ xs) g a
<=>
{Definition of foldl}
foldl_ xs g (g a x) = f x (foldl_ xs) g a
<=>
{Generalizing foldl_ xs = h}
h g (g a x) = f x h g a
<=>
f = (λx h -> (λa -> h(g a x)))

So, we got:
foldl xs f v = foldr((λx h -> (λa -> h(g a x)))) id xs v

When translated to Scala, we obtain the code explained at the beginning of the post.

***

Now, go for fusion property. Recall our map definition defined in the previous post (I modified a little bit):

   1 def map[A,B](f1:A=>B) = {
   2    def combine(x:A, xs:Stream[B]) = f1(x) #:: xs
   3    foldr(combine, Stream.empty)
   4 }

Note that the combine function can be represented as λx xs->f1 x : xs .

We would like to (a little bit informally) prove that map(f1) compose map(f2) =  map(f1 compose f2).
From the equation, we can substitute:
h = map(f1)
g = λx xs->f2(x):xs
w = v = Stream.empty = []
f = f1 compose f2

But,
map(f1) [] = []
map(f1) (g(x,xs)) = map(f1) ( f2(x):xs )
                  = (f1 compose f2)(x):map(f1)(xs)

So, the equation map(f1) compose map(f2) =  map(f1 compose f2)indeed holds.

Folding Stream with Scala

Introduction
Couple of weeks ago, I read a well known paper on expressiveness of fold (Hutton, 1999). The paper is a very interesting paper that explains how fold is a very powerful construct.

The codes in the paper are written in Haskell and therefore assumes laziness. This means that the execution of function in Haskell is delayed until it is really needed. This is not the case for Scala, where the operation is executed eagerly, or in other word, it's strict instead of lazy.

Stream is the implementation of lazy list in Scala. Using Stream, the elements are only evaluated when they are needed. So, we may expect that Stream is close to Haskell's list.

The use of scala Stream and fold right are the topic of this post.

Fold Right
Let's back to fold. The paper I mentioned above (Hutton, 1999) showed how expressive fold construct, especially foldRight. The objective of this post is to show the same things as the paper, but in Scala.

Let's see the problem we may encounter. The following Haskell code works:

   1 Prelude> foldr (||) False (repeat True)
   2 True

But not the following Scala code:

   1 Stream.continually(true).foldRight(false)(_ || _)

because the code above throws StackOverflowError.

The reason of the error is because Stream.foldRight is not actually lazy. When I read the article and wondered how the non-laziness of Stream.foldRight could be solved, I received Tony Morris' tweet telling that scalaz fixes the non-laziness. The following is the reimplementation of lazy foldRight for Stream inspired by Foldr scalaz implementation:

1 
2 def foldr[A, B]( combine: (A, =>B) => B, base: B )(xs: Stream[A]): B = {
3    if (xs.isEmpty) 
4      base
5    else 
6      combine(xs.head,  foldr(combine, base)(xs.tail))
7 }

The following code works without StackOverflowError:

   1 def combine(x: Boolean, y: =>Boolean) = x || y
   2 foldr(combine, false)(Stream.continually(true))  

The key of the foldr implementation above is in thetype definition of combine parameter: (A, =>B) instead of (A,B). This makes the second parameter evaluated lazily.

Some Fold Right Uses
The following shows some familiar functions implemented using foldr.

   1 def sum(xs: Stream[Int]) = {
   2     def combine(x: Int, y: =>Int) = x + y
   3     foldr(combine, 0)(xs)
   4 }
   5 def product(xs: Stream[Int]) = {
   6     def combine(x: Int, y: =>Int) = x * y
   7     foldr(combine, 1)(xs)
   8 }
   9 def and(xs: Stream[Boolean]) = {
  10    def combine(x: Boolean, y: =>Boolean) = x && y
  11    foldr(combine, true)(xs)  
  12 }
  13 def or(xs: Stream[Boolean]) = {
  14    def combine(x: Boolean, y: =>Boolean) = x || y
  15    foldr(combine, false)(xs)  
  16 }

Using Fold Right to Implement Scala Collection Functions
As in (Hutton, 1999), the following section shows how Fold Right can be used to implement some functions. At the first time, let's see length, filter, reverse, flatten, and map implementations.

   1 def map[A,B](f:A=>B, xs:Stream[A]) = {
   2    def combine(x:A, xs: =>Stream[B]) = f(x)  #:: xs
   3    val base:Stream[B] = Stream.empty
   4    foldr(combine, base)(xs)
   5 }
   6 def length[A](xs: Stream[A]) = {
   7     def combine(x: A, len: =>Int) = len + 1
   8     foldr(combine, 0)(xs)
   9 }
  10 def reverse[A](xs: Stream[A]) = {
  11     def combine(x: A, xs: =>Stream[A]) = Stream.concat(xs, Stream(x))
  12     val base:Stream[A] = Stream.empty
  13     foldr(combine, base)(xs)
  14 }
  15 def filter[A](p:A=>Boolean, xs: Stream[A]) = {
  16    def combine(x: A, xs: =>Stream[A]) = if (p(x)) x #:: xs else xs 
  17    foldr(combine , Stream.empty)(xs)
  18 }
  19 def filterNot[A](p:A=>Boolean, xs: Stream[A]) = {
  20    def combine(x: A, xs: =>Stream[A]) = if (p(x)) xs else x #:: xs 
  21    val base:Stream[A] = Stream.empty  
  22    foldr(combine, base)(xs)
  23 }
  24 def flatten[A](xss: Stream[Stream[A]]) = {
  25    def combine(xs: Stream[A], ys: =>Stream[A]) = xs #::: ys
  26    val base: Stream[A] = Stream.empty
  27    foldr(combine, base)(xss)
  28 }
  29 def partition[A](p:A=>Boolean, xs:Stream[A]) = {
  30    (filter(p, xs), filterNot(p, xs))
  31 }
  32 

Note that, the functions like flatten, filter, and map, work with infinite Streams. See the following examples:

   1 scala> map( (_:Int)+1, Stream.from(1))
   2 res2: Stream[Int] = Stream(2, ?)
   3 
   4 scala> res2.take(4).toList
   5 res3: List[Int] = List(2, 3, 4, 5)
   6 
   7 scala> filter( (_:Int) % 2 ==0, Stream.from(10)).take(5).toList
   8 res5: List[Int] = List(10, 12, 14, 16, 18)
   9 
  10 scala> partition( (_:Int) % 2 == 0, Stream.from(20))
  11 res6: (scala.collection.immutable.Stream[Int], Stream[Int]) = (Stream(20, ?),Stream(21, ?))
  12 
  13 scala>  flatten(Stream.continually(Stream(1, 3, 4))).take(10).toList
  14 res13: List[Int] = List(1, 3, 4, 1, 3, 4, 1, 3, 4, 1)

Implementing dropWhile and break
One of the most interesting part of (Hutton, 1999) is the dropWhile implementation using foldr. The implementation is shown in the following code:

   1 def dropWhile[A](pred: A => Boolean, xs: Stream[A])= {
   2    def combine(x: A, xs: =>(Stream[A], Stream[A])) = 
   3       if (pred(x)) 
   4          (xs._1, x #:: xs._2) 
   5       else 
   6          (x #:: xs._2, x #:: xs._2)
   7    val base:(Stream[A], Stream[A]) = (Stream.empty, Stream.empty)
   8    foldr(combine, base)(xs) _1
   9 }

Instead of directly producing the result, a tuple of Streams is returned. The first Stream is the result and the second one is used for bookkeeping purpose.
The following illustrates an execution of dropWhile:

   1 dropWhile( (_:Int)<5, Stream(1,2,7,3,4,5,6,7,8,9,10)) 
   2 10 => ( (10), (10))
   3 9  => ( (9,10), (9,10))
   4 8  => ( (8,9,10), (8,9,10))
   5 7  => ( (7,8,9,10), (7,8,9,10))
   6 6  => ( (6,7,8,9,10), (6,7,8,9,10))
   7 5  => ( (5,6,7,8,9,10), (5,6,7,8,9,10))
   8 4  => ( (5,6,7,8,9,10), (4,5,6,7,8,9,10))
   9 3  => ( (5,6,7,8,9,10), (3,4,5,6,7,8,9,10))
  10 7  => ( (7, 3,4,5,6,7,8,9,10), (7,3,4,5,6,7,8,9,10))
  11 2  => ( (7, 3,4,5,6,7,8,9,10), (2, 7,3,4,5,6,7,8,9,10))
  12 1  => ( (7, 3,4,5,6,7,8,9,10), (1, 2, 7,3,4,5,6,7,8,9,10)) 

What surprising is that the solution actually works for infinite Stream too as illustrated in the following code:

   1 scala> dropWhile( (_:Int)<5, Stream.from(1)).take(10).toList
   2 res17: List[Int] = List(5, 6, 7, 8, 9, 10, 11, 12, 13, 14)

The last interesting function implemented here is break. The  equivalent of Haskell's break in Scala collection is called span (Update, Oct 24 thanks to oxbow). The break function creates a tuple of two lists separated at condition boundary. Example:

   1 scala> val (a,b) = break( (_:Int)<5, Stream.from(1))
   2 a: Stream[Int] = Stream(1, ?)
   3 b: Stream[Int] = Stream(5, ?)
   4 
   5 scala> a.toList
   6 res22: List[Int] = List(1, 2, 3, 4)
   7 
   8 scala> b.take(5).toList
   9 res23: List[Int] = List(5, 6, 7, 8, 9)
  10 

The implementation of break here, of course, highly inspired from dropWhile one:

   1 def break[A](pred: A=>Boolean, xs: Stream[A]) = {
   2    def combine(x: A, xs: =>(Stream[A], Stream[A], Stream[A])) =
   3       if (pred(x)) 
   4         (xs._1, x #:: xs._2, x #:: xs._3)             
   5       else
   6         (x #:: xs._3, Stream.empty, x #:: xs._3) 
   7              
   8    val base:(Stream[A], Stream[A], Stream[A]) = (Stream.empty, Stream.empty, Stream.empty)
   9    
  10    val result = foldr(combine, base)(xs) 
  11    (result._2, result._1)
  12 }

Summary 
In this blog post, I showed the result of playing around with Stream and fold right. First, I rewrote the implementation of foldRight, showed the use of foldRight, expressed some collection functions using foldRight, and finally provided dropWhile and break.

The blog post does not have intention to overcome the non-laziness of Scala language. Scala is not a lazy language, and I think it's not appropriate to use lazy evaluation as the main stream of the codes.

Pope (Pope, 2010 ?) in Monad Reader 6 discussed further the implementation of dropWhile. He presented two further solutions based on higher order function composition. He also presented the fold implementation using what is so called fix function. See http://en.wikibooks.org/wiki/Haskell/Fix_and_recursion to have an idea of what Fix function is.

References 

• Hutton G (1999) A tutorial on the universality and expressiveness of fold. Available from http://www.cs.nott.ac.uk/~gmh/fold.pdf 

• Pope B (2010 ?)  Getting a Fix from the Right Fold. Available from: http://www.haskell.org/wikiupload/1/14/TMR-Issue6.pdf