by Stephen Compall on Sep 11, 2013

technical

Once you’ve started really taking advantage of Scalaz’s typeclasses
for generic programming, you might have noticed a need to write
typelambdas to use some of your neat abstractions, or use syntax like
`traverse`

or `kleisli`

with a strangely-shaped type as an argument.
Here’s a simple generalization, a `List`

-based `traverse`

.

```
import scalaz.Applicative, scalaz.syntax.applicative._
def sequenceList[F[_]: Applicative, A](xs: List[F[A]]): F[List[A]] =
xs.foldRight(List.empty[A].point[F])((a, b) => ^(a, b)(_ :: _))
```

This works fine for a while.

```
scala> import scalaz.std.option._
import scalaz.std.option._
scala> sequenceList(List(some(1),some(2)))
res1: Option[List[Int]] = Some(List(1, 2))
scala> sequenceList(List(some(1),none))
res2: Option[List[Int]] = None
```

The type of the input in the above example, `List[Option[Int]]`

, can be
neatly destructured into the `F`

and `A`

type params needed by
`sequenceList`

. It has the “shape” `F[x]`

, so `F`

can be picked out by
Scala easily.

Consider something else with a convenient `Applicative`

instance,
though.

```
scala> import scalaz.\/
import scalaz.$bslash$div
scala> sequenceList(List(\/.right(42), \/.left(NonEmptyList("oops"))))
<console>:23: error: no type parameters for method
sequenceList: (xs: List[F[A]])(implicit evidence$1: scalaz.Applicative[F])F[List[A]]
exist so that it can be applied to arguments
(List[scalaz.\/[scalaz.NonEmptyList[String],Int]])
--- because ---
argument expression's type is not compatible with formal parameter type;
found : List[scalaz.\/[scalaz.NonEmptyList[String],Int]]
required: List[?F]
sequenceList(List(\/.right(42), \/.left(NonEmptyList("oops"))))
^
```

Here, `?F`

meaning it couldn’t figure out that you meant ```
({type λ[α]
= NonEmptyList[String] \/ α})#λ
```

.

```
scala> sequenceList[({type λ[α] = NonEmptyList[String] \/ α})#λ, Int
](List(\/.right(42), \/.left(NonEmptyList("oops"))))
res5: scalaz.\/[scalaz.NonEmptyList[String],List[Int]] =
-\/(NonEmptyList(oops))
```

The problem is that `NonEmptyList[String] \/ Int`

has the shape
`F[A, B]`

, with `F`

of kind `* -> * -> *`

after a fashion, whereas the
`F`

it wants must have kind `* -> *`

, and Scala kinds aren’t curried
at all.

`Unapply`

instance`Unapply`

, though, *does* have implicit instances matching the
`F[A, B]`

shape, `unapplyMAB1`

and `unapplyMAB2`

, in its companion so
effectively always visible. What’s special about them is that their
type parameters match the “shape” you’re working with, `F[A, B]`

.

You should look at their source to follow along.

Let’s see if one of them works. For implicit resolution to finish,
it’s important that *exactly* one of them works.

```
scala> import scalaz.Unapply
import scalaz.Unapply
scala> Unapply.unapplyMAB1[Applicative, \/, NonEmptyList[String], Int]
<console>:23: error: could not find implicit value for parameter
TC0: scalaz.Applicative[[α]scalaz.\/[α,Int]]
Unapply.unapplyMAB1[Applicative, \/, NonEmptyList[String], Int]
^
scala> Unapply.unapplyMAB2[Applicative, \/, NonEmptyList[String], Int]
res7: scalaz.Unapply[scalaz.Applicative,
scalaz.\/[scalaz.NonEmptyList[String],Int]]{
type M[X] = scalaz.\/[scalaz.NonEmptyList[String],X];
type A = Int
} = scalaz.Unapply_0$$anon$13@5402af61
```

Here, the type `res7.M`

represents the typelambda being passed to
`sequenceList`

. You can see that work.

```
scala> sequenceList[res7.M, res7.A](
List(\/.right(42), \/.left(NonEmptyList("oops"))))
res8: res7.M[List[res7.A]] = -\/(NonEmptyList(oops))
scala> res8 : NonEmptyList[String] \/ List[Int]
res9: scalaz.\/[scalaz.NonEmptyList[String],List[Int]] =
-\/(NonEmptyList(oops))
```

The `res8`

conformance test shows that Scala can still reduce the
path-dependent `res7.M`

and `res7.A`

types at this level, outside
`sequenceList`

.

Implicit resolution can pick the call to `unapplyMAB2`

partly because
it can pick all of its type parameters without weird typelambda
structures. But in Scalaz, we use typeclasses to guide its choice.

Why didn’t `unapplyMAB1`

work? In this case, you can trust `scalac`

to say exactly the right thing: it looked for
`Applicative[[α]scalaz.\/[α,Int]]`

, and didn’t find one. Sure enough,
`\/`

being right-biased means we don’t offer that instance.

Incidentally, if you were to introduce that instance, you’d break code
relying on right-biased `Unapply`

resolution to work.

`unapplyMAB2`

needs evidence of `TC[({type λ[α] = M0[A0, α]})#λ]`

.
But that’s okay, because we have that, where `TC=Applicative`

,
`M0=\/`

, and `A0=NonEmptyList[String]`

!

```
scala> Applicative[({type λ[α] = \/[NonEmptyList[String], α]})#λ]
res10: scalaz.Applicative[[α]scalaz.\/[scalaz.NonEmptyList[String],α]]
= scalaz.DisjunctionInstances2$$anon$1@2f658816
```

