# learning Scalaz: day 12

in

Hey there. There's an updated html5 book version, if you want. reynaldo f. tamayo for openphoto.net

On day 11 we looked at Lens as a way of abstracting access to nested immutable data structure.

Today, let's skim some papers. First is Origami programming by Jeremy Gibbons.

### Origami programming

Gibbons says:

In this chapter we will look at folds and unfolds as abstractions. In a precise technical sense, folds and unfolds are the natural patterns of computation over recursive datatypes; unfolds generate data structures and folds consume them.

We've covered `foldLeft` in day 4 using `Foldable`, but what's unfold?

The dual of folding is unfolding. The Haskell standard List library deﬁnes the function `unfoldr` for generating lists.

Hoogle lists the following sample:

```Prelude Data.List> unfoldr (\b -> if b == 0 then Nothing else Just (b, b-1)) 10
[10,9,8,7,6,5,4,3,2,1]```

### DList

There's a data structure called `DList` that supports `DList.unfoldr`. `DList`, or difference list, is a data structure that supports constant-time appending.

```scala> DList.unfoldr(10, { (x: Int) => if (x == 0) none else (x, x - 1).some })
res50: scalaz.DList[Int] = scalaz.DListFunctions\$\$anon\$3@70627153

scala> res50.toList
res51: List[Int] = List(10, 9, 8, 7, 6, 5, 4, 3, 2, 1)```

### Folds for Streams

In Scalaz `unfold` defined in `StreamFunctions` is introduced by `import Scalaz._`:

```scala> unfold(10) { (x) => if (x == 0) none else (x, x - 1).some }
res36: Stream[Int] = Stream(10, ?)

scala> res36.toList
res37: List[Int] = List(10, 9, 8, 7, 6, 5, 4, 3, 2, 1)```

Let's try implementing the selection sort example from the paper:

```scala> def minimumS[A: Order](stream: Stream[A]) = stream match {
case x #:: xs => xs.foldLeft(x) {_ min _}
}
minimumS: [A](stream: Stream[A])(implicit evidence\$1: scalaz.Order[A])A

scala> def deleteS[A: Equal](y: A, stream: Stream[A]): Stream[A] = (y, stream) match {
case (_, Stream()) => Stream()
case (y, x #:: xs) =>
if (y === x) xs
else x #:: deleteS(y, xs)
}
deleteS: [A](y: A, stream: Stream[A])(implicit evidence\$1: scalaz.Equal[A])Stream[A]

scala> def delmin[A: Order](stream: Stream[A]): Option[(A, Stream[A])] = stream match {
case Stream() => none
case xs =>
val y = minimumS(xs)
(y, deleteS(y, xs)).some
}
delmin: [A](stream: Stream[A])(implicit evidence\$1: scalaz.Order[A])Option[(A, Stream[A])]

scala> def ssort[A: Order](stream: Stream[A]): Stream[A] = unfold(stream){delmin[A]}
ssort: [A](stream: Stream[A])(implicit evidence\$1: scalaz.Order[A])Stream[A]

scala> ssort(Stream(1, 3, 4, 2)).toList
res55: List[Int] = List(1, 2, 3, 4)```

I guess this is considered origami programming because are using `foldLeft` and `unfold`? This paper was written in 2003 as a chapter in The Fun of Programming, but I am not sure if origami programming caught on.

### The Essence of the Iterator Pattern

In 2006 the same author wrote The Essence of the Iterator Pattern. Linked is the revised 2009 version. This paper discusses applicative style by breaking down the GoF Iterator pattern into two aspects: mapping and accumulating.

The first half of the paper reviews functional iterations and applicative style. For applicative functors, it brings up the fact that there are three kinds of applicatives:
2. Naperian applicative functors
3. Monoidal applicative functors

We've brought up the fact that all monads are applicatives many times. Naperian applicative functor zips together data structure that are fixed in shape. Also apparently appliactive functors were originally named idiom, so idiomatic in this paper means applicative.

### Monoidal applicatives

Scalaz implements `Monoid[m].applicative` to turn any monoids into an applicative.

```scala> Monoid[Int].applicative.ap2(1, 1)(0)
res99: Int = 2

scala> Monoid[List[Int]].applicative.ap2(List(1), List(1))(Nil)
res100: List[Int] = List(1, 1)```

