Lens_and_zipper_equivalence.scala

object LensToZiper {

/*
  This is a small sleight of hand to show how
  [lenses](https://en.wikibooks.org/wiki/Haskell/Lenses_and_functional_references)
  are actually related to to zippers (getters + setters).

  This connection give some insight about why lenses
  have the properties they have. So let's define all
  we need for lenses:
*/

import scala.language.higherKinds

trait Functor[F[_]] {
  def map[X,Y](fx: F[X], f: X => Y): F[Y]
}

trait Lens[A,B] {
  def apply[F[_]](f: A => F[A])(implicit ev: Functor[F]): B => F[B]
}

/* Pretty tricky isn't it? It is actually very simple if you consider a small
   example. Take the value `(3, true)`

   If you have some function `f` that can, possibly with (side-)effects, from `3`
   compute some value, say 9, then it is trivial from `(3, true)` to replace `3`
   by `9` to get `(9, true)`

   It means that if you can, from a sub-term (`3` in our example), compute some value
   (`9` in our example), then you can replace the sub-term (still `3` in out example)
   by the value in the whole expression (`(3, true)` in our example) to get another
   big expression (`(9, true)`).
*/

object ex1 extends Lens[Int, (Int, Boolean)] {
  def apply[F[_]](f: Int => F[Int])(implicit ev: Functor[F]): ((Int, Boolean)) => F[(Int, Boolean)] =
    { case (i, b) => ev.map(f(i), (j: Int) => (j, b)) }
}

/* If we reorganize arguments a little bit, in an equivalent way: */

trait Lens2[A,B] extends Lens[A,B] {
  def apply2[F[_]](b:B)(f: A => F[A], ev: Functor[F]): F[B]

  final def apply[F[_]](f: A => F[A])(implicit ev: Functor[F]): B => F[B] =
    (b:B) => apply2[F](b)(f, ev)
}

/* Still a bit of argument manipulation, sill in an equivalent way: */

trait Lens3[A,B] extends Lens2[A,B] {
  def apply3(b:B): Lens3Aux[A,B]