Scala doesn’t need to figure out any typelambda itself for this to
work; we did everything by putting the typelambda right into
`unapplyMAB2`

’s evidence requirement, so it just has to find the
conforming implicit value.

`Unapply`

genericallyNow you can write a `sequenceList`

wrapper that works for `\/`

and
many other shapes, including user-provided shapes in the form of new
`Unapply`

implicit instances. If you’re using Scala 2.9 (still?!) you
need to add `-Ydependent-method-types`

to `scalacOptions`

to write
this function.

```
def sequenceListU[FA](xs: List[FA])
(implicit U: Unapply[Applicative, FA]
): U.M[List[U.A]] =
sequenceList(U.leibniz.subst(xs))(U.TC)
```

Instead of `xs`

being `List[F[A]]`

, it’s `List[FA]`

, and that’s
destructured into `U.M`

and `U.A`

. The latter are path-dependent
types on `U`

, the conventional name of the `Unapply`

parameter. We
have also followed the convention of naming the `Unapply`

-taking
variant function ending with a `U`

.

And that works great!

```
scala> sequenceListU(List(\/.right(42), \/.left(NonEmptyList("oops"))))
res11: scalaz.\/[scalaz.NonEmptyList[String],List[Int]] =
-\/(NonEmptyList(oops))
```

Of course, there’s that strange-looking function body to consider, still.

`U`

evidenceThe type equalities of the original `U.M`

and `U.A`

to the original
types can be seen where `res8`

is refined to `res9`

above. But only
the *caller* of the function knows those equalities, because it
produced and supplied the `unapplyMAB2`

call, which has a structural
type containing those equalities.

The body of `sequenceListU`

doesn’t know those things. In particular,
it *still* can’t pick type parameters to pass to `sequenceList`

without a little help.

The `leibniz`

member is a reified type equality of `FA === U.M[U.A]`

,
meaning those are the same at the type level, even though Scala can’t
see it in this context. It represents genuine evidence that those two
types are equal, and is much more powerful than scala-library’s own
`=:=`

. We’re using the core Leibniz operator, `subst`

, directly to
prove that, *as a consequence of that type equality*, ```
List[FA] ===
List[U.M[U.A]]
```

is *also* a type equality, and that therefore this
[constant-time] coercion is valid. This lifting is applicable in all
contexts, not just covariant ones like `List`

’s. Take a look at
the full API
for more, though you’ll typically just need to come up with the right
type parameter for `subst`

.

You can’t ask for an `Unapply`

and *also* ask for an
`Applicative[U.M]`

; Scala won’t allow it. So, because we needed to
resolve the typeclass anyway to find the `Unapply`

implicit to use, we
just cart it along with the `U`

and give it to the function, which
almost always needs to use it anyway. Because it’s not implicitly
available, you usually need to grab it, `U.TC`

, and use it directly.

`scalaz.syntax`

`map`

comes from functor syntax; it’s not a method on `Function1`

. So
how come this works?

```
scala> import scalaz.std.function._
import scalaz.std.function._
scala> ((_:Int) + 42) map (_ * 33)
res13: Int => Int = <function1>
scala> res13(1)
res14: Int = 1419
```

When you import syntax, as `Functor`

syntax was imported with
`scalaz.syntax.applicative._`

above, you get at least two conversions:
the plain one, like `ToFunctorOps[F[_],A]`

, which works if you have
the right shape, and the fancy one, `ToFunctorOpsUnapply[FA]`

, which
uses an `Unapply`

to effectively invoke `ToFunctorOps`

as in the
above. The latter is lower-priority, so Scala will pick the former if
the value has the `F[A]`

shape.

That gives access to all the methods in `FunctorOps`

, and other ops
classes, with only one special `U`

-taking method. If you have several
functions operating on the same value type, or you can make that type
similar with Leibnizian equality as implicit arguments to your
methods, I suggest grouping them in this way, too, to cut down on
boilerplate.

We sometimes get asked “why not just provide the `Unapply`

version of
the function or ops?”

We do it, and suggest it for your own code, despite the confusion,
because it’s easier to work with real type equalities than with
Leibnizian equality, which you can do in your “real” function
implementation, and as seen in `res8`

above, the path-dependent type
resolution can leave funny artifacts in the inferred result. Here’s
an extreme example from
an earlier demonstration.

```
scala> val itt = IdentityT lift it
itt: IdentityT[scalaz.Unapply[scalaz.Monad,IdentityT[scalaz.Unapply[scalaz.Monad,Identity[Int]]
{type M[X] = Identity[X]; type A = Int}#M,
Int]]
{type M[X] = IdentityT[scalaz.Unapply[scalaz.Monad,Identity[Int]]
{type M[X] = Identity[X]; type A = Int}#M,
X];
type A = Int}#M,
Int]
= IdentityT(IdentityT(Identity(42)))
```

Jason Zaugg implemented Scalaz
`Unapply`

, based on
ideas
from Miles Sabin and
Paul Chiusano.

Leibnizian equality was implemented for Scalaz by Edward Kmett.

Lars Hupel’s talk
(slides,
video)
on the features in the then-upcoming Scalaz 7 at nescala 2013,
including `Unapply`

, gave me the missing “guided by typeclasses”
detail, inspiring me to tell more people about the whole thing at the
conference, and then, much later, write it down here.

*This article was tested with Scala 2.10.2 & Scalaz 7.0.3.*