Functional double fold pattern

Question

Let a Counter toy class, such as:

 class Counter private( val next: Int, val str2int: Map[String,Int] ) { def apply( str: String ): (Int,Counter) = str2int get str match { case Some(i) => ( i, this ) case None => ( next, new Counter( next+1, str2int + (str -> next) ) ) } } object Counter { def apply() = new Counter( 0, Map() ) } 

This class provides a mapping between a string and a natural number, the display is incremented lazily every time a new line is requested.

Then I can write a method that can convert Seq strings to Seq of Ints, updating the display during the crawl. The first implementation I got is foldLeft :

 def toInt( strs: Seq[String], counter: Counter ): ( Seq[Int], Counter ) = strs.foldLeft( (Seq[Int](), counter) ) { (result, str) => val (i, nextCounter) = result._2( str ) ( result._1 :+ i, nextCounter ) } 

This works as intended:

 val ss = Seq( "foo", "bar", "baz", "foo", "baz" ) val is = toInt( ss, Counter() )._1 //is == List(0, 1, 2, 0, 2) 

But I'm not very happy with the implementation of toInt . The problem is that I add up two different values. Is there a functional programming pattern to simplify implementation?

Answer 1

The sample you are looking for is the State monad:

 import scalaz._ import Scalaz._ case class Counter(next: Int = 0, str2int: Map[String,Int] = Map()) { def apply( str: String ): (Counter, Int) = (str2int get str) fold ( (this, _), (new Counter(next+1, str2int + (str -> next)), next) )} type CounterState[A] = State[Counter, A] def count(s: String): CounterState[Int] = state(_(s)) def toInt(strs: Seq[String]): CounterState[Seq[Int]] = strs.traverse[CounterState, Int](count) 

Type annotations are unsuccessful, and perhaps they can be somehow eliminated. Anyway, run it here:

 scala> val ss = Seq( "foo", "bar", "baz", "foo", "baz" ) ss: Seq[java.lang.String] = List(foo, bar, baz, foo, baz) scala> val is = toInt(ss) ! Counter() is: Seq[Int] = List(0, 1, 2, 0, 2) 

Answer 2

You can make a fold that you like by doing more pattern matching:

 strs.foldLeft((Seq[Int](), counter)) { case ((xs,counter), str) => val (i, nextCounter) = counter(str) (xs :+ i, nextCounter) } 

And then, if you have a statement operator |> , which is defined for you, and you are comfortable with the alias /: for foldLeft , you can do this

 ((Seq[Int](), counter) /: strs) { case ((xs,counter), str) => counter(str) |> { case (i,nextCounter) => (xs +: i, nextCounter) } } 

which, once you are familiar with the syntax, are compact and readable.

Answer 3

I think the state monad is what you are looking for.

Answer 4

Nothing wrong with folding on two values. It can be improved a bit:

 import scalaz._ import Scalaz._ def toInt( strs: Seq[String], counter: Counter ): ( Seq[Int], Counter ) = strs.foldLeft( (Seq[Int](), counter) ) { case ((xs, counter), str) => counter(str).mapElements(xs :+ _, identity) } 

Or if you want

 def toInt( strs: Seq[String], counter: Counter ): ( Seq[Int], Counter ) = strs.foldLeft( (Seq[Int](), counter) ) { case ((xs, counter), str) => (xs :+ (_: Int)) <-: counter(str) } 

Or even,

 def toInt( strs: Seq[String], counter: Counter ): ( Seq[Int], Counter ) = strs.foldLeft( (Seq[Int](), counter) ) { case (result, str) => result.fold((xs, counter) => counter(str).mapElements(xs :+ _, identity)) }