@alissapajer

# Yay!

But once you learn basic Haskell syntax, a huge world of implementations opens up to you.

Many Haskell library functions exist in other languages too, for example in scalaz.

We can understand abstractions and concepts (like Yoneda!) through Haskell.

We can develop our learning skills themselves through Haskell.

Haskell forces us to think clearly and logically.

Haskell allows us to write code we can deeply understand.

# Right In

## Types are Cool

Here are some Scala types:

``````Int
String
Option[Boolean]
List[Double]
``````

And here are some Haskell types:

``````Int
String
Maybe Bool
[Double]
``````

## Sets of Values

A type represents a set of values.

Scala:

``````val mby: Option[Boolean] = Some(true)     // or
val mby: Option[Boolean] = Some(false)    // or
val mby: Option[Boolean] = None``````

``````mby :: Maybe Bool
mby = Just True     -- or
mby = Just False    -- or
mby = Nothing
``````

## Large Sets of Values

A type represents a finite or theoretically infinite

set of values.

Scala:

``````val bools: List[Boolean] = List(true, false, true)
val bools: List[Boolean] = List(false, ...)
``````

``````bools :: [Bool]
bools = [True, False, True]
bools = [False, ...]
``````

## Type Equivalence

The Yoneda Lemma claims an equivalence of types.

Two types X and Y are equivalent when
their underlying sets of values are equivalent.

Two equivalent types represent the same information, even though they may look drastically different.

## Type Equivalence Part II

Two types  X and Y are equivalent when can morph from values of X to values of Y and back without losing any information (and vice versa).

( s/equivalent/isomorphic/ )

# How Not Isomorphic Types?

## Types That Are Not Equivalent

Scala:

``````def f1: Option[Boolean]   // three values of this type

def f2: List[Boolean]     // infinitely many values of this type``````

``````f1 :: Maybe Bool   -- three values of this type

f2 :: [Bool]       -- infinitely many values of this type
``````

The types of `f 1` and `f 2` are not isomorphic because...

## Why No Equivalence

Scala:

``````def toList(opt: Option[Boolean]): List[Boolean] = opt match {
case None => List.empty[Boolean]
case Some(b) => List(b)
}
def toOpt(bools: List[Boolean]): Option[Boolean] = bools.headOption
``````
``` ```
``````// need: toOpt(toList(opt)) == opt
// need: toList(toOpt(bools)) == bools
``````

``````scala> toOpt(toList(Some(true))) == Some(true)                 // true
scala> toList(toOpt(List(true, false))) == List(true)          // false``````

`toOpt` loses information.

## Why No Equivalence

``````toList :: Maybe Bool -> [Bool]
toList Nothing = []
toList (Just b) = [b]

toMby :: [Bool] -> Maybe Bool
toMby [] = Nothing
toMby (a:_) = Just a
``````

``````-- need: toList \$ toMby bools == bools
-- need: toMby \$ toList mby = mby
``````

``````ghci> toList \$ toMby [true, false]
[true]
``````

Note the underscore: `toMby` loses information.

## Types That Are Equivalent

Scala:

``````def g1: Option[Boolean]                 // three values

def g2[B](f: Boolean => B): Option[B]   // three values?``````

``````g1 :: Maybe Bool                         -- three values

g2 :: forall b. (Bool -> b) -> Maybe b   -- three values?
``````

The Yoneda lemma claims that
the types of `g1` and `g2` are isomorphic.

# Do We Agree?

## Values are Implementations

Scala:

``````def g2[B](f: Boolean => B): Option[B]     // three impls?
``````
``````// equivalently we can write
def g2[B]: (Boolean => B) => Option[B]    // three impls?``````

``g2 :: forall b. (Bool -> b) -> Maybe b    -- three impls?``

The type of a function is more than just its return type.
Parameters matter too!

## Let's Implement!

Scala:

``````def g2[B](f: Boolean => B): Option[B] = None             // or
def g2[B](f: Boolean => B): Option[B] = Some(f(true))    // or
def g2[B](f: Boolean => B): Option[B] = Some(f(false))   // and there are 3
``````

