March 21, 2014

## Functors in Scalaz

Executive summary:

- A
**Functor**is something you can map over. - Mapping with the
`identity`

function has no effect. - Familiar examples include
`List`

and`Option`

. - Less familiar examples include functions, where you can map over the result type.

## Definition

More formally, a **Covariant Functor** is defined by a type constructor `F[_]`

together with a function

```
map : (A => B) => F[A] => F[B]
```

where the following laws hold:

`map identity`

means the same thing as`identity`

`(map f) compose (map g)`

means the same thing as`map (f compose g)`

Note that `map`

is sometimes called `fmap`

, and the argument order is sometimes reversed.

In common usage we say that type `A`

*is* a functor when it is possible to define an instance of `Functor[A]`

. Some people prefer to say that `A`

*has* a functor.

## Standard Library

Functor-_like_ behavior is built into the Scala standard library, but Functor as an abstraction does
not exist in vanilla Scala. These invocations of `map`

are consistent with the definition:

```
scala> def add1(n:Int) = n + 1
add1: (n: Int)Int
scala> Some(1).map(add1) // ok
res0: Option[Int] = Some(2)
scala> List(1,2,3).map(add1) // ok
res1: List[Int] = List(2, 3, 4)
```

These examples of `map`

are *not* consistent with the defintion of Functor, so beware:

```
scala> "abc".map(_.toUpper) // String has the wrong kind (i.e,. type-level arity)
res2: String = ABC
scala> Set(1,2,3,4,5,6).map(_ / 2) // Breaks parametricity; behavior depends on concrete element type
res3: scala.collection.immutable.Set[Int] = Set(2, 0, 3, 1)
scala> collection.mutable.ArrayBuffer(1,2,3).map(identity) // mutable; violates identity law
res4: scala.collection.mutable.ArrayBuffer[Int] = ArrayBuffer(1, 2, 3)
```

## Scalaz Representation

Scalaz provides the typeclass `Functor[F[_]]`

which defines `map`

as

```
def map[A, B](fa: F[A])(f: A => B): F[B]
```

together with trait `FunctorLaw`

which encodes the laws stated above (this can be used for testing that a given functor instance is lawful).

### Functor Instance

Let’s define `Functor`

instance for a simple container type, and then look at the other operations
that you get for free (all defined in terms of `map`

). Here we will work directly with the Functor
instance; in a later section we will do the same things with library syntax.

```
scala> import scalaz.Functor
import scalaz.Functor
scala> case class Box2[A](fst: A, snd: A)
defined class Box2
scala> implicit val boxFunctor = new Functor[Box2] {
| def map[A, B](fa: Box2[A])(f: A => B): Box2[B] = Box2(f(fa.fst), f(fa.snd))
| }
boxFunctor: scalaz.Functor[Box2] = $anon$1@24c3d6b1
scala> val F = Functor[Box2]
F: scalaz.Functor[Box2] = $anon$1@24c3d6b1
```

#### Function Lifting

The fundamental `map`

operation (which we defined) is also called `apply`

.

```
scala> F.map(Box2("123", "x"))(_.length)
res5: Box2[Int] = Box2(3,1)
scala> F.apply(Box2("123", "x"))(_.length)
res6: Box2[Int] = Box2(3,1)
scala> F(Box2("123", "x"))(_.length)
res7: Box2[Int] = Box2(3,1)
```

We can use `lift`

to take a function `A => B`

to `F[A] => F[B]`

```
scala> F.lift((s:String) => s.length)(Box2("123", "x"))
res8: Box2[Int] = Box2(3,1)
```

`mapply`

takes an `F[A => B]`

and applies it to a value of type `A`

to produce an `F[B]`

.

```
scala> def add1(n:Int) = n + 1
add1: (n: Int)Int
scala> def times2(n:Int) = n * 2
times2: (n: Int)Int
scala> F.mapply(10)(Box2(add1 _, times2 _))
res9: Box2[Int] = Box2(11,20)
```

#### Pairing

We can turn `A`

into `(A,A)`

.