### Combining applicative functors

EIP:

Like monads, applicative functors are closed under products; so two independent idiomatic
effects can generally be fused into one, their product.

In Scalaz, `product` is implemented under `Applicative` typeclass:

```trait Applicative[F[_]] extends Apply[F] with Pointed[F] { self =>
...
/**The product of Applicatives `F` and `G`, `[x](F[x], G[x]])`, is an Applicative */
def product[G[_]](implicit G0: Applicative[G]): Applicative[({type λ[α] = (F[α], G[α])})#λ] = new ProductApplicative[F, G] {
implicit def F = self
implicit def G = G0
}
...
}```

Let's make a product of `List` and `Option`.

```scala> Applicative[List].product[Option]
res0: scalaz.Applicative[[α](List[α], Option[α])] = scalaz.Applicative\$\$anon\$2@211b3c6a

scala> Applicative[List].product[Option].point(1)
res1: (List[Int], Option[Int]) = (List(1),Some(1))```

The product seems to be implemented as a `Tuple2`. Let's use Applicative style to append them:

```scala> ((List(1), 1.some) |@| (List(1), 1.some)) {_ |+| _}
res2: (List[Int], Option[Int]) = (List(1, 1),Some(2))

scala> ((List(1), 1.success[String]) |@| (List(1), "boom".failure[Int])) {_ |+| _}
res6: (List[Int], scalaz.Validation[String,Int]) = (List(1, 1),Failure(boom))```

EIP:

Unlike monads in general, applicative functors are also closed under composition; so
two sequentially-dependent idiomatic effects can generally be fused into one, their composition.

This is called `compose` under `Applicative`:

```trait Applicative[F[_]] extends Apply[F] with Pointed[F] { self =>
...
/**The composition of Applicatives `F` and `G`, `[x]F[G[x]]`, is an Applicative */
def compose[G[_]](implicit G0: Applicative[G]): Applicative[({type λ[α] = F[G[α]]})#λ] = new CompositionApplicative[F, G] {
implicit def F = self
implicit def G = G0
}
...
}```

Let's compose `List` and `Option`.

```scala> Applicative[List].compose[Option]
res7: scalaz.Applicative[[α]List[Option[α]]] = scalaz.Applicative\$\$anon\$1@461800f1

scala> Applicative[List].compose[Option].point(1)
res8: List[Option[Int]] = List(Some(1))```

EIP:

The two operators `⊗` and `⊙` allow us to combine idiomatic computations in two different ways; we call them parallel and sequential composition, respectively.

The fact that we can compose applicatives and it remain applicative is neat. I am guessing that this characteristics enables modularity later in this paper.

### Idiomatic traversal

EIP:

Traversal involves iterating over the elements of a data structure, in the style of a `map`, but interpreting certain function applications idiomatically.

The corresponding typeclass in Scalaz 7 is called `Traverse`:

```trait Traverse[F[_]] extends Functor[F] with Foldable[F] { self =>
def traverseImpl[G[_]:Applicative,A,B](fa: F[A])(f: A => G[B]): G[F[B]]
}```

This introduces `traverse` operator:

```trait TraverseOps[F[_],A] extends Ops[F[A]] {
final def traverse[G[_], B](f: A => G[B])(implicit G: Applicative[G]): G[F[B]] =
G.traverse(self)(f)
...
}```

Here's how we can use it for `List`:

```scala> List(1, 2, 3) traverse { x => (x > 0) option (x + 1) }
res14: Option[List[Int]] = Some(List(2, 3, 4))

scala> List(1, 2, 0) traverse { x => (x > 0) option (x + 1) }
res15: Option[List[Int]] = None```

The `option` operator is injected to `Boolean`, which expands `(x > 0) option (x + 1)` to `if (x > 0) Some(x + 1) else None`.

EIP:

In the case of a monadic applicative functor, traversal specialises to monadic map, and has the same uses.

It does have have similar feel to `flatMap`, except now the passed in function returns `G[B]` where `[G: Applicative]` instead of requiring `List`.

EIP:

For a monoidal applicative functor, traversal accumulates values. The function reduce performs that accumulation, given an argument that assigns a value to each element.