  final def apply2[F[_]](b:B)(f: A => F[A], ev: Functor[F]): F[B] =
    apply3(b)[F](f, ev)
}

trait Lens3Aux[A,B] {
  def apply[F[_]](f: A => F[A], ev: Functor[F]): F[B]
}

/* Doesn't the type `Lens3Aux` looks familiar?
   It really looks like a `fold` function of type
  whose constructors would be:
  
   - def f : A => F[A]

   and def ev: Functor[F] which is actually

   - def ev[X,Y] : (F[X], X => Y) => F[Y]`

   because a functor instance is really only the map function.
   Let's give this type a name: `Lens3ADT1`
*/

sealed abstract class Lens3ADT1[A,B] extends Lens3Aux[A,B] {
  final def apply[F[_]](f: A => F[A], ev: Functor[F]): F[B] = Lens3ADT1.fold[A,B,F](f,ev)(this)
}
final case class ConstructorF1[A](a: A) extends Lens3ADT1[A,A]
final case class ConstructorEV1[A,X,Y](fx: Lens3ADT1[A,X], f: X => Y) extends Lens3ADT1[A,Y]

object Lens3ADT1 {
  def fold[A,B,F[_]](f: A => F[A], ev: Functor[F]): Lens3ADT1[A,B] => F[B] =
    (l: Lens3ADT1[A,B]) => l match {
      case c : ConstructorF1[a] => f(c.a)
      case c : ConstructorEV1[a,x,y] => ev.map(fold(f,ev)(c.fx), c.f)
    }
}

/* We're making some progress but we're not still done.
   The `map` function of a `Functor` must satisfy some properties.
   One if them is `l.map(f).map(g) == l.map(f.andThen(g))`
   for any valid `l`, `f` and `g`.
   
   L3ADT1 should satisfy this equality which means we should have
   
   ConstructorEV1(ConstructorEV1(l, f), g) == ConstructorEV1(l, f.andThen(g))
   
   Unfortunately this is not the case but we can define a smart constructor just for that:
*/

def constructorEV1[A,X,Y](gx: Lens3ADT1[A,X], g: X => Y):  Lens3ADT1[A,Y] =
  gx match {
    case c : ConstructorEV1[a,w,x] => constructorEV1(c.fx, c.f.andThen(g))
    case _ => ConstructorEV1(gx, g)
  }

/* This time we have 

   constructorEV(constructorEV(l, f), g) == constructorEV(l, f.andThen(g))

   An interesting consequence of using `constructorEV1` is there is no more one `ConstructorEV1`
   as first argument of another `ConstructorEV1` because we can always rewrite this case by the
   right-hand side of the equality: `constructorEV1(l, f.andThen(g))`.

   So the first argument of `ConstructorEV1` has to be `ConstructorF` which is equivalent to
   having a value `a` of type `A`.

   Let's redefine `Lens3ADT1` to take this into account:
*/

sealed abstract class Lens3ADT2[A,B] extends Lens3Aux[A,B] {
  final def apply[F[_]](f: A => F[A], ev: Functor[F]): F[B] = Lens3ADT2.fold[A,B,F](f,ev)(this)
}
final case class ConstructorF2[A](a: A) extends Lens3ADT2[A,A]
final case class ConstructorEV2[A,Y](a: A, f: A => Y) extends Lens3ADT2[A,Y]

def constructorEV2[A,X,Y](gx: Lens3ADT2[A,X], g: X => Y):  Lens3ADT2[A,Y] =
  gx match {
    case c : ConstructorEV2[a,x] => ConstructorEV2(c.a, c.f.andThen(g))
    case c : ConstructorF2[a]    => ConstructorEV2(c.a, g)
  }


object Lens3ADT2 {
  def fold[A,B,F[_]](f: A => F[A], ev: Functor[F]): Lens3ADT2[A,B] => F[B] =
    (l: Lens3ADT2[A,B]) => l match {
      case c : ConstructorF2[a] => f(c.a)
      case c : ConstructorEV2[a,y] => ev.map(f(c.a), c.f)
    }
}

/* One other rule `map` must satisfy is `l.map(x => x) == l` for any valid `l`.
   Which means for `Lens3ADT2` that

   ConstructorF2(a) == ConstructorEV2(a, x => x)

   This time, it is the constructor `ConstructorF2` that we can replace by a smart constructor
   to fulfil this equality:
*/

def constructorF2[A](a: A): Lens3ADT2[A,A] = ConstructorEV2[A,A](a, (x:A) => x)

/* Another consequence is we don't even need `ConstructorF2` anymore.
   We can rewrite `Lens3ADT2` into:
*/

final case class Lens3ADT3[A,B](a: A, f: A => B)
  extends Lens3Aux[A,B] {
    final def apply[F[_]](f: A => F[A], ev: Functor[F]): F[B] = Lens3ADT3.fold[A,B,F](f,ev)(this)
}

object Lens3ADT3 {
  def fold[A,B,F[_]](f: A => F[A], ev: Functor[F]): Lens3ADT3[A,B] => F[B] =
    (l: Lens3ADT3[A,B]) => ev.map(f(l.a), l.f)
}

/* Updating the definition of `Lens3[A,B] we get, sill in an equivalent way: */

trait Lens4[A,B] extends Lens3[A,B] {
  def apply4(b:B) : (A, A => B)

  final def apply3(b:B): Lens3Aux[A,B] = {
    val (a, context) = apply4(b)
    Lens3ADT3(a, context)
  }
}

/* `Lens4[A,B]` instances are just functions: B => (A, A => B)

    Finally we can establish the equivalence between the two following
    forms:
*/

type LensViaZipper[A,B] = B => (A, A => B)
// Which is equivalent to a getter (B => A) and a setter (B => A => B)

def toClassic[A,B](lz: LensViaZipper[A,B]): Lens[A,B] =
  new Lens[A,B] {
    def apply[F[_]](f: A => F[A])(implicit ev: Functor[F]): B => F[B] =
      (b: B) => {
        val (a, context) = lz(b)
        ev.map(f(a), context)
      }
  }

def toViaZipper[A,B](lc: Lens[A,B]): LensViaZipper[A,B] = {
  type F[X] = (A, A => X)

  val ev = new Functor[F] {
    def map[X,Y](fx: F[X], f: X => Y): F[Y] =
      (fx._1, fx._2.andThen(f))
  }

  val f: A => F[A] = (a: A) => (a, (x:A) => x)

  lc[F](f)(ev)
}

/* Nice, isn't it? It explains well how a lens is nothing more than a pair of of
   a getter and a setter.

   There are two very general techniques i have used here. The first one is
   the equivalence between the type of a (Generalized) Algebraic Data Type
   (i.e. case classes/case object/sealed trait) and the type of its recursor
   (the type of the `fold` function). The second one is to take advantage of 
   the equalities a structure have to satisfy to simply its type and find
   a simple yet genral form.

   Theses techniques works very well in practice and enable to see connections
   where it would be very difficult to do intuitively.
*/
}