```
scala> F.fpair(Box2(true, false))
res10: Box2[(Boolean, Boolean)] = Box2((true,true),(false,false))
```

Or do this by injecting a constant of any type `B`

on the right or left.

```
scala> F.strengthL(1, Box2("abc", "x"))
res11: Box2[(Int, String)] = Box2((1,abc),(1,x))
scala> F.strengthR(Box2("abc", "x"), 1)
res12: Box2[(String, Int)] = Box2((abc,1),(x,1))
```

Or pair each element with the result of applying a function.

```
scala> F.fproduct(Box2("foo", "x"))(_.length)
res13: Box2[(String, Int)] = Box2((foo,3),(x,1))
```

#### Miscellaneous

We can empty our value of any information, retaining only structure:

```
scala> F.void(Box2("foo", "x"))
res14: Box2[Unit] = Box2((),())
```

We can turn a disjunction of `F`

s into an `F`

of disjunctions. This uses the disjunction type `\/`

from scalaz, which has the same meaning as `Either`

but is a bit more convenient to use.

```
scala> import scalaz.syntax.id._
import scalaz.syntax.id._
scala> F.counzip(Box2(1, 2).left[Box2[String]])
res15: Box2[scalaz.\/[Int,String]] = Box2(-\/(1),-\/(2))
scala> F.counzip(Box2(1, 2).right[Box2[String]])
res16: Box2[scalaz.\/[String,Int]] = Box2(\/-(1),\/-(2))
```

#### Operations on Functors Themselves

So far we have seen operations that Functors provide for the types they describe. But Functors are also values that can be composed in several ways.

We can `compose`

functors, which lets us `map`

over nested structures.

```
scala> import scalaz.std.option._; import scalaz.std.list._ // functor instances
import scalaz.std.option._
import scalaz.std.list._
scala> val f = Functor[List] compose Functor[Option]
f: scalaz.Functor[[α]List[Option[α]]] = scalaz.Functor$$anon$1@69ac3399
scala> f.map(List(Some(1), None, Some(3)))(_ + 1)
res17: List[Option[Int]] = List(Some(2), None, Some(4))
```

We can also `bicompose`

a functor with a **bifunctor** (tutorial forthcoming), yielding a new bifunctor.

```
scala> // import scalaz.std.either._ // either bifunctor instance
| // val f = Functor[List] bicompose Bifunctor[Either]
| // f.bimap(List(Left(1), Right(2), Left(3)))(_ + 1, _ + 2)
| "(Requires scalaz 7.1)"
res21: String = (Requires scalaz 7.1)
```

The `product`

of two functors is a functor over pairs.

```
scala> val f = Functor[List] product Functor[Option]
f: scalaz.Functor[[α](List[α], Option[α])] = scalaz.Functor$$anon$2@7cee216d
scala> f.map((List(1,2,3), Some(4)))(_ + 1)
res22: (List[Int], Option[Int]) = (List(2, 3, 4),Some(5))
```

**TODO**: `icompose`

### Functor Syntax

Scalaz provides syntax for types that have a `Functor`

instance. Many of the operations we have
already seen are available this way:

```
scala> import scalaz.syntax.functor._ // the syntax comes from here
import scalaz.syntax.functor._
scala> val b2 = Box2("foo", "x")
b2: Box2[String] = Box2(foo,x)
scala> b2.map(_.length)
res23: Box2[Int] = Box2(3,1)
scala> b2.strengthL(true)
res24: Box2[(Boolean, String)] = Box2((true,foo),(true,x))
scala> b2.strengthR(true)
res25: Box2[(String, Boolean)] = Box2((foo,true),(x,true))
scala> b2.fpair
res26: Box2[(String, String)] = Box2((foo,foo),(x,x))
scala> b2.fproduct(_.length)
res27: Box2[(String, Int)] = Box2((foo,3),(x,1))
scala> b2.void
res28: Box2[Unit] = Box2((),())
```

The `as`

operation (also called `>|`

) replaces all elements with the given constant, preserving
structure. Note the similarity to the `void`

