What is "lifting" in Haskell?

functional-programming, haskell

Solution

Lifting is more of a design pattern than a mathematical concept (although I expect someone around here will now refute me by showing how lifts are a category or something).

Typically you have some data type with a parameter. Something like

data Foo a = Foo { ...stuff here ...}

Suppose you find that a lot of uses of `Foo` take numeric types (`Int`, `Double` etc) and you keep having to write code that unwraps these numbers, adds or multiplies them, and then wraps them back up. You can short-circuit this by writing the unwrap-and-wrap code once. This function is traditionally called a "lift" because it looks like this:

liftFoo2 :: (a -> b -> c) -> Foo a -> Foo b -> Foo c

In other words you have a function which takes a two-argument function (such as the `(+)` operator) and turns it into the equivalent function for Foos.

So now you can write

addFoo = liftFoo2 (+)

Edit: more information

You can of course have `liftFoo3`, `liftFoo4` and so on. However this is often not necessary.

Start with the observation

liftFoo1 :: (a -> b) -> Foo a -> Foo b

But that is exactly the same as `fmap`. So rather than `liftFoo1` you would write

instance Functor Foo where
   fmap f foo = ...

If you really want complete regularity you can then say

liftFoo1 = fmap

If you can make `Foo` into a functor, perhaps you can make it an applicative functor. In fact, if you can write `liftFoo2` then the applicative instance looks like this:

import Control.Applicative

instance Applicative Foo where
   pure x = Foo $ ...   -- Wrap 'x' inside a Foo.
   (<*>) = liftFoo2 ($)

The `(<*>)` operator for Foo has the type

(<*>) :: Foo (a -> b) -> Foo a -> Foo b

It applies the wrapped function to the wrapped value. So if you can implement `liftFoo2` then you can write this in terms of it. Or you can implement it directly and not bother with `liftFoo2`, because the `Control.Applicative` module includes

liftA2 :: Applicative f => (a -> b -> c) -> f a -> f b -> f c

and likewise there are `liftA` and `liftA3`. But you don't actually use them very often because there is another operator

(<$>) = fmap

This lets you write:

result = myFunction <$> arg1 <*> arg2 <*> arg3 <*> arg4

The term `myFunction <$> arg1` returns a new function wrapped in Foo:

ghci> :type myFunction
a -> b -> c -> d

ghci> :type myFunction <$> Foo 3
Foo (b -> c -> d)

This in turn can be applied to the next argument using `(<*>)`, and so on. So now instead of having a lift function for every arity, you just have a daisy chain of applicatives, like this:

ghci> :type myFunction <$> Foo 3 <*> Foo 4
Foo (c -> d)

ghci: :type myFunction <$> Foo 3 <*> Foo 4 <*> Foo 5
Foo d

Problem

I don't understand what "lifting" is. Should I first understand monads before understanding what a "lift" is? (I'm completely ignorant about monads, too :) Or can someone explain it to me with simple words?

Original source