How Haskell is Changing my Brain



@alissapajer


Yoneda

Yay!

Why Haskell?


Haskell syntax looks different.


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.

Haskell for Learning


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.


Let's Jump

Right In


*SPLASH*

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


Haskell:

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, ...)


Haskell:

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

Isomorphic Types?



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


Haskell:

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

Haskell:

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?


Haskell:

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?

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

Haskell lesson:
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

Haskell:
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

Haskell:

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:

Haskell's `flip`

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.


Haskell lesson:

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

Follow the types.
-- 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.

Haskell reference:
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


Haskell forces you to stop and reason about your code.


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


Once you learn to read Haskell, you can read Haskell implementations of concepts you know from other languages.

Learning Haskell


Haskell is a learning tool that itself must be learned.



http://learnyouahaskell.com/


https://github.com/NICTA/course


http://www.haskell.org/hoogle/



Thank You!