operation.

```
scala> b2 as 123
res29: Box2[Int] = Box2(123,123)
scala> b2 >| false
res30: Box2[Boolean] = Box2(false,false)
```

The `fpoint`

operation lifts the parameterized type into a given `Applicative`

.

```
scala> import scalaz.std.list._
import scalaz.std.list._
scala> b2.fpoint[List]
res31: Box2[List[String]] = Box2(List(foo),List(x))
scala> import scalaz.std.option._
import scalaz.std.option._
scala> b2.fpoint[Option]
res32: Box2[Option[String]] = Box2(Some(foo),Some(x))
```

The `distribute`

, `cosequence`

, and `cotraverse`

operations require a `Distributive`

instance for the
target type. **TODO**

### Provided Functor Instances

Scalaz provides functor (or better) instances for the following stdlib types. In many cases the functor instance is provided by a subtype of `Functor`

such as `Monad`

.

```
scala> import scalaz._; import Scalaz._ // get all
import scalaz._
import Scalaz._
scala> Functor[java.util.concurrent.Callable]
res33: scalaz.Functor[java.util.concurrent.Callable] = scalaz.std.java.util.concurrent.CallableInstances$$anon$1@2923122a
scala> Functor[List]
res34: scalaz.Functor[List] = scalaz.std.ListInstances$$anon$1@59c1c2bc
scala> Functor[Option]
res35: scalaz.Functor[Option] = scalaz.std.OptionInstances$$anon$1@6442f7db
scala> Functor[Stream]
res36: scalaz.Functor[Stream] = scalaz.std.StreamInstances$$anon$1@ac951b8
scala> Functor[Vector]
res37: scalaz.Functor[Vector] = scalaz.std.IndexedSeqSubInstances$$anon$1@e24716c
```

Either and its projections have functors when partially applied:

```
scala> Functor[({type λ[α] = Either[String, α]})#λ] // Either, if left type param is fixed
res38: scalaz.Functor[[α]scala.util.Either[String,α]] = scalaz.std.EitherInstances$$anon$1@783f9e6b
scala> Functor[({type λ[α] = Either.RightProjection[String, α]})#λ] // Right projection, if left type param is fixed
res39: scalaz.Functor[[α]Either.RightProjection[String,α]] = scalaz.std.EitherInstances$$anon$7@3b664ab
scala> Functor[({type λ[α] = Either.LeftProjection[α, String]})#λ] // Left projection, if right type param is fixed
res40: scalaz.Functor[[α]Either.LeftProjection[α,String]] = scalaz.std.EitherInstances$$anon$4@2fdf4fea
```

Function types are functors over their return type:

```
scala> Functor[({type λ[α] = String => α})#λ]
res41: scalaz.Functor[[α]String => α] = scalaz.std.FunctionInstances$$anon$2@e16a596
scala> Functor[({type λ[α] = (String, Int) => α})#λ]
res42: scalaz.Functor[[α](String, Int) => α] = scalaz.std.FunctionInstances$$anon$10@28da6ea6
scala> Functor[({type λ[α] = (String, Int, Boolean) => α})#λ] // and so on, up to Function8
res43: scalaz.Functor[[α](String, Int, Boolean) => α] = scalaz.std.FunctionInstances$$anon$9@1a00c41a
```

Tuple types are functors over their rightmost parameter:

```
scala> Functor[({type λ[α] = (String, α)})#λ]
res44: scalaz.Functor[[α](String, α)] = scalaz.std.TupleInstances1$$anon$2@21651dc0
scala> Functor[({type λ[α] = (String, Int, α)})#λ]
res45: scalaz.Functor[[α](String, Int, α)] = scalaz.std.TupleInstances1$$anon$3@b34c7a3
scala> Functor[({type λ[α] = (String, Int, Boolean, α)})#λ] // and so on, up to Tuple8
res46: scalaz.Functor[[α](String, Int, Boolean, α)] = scalaz.std.TupleInstances0$$anon$27@3b830dee
```

**TODO** instances for scalaz types