Created
February 21, 2015 05:54
-
-
Save tonymorris/42c491295488f804f882 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// https://groups.google.com/d/msg/scala-functional/NAMWgC90KLA/sU0rw7ceoQMJ | |
object ApplyUnapply { | |
import language.higherKinds // I laugh every time | |
/* | |
In order to define Prism, we must define: | |
* Choice | |
In order to define Choice, we must define Profunctor | |
* Applicative | |
In order to define Applicative, we must define Functor | |
*/ | |
// Let's define Profunctor | |
trait Profunctor[~>[_, _]] { | |
def dimap[A, B, C, D](f: C => A, g: B => D): (A ~> B) => C ~> D | |
} | |
// so now we can define Choice | |
trait Choice[~>[_, _]] extends Profunctor[~>] { | |
def left[A, B, C](f: A ~> B): (A Either C) ~> (B Either C) | |
def right[A, B, C](f: A ~> B): (C Either A) ~> (C Either B) | |
} | |
// Functor as we know it | |
trait Functor[F[_]] { | |
def fmap[A, B](f: A => B): F[A] => F[B] | |
} | |
// And so Applicative, as we know it | |
trait Applicative[F[_]] extends Functor[F] { | |
def pure[A]: A => F[A] | |
def ap[A, B](f: F[A => B]): F[A] => F[B] | |
} | |
// Finally, we can define Prism | |
trait Prism[S, T, A, B] { | |
def prism[~>[_, _]: Choice, F[_]: Applicative] | |
(f: A ~> F[B]): (S ~> F[T]) | |
} | |
// And now we can start answering the question. Restated for clarity (fixed typos): | |
// ---- | |
/* | |
Is there a standard typeclass name for a typeclass that exposes apply/unapply methods for the type? | |
*/ | |
trait ApplyUnapply[T, A] { | |
def apply(a: A): T | |
def unapply(t: T): Option[A] | |
} | |
/* | |
This obviously has variants for different arities, so: | |
*/ | |
trait ApplyUnapply2[T, A, B] { | |
def apply(a: A, b: B): T | |
def unapply(t: T): Option[(A, B)] | |
} | |
/* | |
And so on. There's also an obvious pair of laws: | |
unapply(apply(a)) == Option(a) // unapply gets the value out again | |
unapply(t).map(apply(_) == t).getOrElse(true) // apply puts the value in again | |
*/ | |
// ---- | |
// To the answer. | |
// First, let's define a construction function for prisms. This function is | |
// similar, but not the same, as apply/unapply. | |
def prism[S, T, A, B] | |
( | |
a: B => T // "apply" | |
, u: S => (T Either A) // "unapply" | |
): Prism[S, T, A, B] = | |
new Prism[S, T, A, B] { | |
def prism[~>[_, _]: Choice, F[_]: Applicative] | |
(f: A ~> F[B]): (S ~> F[T]) = { | |
val C = implicitly[Choice[~>]] | |
val F = implicitly[Applicative[F]] | |
// the important part | |
C.dimap( | |
u | |
, (_: T Either F[B]).fold(F.pure, F.fmap(a)) | |
)(C.right(f)) | |
} | |
} | |
// Second, let us define a type-alias that specialises Prism. This type-alias | |
// removes the "polymorphic update" aspect of Prism. That's because the original | |
// question does not have a need for it (at least, not the way it was phrased). | |
// That is to say, if we turn (T) into (A), we are also turning (A) into (T) on | |
// the way back. We are not turning (A) into (B) and then (S) into (T). | |
// The `Prismy` type-alias specialises Prism by removing the polymorphism during | |
// transformation of values. We have only (T) and (A) values. | |
type Prismy[T, A] = | |
Prism[T, T, A, A] | |
// As a consequence of our `Prismy` type-alias, we can further specialise our | |
// construction function, by turning the polymorphic `Either` result to | |
// `Option`. | |
def prismy[T, A]( | |
a: A => T // "apply" | |
, u: T => Option[A] // "unapply" | |
): Prismy[T, A] = // a note on this return type below | |
prism( | |
a | |
, x => u(x).fold( | |
Left(x): T Either A)( // pardon me Scala, but did you say "type inference"? | |
Right(_) | |
) | |
) | |
// We have declared the return type of `prismy` to be `Prismy[T, A]`, which is | |
// the same as `Prism[T, T, A, A]`. However, this is over-specialised, since | |
// none of the operations demand that the loop back from the "unapply" to | |
// "apply" are the same type. That is to say, the (A) to (A) part is | |
// over-specialised and so the return type could well have been | |
// `Prism[T, T, A, B]`. | |
// However, to get more to the point of the question, we can now start to see a | |
// similarity. The `prismy` function captures the idea of `ApplyUnapply` in the | |
// original question statement. | |
// There is a catch though. These construction functions are unrecoverable from | |
// the prism. That is to say, given `ApplyUnapply`, we can obtain the `apply` | |
// and `unapply` functions. This is not true for a `Prism`. | |
// However, in practice, these are rarely necessary. Instead, the derivable | |
// operations of a prism are an intersecting set where: | |
// a) the few operations on `ApplyUnapply`, but not `Prism`, are almost never | |
// necessary | |
// b) the much larger set of operations on `Prism` but not `ApplyUnapply` are | |
// usually contributory to the solution. | |
// We sacrifice very little (in practice, nothing) for a large benefit. | |
// Defining the remainder of the `Prism` library is left as an exercise. | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment