Sunday, March 4, 2012

Where we traverse, accumulate and collect in Scala


In a previous post targeting Applicative ramblings, we studied the ability to transform a list of monadic values into a Monadic list of values. In situation when one wishes to convert a list of futures into a future of list, or convert a list of optional values into an optional list of values during a validation process, this ability can become very handy and self explanatory. 
Recently, as watching the wonderful presentation of Rúnar Bjarnason here on functional programming in Scala with Scalaz, I noticed a more generic definition of the sequence function we have early defined. Starting form the usual code project here, from:

we could abstract the concept into the following trait:

where the type constructor C plays the part of a "traversable" structure. This more complete definition provides also a sequence method, but this time, taking benefit from a more generic traverse method. Quoting the McBride and Patterson seminal article on applicative programming with side effects, let say the Traverse trait captures data structures built with the C type constructor through which it can apply applicative computation. 
In essence the traverse method allows us to traverse a C[T] structure and produces a M[C[U]] structure with the help of a f: (T) ⇒ M[U] function. Viewing Applicative Functors as a way to lift functions into the world of Monadic values one can sense that using the traverse function we are going to distribute Monadic applications all over the data structure. 
Doing so, we will be able to convert a structure of possible values to a possible structure of values, same with a structure of Futures, Lists etc. and so on, whatever is the structure I can define as traversable using an ad-hoc definition.
I provided two definitions of traversable. One to reproduce the list example, and a second to play with a tree structure. Concerning the list definition:

As lists belong to a more generic category of traversable structures per se, I freely defined a ListLike trait gathering the basic functions required during the construction of a list. Then I explicitly self referenced this first trait in a second trait TraverseListLike reusing all the basic methods of the first trait. We witness here the real power of the applicative style allowing us to lift all the tool methods into the world of Monadic values keeping the construction of the new monadic structure specifically clear. 
The expression

  cons[U] _ :@:f(value):*:traverse(rest(source))(f) 

nicely reproduces the pattern of construction of a list like structure:  

(cons value (rest))  

in Lisp-ish form. The same procedure can apply to a structure I wanted to play with, the trees:

Both the definition of a Tree (algebraic data type) and of the Traverse object speak for themselves. Here, we still can perceive through the applicative style form  

cons[U] _ :@: f(v) :*: traverse(left)(f) :*: traverse(right)(f)  

the pattern of construction of nodes in a tree 

(cons value left-node right-node)  

Exercising our new toys provides the following:

At that step we have implemented the interface kindly exposed by Rúnar. The traverse function reveals itself to be very powerful. One example of application provided in the McBride and Patterson article proposes to accumulate information while we are traversing the structure. The cumulated value could evolve depending on each of the structure item. An elegant way to do it consists in cumulating values calculable using the add method of a Monoïd given by the type of the values:

Cumulating a value means changing a State while we are traversing the tree, the changing state type being the type of the cumulative value. De facto we think about using the State Monad which we extended to the applicative definition:

I propose you the following implementation for an accumulate function:

The function distributed all over the structure,  

(x: A) ⇒ toAccumulator(x, f, monoid) 

impersonates the f: (T) ⇒ M[U] function as one of the traverse function parameters. 
The toAccumulator function provides a State instance depending both on an input value being the current item in the tree and the Monoïd used for the cumulative effect. The Monoïd cumulate the result of applying f to the current item with any provided external state. 
Traversing the structure means chaining all the cumulated state changes each change depending on a local item value. 

The function f: (T) ⇒ M[U] expects a single parameter type constructor M[_]. So, instead of defining once again a type lambda I defined a local Projection[X] type synonym allowing to dictate to the traverse function the [Projection, A, A] parameters where Projection matches a single parameter type constructor. In exchange the Scala compiler not fooled by my trick demands an explicit specification of the returned type : State[T[A], U]. I'd really love Scala type Gurus to provide me with an explanation concerning this behaviour and another about the fact too that the compiler needs a local definition of the stateApplicative[U]() as the stateApplicative function is already defined implicitly. 

Suppose I want to check some property on any of the element in the tree in a Tree.The input function f: (T) ⇒ U in the accumulate functions becomes a predicate producing a boolean value we cumulate using an OR operation.Wishing to verify if there are some integers greater than 8 in a tree of integers, we provide:

Providing the Any definition as a an logical OR centric Monoid. Both the traversableTree applicative functor and Any Monoid are explicitly provided as the Monoid Any definition is not implicit. We could could cumulate all the values greater than 8:

Here the toListMonoid definition is implicit, so omitted. Building on top of the accumulate function we can reduce (aka crush) all the values in a tree using a Monoïd given by the type of the elements in the tree:

In one of his wondeful posts Debasish Gosh presents Scala variations on the The Essence of the Iterator Pattern article by Jeremy Gibbons and Bruno C. d. S. Oliveira. 
Among all variations, one function called collect, specifically modifies the elements of a data structure purely and independently of the accumulation process. The example provided converts a list of integers into a new list while counting the number elements independently. Here is the implementation of his example:

The implementation, very similar to the accumulate function definition splits in the state definition (f(x), g(s))) both the effect of transforming the tree applying f(x) to a current item, while cumulating a state g(s).

Today we started taking benefit from the Applicative style levering our ability to traverse data structures, cumulating effects, rebuilding our tree, or doing both in just one shot (code project here). 
 I have to go and work on CQRS now. Night's going to be short 

Be seeing you !!! :)


Post a Comment