```scala> Monoid[Int].applicative.traverse(List(1, 2, 3)) {_ + 1}
res73: Int = 9```

I wasn't able to write this as `traverse` operator.

### Shape and contents

EIP:

In addition to being parametrically polymorphic in the collection elements, the generic traverse operation is parametrised along two further dimensions: the datatype being traversed, and the applicative functor in which the traversal is interpreted. Specialising the latter to lists as a monoid yields a generic contents operation.

```scala> def contents[F[_]: Traverse, A](f: F[A]): List[A] =
Monoid[List[A]].applicative.traverse(f) {List(_)}
contents: [F[_], A](f: F[A])(implicit evidence\$1: scalaz.Traverse[F])List[A]

scala> contents(List(1, 2, 3))
res87: List[Int] = List(1, 2, 3)

scala> contents(NonEmptyList(1, 2, 3))
res88: List[Int] = List(1, 2, 3)

scala> val tree: Tree[Char] = 'P'.node('O'.leaf, 'L'.leaf)
tree: scalaz.Tree[Char] = <tree>

scala> contents(tree)
res90: List[Char] = List(P, O, L)```

Now we can take any data structure that supports `Traverse` and turn it into a `List`. We can also write `contents` as follows:

```scala> def contents[F[_]: Traverse, A](f: F[A]): List[A] =
f.traverse[({type l[X]=List[A]})#l, A] {List(_)}
contents: [F[_], A](f: F[A])(implicit evidence\$1: scalaz.Traverse[F])List[A]```

The other half of the decomposition is obtained simply by a map, which is to say, a traversal interpreted in the identity idiom.

The "identity idiom" is the `Id` monad in Scalaz.

```scala> def shape[F[_]: Traverse, A](f: F[A]): F[Unit] =
f traverse {_ => ((): Id[Unit])}
shape: [F[_], A](f: F[A])(implicit evidence\$1: scalaz.Traverse[F])F[Unit]

scala> shape(List(1, 2, 3))
res95: List[Unit] = List((), (), ())

scala> shape(tree).drawTree
res98: String =
"()
|
()+-
|
()`-
"```

EIP:

This pair of traversals nicely illustrates the two aspects of iterations that we are focussing on, namely mapping and accumulation.

Let's also implement `decompose` function:

```scala> def decompose[F[_]: Traverse, A](f: F[A]) = (shape(f), contents(f))
decompose: [F[_], A](f: F[A])(implicit evidence\$1: scalaz.Traverse[F])(F[Unit], List[A])

scala> decompose(tree)
res110: (scalaz.Tree[Unit], List[Char]) = (<tree>,List(P, O, L))```

This works, but it's looping the tree structure twice. Remember a product of two applicatives are also an applicative?

```scala> def decompose[F[_]: Traverse, A](f: F[A]) =
Applicative[Id].product[({type l[X]=List[A]})#l].traverse(f) { x => (((): Id[Unit]), List(x)) }
decompose: [F[_], A](f: F[A])(implicit evidence\$1: scalaz.Traverse[F])(scalaz.Scalaz.Id[F[Unit]], List[A])

scala> decompose(List(1, 2, 3, 4))
res135: (scalaz.Scalaz.Id[List[Unit]], List[Int]) = (List((), (), (), ()),List(1, 2, 3, 4))

scala> decompose(tree)
res136: (scalaz.Scalaz.Id[scalaz.Tree[Unit]], List[Char]) = (<tree>,List(P, O, L))```

Since the above implementation relys on type annotation to get the monoidal applicative functor, I can't write it as nice as the Haskell example:

`decompose = traverse (shapeBody ⊗ contentsBody)`

### Sequence

There's a useful method that `Traverse` introduces called `sequence`. The names comes from Haskell's `sequence` function, so let's Hoogle it:

` sequence :: Monad m => [m a] -> m [a]`
Evaluate each action in the sequence from left to right, and collect the results.

Here's `sequence` method:

```  /** Traverse with the identity function */
final def sequence[G[_], B](implicit ev: A === G[B], G: Applicative[G]): G[F[B]] = {
val fgb: F[G[B]] = ev.subst[F](self)
F.sequence(fgb)
}```

Instead of `Monad`, the requirement is relaxed to `Applicative`. Here's how we can use it:

```scala> List(1.some, 2.some).sequence
res156: Option[List[Int]] = Some(List(1, 2))

scala> List(1.some, 2.some, none).sequence
res157: Option[List[Int]] = None```

This looks cool. And because it's a `Traverse` method, it'll work for other data structures as well:

```scala> val validationTree: Tree[Validation[String, Int]] = 1.success[String].node(
2.success[String].leaf, 3.success[String].leaf)
validationTree: scalaz.Tree[scalaz.Validation[String,Int]] = <tree>

scala> validationTree.sequence[({type l[X]=Validation[String, X]})#l, Int]
res162: scalaz.Validation[String,scalaz.Unapply[scalaz.Traverse,scalaz.Tree[scalaz.Validation[String,Int]]]{type M[X] = scalaz.Tree[X]; type A = scalaz.Validation[String,Int]}#M[Int]] = Success(<tree>)

scala> val failedTree: Tree[Validation[String, Int]] = 1.success[String].node(
2.success[String].leaf, "boom".failure[Int].leaf)
failedTree: scalaz.Tree[scalaz.Validation[String,Int]] = <tree>

scala> failedTree.sequence[({type l[X]=Validation[String, X]})#l, Int]
res163: scalaz.Validation[String,scalaz.Unapply[scalaz.Traverse,scalaz.Tree[scalaz.Validation[String,Int]]]{type M[X] = scalaz.Tree[X]; type A = scalaz.Validation[String,Int]}#M[Int]] = Failure(boom)```

### Collection and dispersal

EIP:

We have found it convenient to consider special cases of effectful traversals, in which the mapping aspect is independent of the accumulation, and vice versa. The ﬁrst of these traversals accumulates elements effectfully, with an operation of type `a → m ()`, but modiﬁes those elements purely and independently of this accumulation, with a function of type `a → b`.

This is mimicking the use of `for` loop with mutable variable accumulating the value outside of the loop. `Traverse` adds `traverseS`, which is a specialized version of `traverse` for `State` monad. Using that we can write `collect` as following:

```scala> def collect[F[_]: Traverse, A, S, B](t: F[A])(f: A => B)(g: S => S) =
t.traverseS[S, B] { a => State { (s: S) => (g(s), f(a)) } }
collect: [F[_], A, S, B](t: F[A])(f: A => B)(g: S => S)(implicit evidence\$1: scalaz.Traverse[F])scalaz.State[S,scalaz.Unapply[scalaz.Traverse,F[A]]{type M[X] = F[X]; type A = A}#M[B]]

scala> val loop = collect(List(1, 2, 3, 4)) {(_: Int) * 2} {(_: Int) + 1}
loop: scalaz.State[Int,scalaz.Unapply[scalaz.Traverse,List[Int]]{type M[X] = List[X]; type A = Int}#M[Int]] = scalaz.package\$State\$\$anon\$1@3926008a

scala> loop(0)
res165: (Int, scalaz.Unapply[scalaz.Traverse,List[Int]]{type M[X] = List[X]; type A = Int}#M[Int]) = (4,List(2, 4, 6, 8))```

EIP:

The second kind of traversal modiﬁes elements purely but dependent on the state, with a binary function of type `a → b → c`, evolving this state independently of the elements, via a computation of type `m b`.

This is the same as `traverseS`. Here's how we can implement `label`:

```scala> def label[F[_]: Traverse, A](f: F[A]): F[Int] =
(f.traverseS {_ => for {
n <- get[Int]
x <- put(n + 1)
} yield n}) eval 0
label: [F[_], A](f: F[A])(implicit evidence\$1: scalaz.Traverse[F])F[Int]```

It's ignoring the content of the data structure, and replacing it with a number starting with 0. Very effecty. Here's how it looks with `List` and `Tree`:

```scala> label(List(10, 2, 8))
res176: List[Int] = List(0, 1, 2)

scala> label(tree).drawTree
res177: String =
"0
|
1+-
|
2`-
"```

Marc-Daniel Ortega (@patterngazer)'s Where we traverse, accumulate and collect in Scala also covers `sequence` and `collect` using Scalaz.