λ Tony’s blog λ

Lifting

Below is a compileable Scala source file. If you read it from top to bottom, it may help with some insights regarding applicative functors. It was partially inspired by Eric’s rendition of The Essence of the Iterator Pattern.

trait Lift[F[_]] {
  // Spot the pattern in these type signatures
  // of increasing arity.
 
  def lift0[A]:
    A => F[A]
 
  def lift1[A, B]:
    (A => B) => (F[A] => F[B])
 
  def lift2[A, B, C]:
    (A => B => C) => (F[A] => F[B] => F[C])
 
  def lift3[A, B, C, D]:
    (A => B => C => D) => (F[A] => F[B] => F[C] => F[D])
 
  // ... and so on
 
  // The relationship between lift<N> and lift<N-1>
  // can be given by a function,
 
  def ap[A, B]:
    F[A => B] => (F[A] => F[B])
}
 
trait LiftImpl[F[_]] extends Lift[F] {
  // Each lift function uses
  // the previous lift function and ap.
 
  def lift1[A, B]:
    (A => B) => (F[A] => F[B])
    = ap compose lift0
 
  def lift2[A, B, C]:
    (A => B => C) => (F[A] => F[B] => F[C])
    = f => ap compose lift1(f)
 
  def lift3[A, B, C, D]:
    (A => B => C => D) => (F[A] => F[B] => F[C] => F[D])
    = f => a => ap compose lift2(f)(a)
}
 
// Notes
// * lift0 is often called: unit, return, pure, point, η
// * lift1 is often called: fmap, map, ∘
// * lift<N> is often called: liftA<N>, liftM<N>

All that is left to do is to implement the LiftImpl trait! You can do this by implementing the ap and lift0 functions.

Examples of implementations that I know will work out if you try to implement them:

class ListLift extends LiftImpl[List]

class OptionLift extends LiftImpl[Option]

class EitherLift[R] extends LiftImpl[({type λ[α] = Either[R, α]})#λ]

class Function1Lift[R] extends LiftImpl[({type λ[α] = R => α})#λ]

Those last couple are a bit funky, but a lot of that is syntax noise rather than anything too complicated. Fill out the body of those classes!

This entry was posted on Sunday, July 17th, 2011 at 10:57 am and is filed under Programming. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

12 Responses to “Lifting”

Charles O'Farrell Says:
July 17th, 2011 at 12:02 pm
I’m finding it tempting to just use the predefined map/flatMap, but I realise that invalidates the whole exercise.
Tony Morris Says:
July 17th, 2011 at 12:24 pm
Cheater! It’s not a big deal if you use flatMap/map to implement ap. You’ll just be repeating the function body otherwise, so as long as you understand that, you don’t lose anything.
Paulo Says:
July 17th, 2011 at 9:16 pm
I’m having some trouble with the third one. Possibly I’m not understanding the type correctly, but shouldn’t the following typecheck:

val el = new EitherLift[Char]
val f1 = (x: Int) => x + 2
el.lift1(f1)(Right(13)) // Ok, gives the expected result Right(15)
el.lift1(f1)(Left(’a')) // Fails to typecheck
Erik Says:
July 17th, 2011 at 11:35 pm
Thanks Tony! This is short and very sweet, just the way I like it. Really enjoyed this one too, btw: http://blog.tmorris.net/understanding-practical-api-design-static-typing-and-functional-programming.
Tony Morris Says:
July 18th, 2011 at 5:12 pm
Hey Paulo, You’ll have to type-annotate your Left(’a') value.
Paulo Says:
July 19th, 2011 at 7:40 am
Thank you! I did try to annotate with Either[Char, Int] before, but it wasn’t working. My fault though, I had 2.7 installed instead of 2.9, and it seems I can drop the type-annotation entirely.
Kenbot Says:
July 19th, 2011 at 10:50 pm
So it looks like most of these can be replaced with a class MonadLift[M[_]: scalaz.Monad] extends LiftImpl[M].

I’m not sure if this can be applied to the Function1 example though. Is it possible?
Channing Walton Says:
July 20th, 2011 at 6:51 pm
Hi Tony,
you mentioned that using map/flatmap is cheating. Any chance of a hint how to implement ap without flatmap/map?

Thanks

Channing
Tony Morris Says:
July 21st, 2011 at 7:26 am
Hi Kenbot, yes a monad gives rise to all of the operations, however, a monad is not necessary. You may weak the interface to an applicative functor, which has some desirable properties that monads do not.

Channing, you’d just reimplement the bodies of flatMap/map in your definition of ap. If you’re comfortable with knowing how it all works, just use flatMap/map.
Germán Says:
July 26th, 2011 at 1:01 am
I tried ListLift and OptionLift, for which I tend to use for comprehensions. But these in turn are based on flatMap/map, right? If there was no flatMap/map, I guess you’d go for imperative iteration and pattern matching. Am I off the mark?
Tony Morris Says:
July 26th, 2011 at 7:34 am
Germán, I’d use the next best thing available. Pattern-matching is a last resort, but in the absence of specialised combinators I might just have to resort that low in abstraction.
λ Tony’s blog λ » Blog Archive » Lifting (Haskell addendum) Says:
August 19th, 2011 at 11:03 am
[...] follow-on from Lifting. A port of the Scala code to Haskell follows. class Lift f where lift0 :: a -> f a lift1 [...]

Lifting

12 Responses to “Lifting”

Leave a Reply