``````g2 :: forall b. (Bool -> b) -> Maybe b
g2 _ = Nothing          -- or
g2 f = Just \$ f True    -- or
g2 f = Just \$ f False   -- and there are 3
``````

We only have access to two values of type B / b.

The implementations must explicitly provide a Boolean.

## What We're Claiming

Scala:
``````type X[B] = (Boolean => B) => Option[B]
// Option[Boolean] ≅ X ``````

``````type X = forall b. (Bool -> b) -> Maybe b
-- Maybe Bool ≅ X``````

≅ means "isomorphic"

## Intuitions for the Isomorphism

``````type X = forall b. (Bool -> b) -> Maybe b
-- Maybe Bool ≅ X
``````
``````g1 :: Maybe Bool
g1 = Nothing      -- or
g1 = Just True    -- or
g1 = Just False
``````

``` ```
``````g2 :: forall b. (Bool -> b) -> Maybe b
g2 _ = Nothing          -- or
g2 f = Just \$ f True    -- or
g2 f = Just \$ f False``````
Goal: Given a `g2`, get a `g1`.

Given a `g2`, apply it to the id function to get a `g1`.

``````-- g2 id == Nothing
-- g2 id == Just True
-- g2 id == Just False
``````

## Intuitions for the Isomorphism

``````type X = forall b. (Bool -> b) -> Maybe b
-- Maybe Bool ≅ X
``````
``````g1 :: Maybe Bool
g1 = Nothing      -- or
g1 = Just True    -- or
g1 = Just False
``````

``` ```
``````g2 :: forall b. (Bool -> b) -> Maybe b
g2 _ = Nothing          -- or
g2 f = Just \$ f True    -- or
g2 f = Just \$ f False``````

Goal: Given a `g1`, get a `g2`.

Given a `g1`, partially apply fmap to get a `g2`...

``fmap :: (Bool -> b) -> Maybe Bool -> Maybe b ``

But the arguments are in the wrong order! Ut oh!

# My Favorite Function Ever:

## Scala Context for Haskell's flip

In Scala, these functions effectively have the same signature:

``````def foo(a: String, b: Int, c: Double, d: Boolean): List[Int]
def bar(b: Int, a: String, d: Boolean, c: Double): List[Int] ``````

In Haskell, these function signatures are distinct:

``````foo :: String -> Int -> Double -> Bool -> [Int]
bar :: Int -> String -> Boolean -> Double -> [Int] ``````

Why? Because Haskell only has single parameter functions.

(Yay lambda calculus! Yay currying!)

## (╯°□°）╯︵ ┻━┻

``flip :: (a -> b -> c) -> b -> a -> c ``

Can we actually just flip the order of the arguments!?
``````fmap :: Functor f => (a -> b) -> f a -> f b
flip fmap :: Functor f => f a -> (a -> b) -> f b``````

Yes, we can!
``````flip :: (a -> b -> c) -> b -> a -> c
flip f b a = f a b
``````

## Single Parameter Functions

In Scala, parameter order can be treated arbitrarily, but as a result we lose control over partial application.

Partial function application to any parameter is normal.

We rearrange the parameters using `flip`.

## What is the Isomorphism?

``````type X = forall b. (Bool -> b) -> Maybe b
-- Maybe Bool ≅ X
``````

``````inv1 :: Maybe Bool -> X
inv1 mby = \f -> fmap f mby    -- or
inv1 = flip fmap
``````

``````inv2 :: X -> Maybe Bool
inv2 f = f id``````

``````-- inv2 (inv1 p) == p
-- inv1 (inv2 q) == q
``````

## What Can We Abstract?

``````type X = forall b. (Bool -> b) -> Maybe b
-- Maybe Bool ≅ X
``````

``````inv1 :: Maybe Bool -> X
inv1 = flip fmap
``````
``````inv2 :: X -> Maybe Bool
inv2 f = f id``````

The only constrained function we are using is `fmap`.

We can abstract over `Maybe` with a functor.
We can abstract over `Bool` with a type.

## The Abstraction Realized

Given a functor (Maybe) and a type (Bool),

we can construct the isomorphism:

``````type X = forall b. (Bool -> b) -> Maybe b
-- Maybe Bool ≅ X``````

From Data.Functor.Yoneda (Edward Kmett):
``newtype Yoneda f a = Yoneda { runYoneda :: forall b. (a -> b) -> f b } ``
``````liftYoneda :: Functor f => f a -> Yoneda f a
liftYoneda a = Yoneda (\f -> fmap f a)
``````
``````lowerYoneda :: Yoneda f a -> f a
lowerYoneda (Yoneda f) = f id ``````

`liftYoneda` and `lowerYoneda` are inverses.

## Examples of Inverses

``````newtype Yoneda f a = Yoneda { runYoneda :: forall b. (a -> b) -> f b }
liftYoneda :: Functor f => f a -> Yoneda f a
lowerYoneda :: Yoneda f a -> f a
``````

``````ghci> lowerYoneda \$ liftYoneda (Just True)
Just True

ghci> lowerYoneda \$ liftYoneda [1,2,3,4]
[1,2,3,4]
``````

``````yo :: Yoneda Maybe Bool
yo = Yoneda (\f -> Just \$ f True)

ghci> liftYoneda \$ lowerYoneda yo
liftYoneda (Just True)
``````

## Yoneda in Scalaz

``````abstract class Yoneda[F[_], A] {
def apply[B](f: A => B): F[B]       // forall b. (a -> b) -> f b
def run: F[A] = apply(a => a)       // lowerYoneda
}

object Yoneda {
// liftYoneda
def apply[F[_]: Functor, A](fa: F[A]): Yoneda[F, A] = new Yoneda[F, A] {
def apply[B](f: A => B) = Functor[F].map(fa)(f)
}
}
``````
Given a Yoneda, we `run` it to get the secret type out.

``````newtype Yoneda f a = Yoneda { runYoneda :: forall b. (a -> b) -> f b }
liftYoneda :: Functor f => f a -> Yoneda f a
lowerYoneda :: Yoneda f a -> f``````

## Scala Examples

``````scala> Yoneda.apply(Some(true): Option[Boolean]).run
res9: Option[Boolean] = Some(true)
``````

``````scala> Yoneda.apply(List(1,2,3,4)).run
res10: List[Int] = List(1, 2, 3, 4)``````
``` ```

The other identity composition is more verbose.

## Multiple Yoneda's for List(1,2,3)?

``````val revyo = new Yoneda[List, Int] {
def apply[B](f: Int => B): List[B] = List(1,2,3).map(f).reverse
}
``````

How can Yoneda be true? Wouldn't both of these impls map under `run` to `List(1,2,3)`? (Hence no isomorphism!?)
``````def apply[B](f: Int => B): List[B] = List(1,2,3).map(f).reverse
def apply[B](f: Int => B): list[B] = List(1,2,3).map(f)
``````

We can rewrite `apply` as:

``````def apply[B](f: Int => B): List[B] = List(1,2,3).reverse map f
// = List(3,2,1).map(f)    // scalaz's impl
``````
``````scala> revyo.run
res13: List[Int] = List(3, 2, 1)``````

## Yoneda is a Functor

Which means that we can map over it.

``````val yo = new Yoneda[List, Int] {
def apply[B](f: Int => B): List[B] = List(1,2,3).map(f).reverse.tail
}

scala> yo.map(_ + 3)
res22: scalaz.Yoneda[List,Int] = scalaz.Yoneda\$\$anon\$2@4899aebd

scala> yo.map(_ + 3).run
res23: List[Int] = List(5, 4)
``````

## Some Mathy Math

``````newtype Yoneda f a = Yoneda { runYoneda :: forall b. (a -> b) -> f b }
liftYoneda :: Functor f => f a -> Yoneda f a
lowerYoneda :: Yoneda f a -> f``````

For a fixed type `a` and a fixed functor `f`

the Yoneda type represents a set of natural transformations

from the hom functor ( a -> _ )

to the functor f.

This set is isomorphic to the elements of `f a`.

# In Conclusion...

## What I've Observed

You cannot just "mess with it" until it compiles.

Haskell is a learning tool that itself must be learned.