What is "lifting" in Haskell?

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?

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

Paul's and yairchu's are both good explanations.

I'd like to add that the function being lifted can have an arbitrary number of arguments and that they don't have to be of the same type. For example, you could also define a liftFoo1:

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

In general, the lifting of functions that take 1 argument is captured in the type class Functor, and the lifting operation is called fmap:

fmap :: Functor f => (a -> b) -> f a -> f b

Note the similarity with liftFoo1's type. In fact, if you have liftFoo1, you can make Foo an instance of Functor:

instance Functor Foo where
  fmap = liftFoo1

Furthermore, the generalization of lifting to an arbitrary number of arguments is called applicative style. Don't bother diving into this until you grasp the lifting of functions with a fixed number of arguments. But when you do, Learn you a Haskell has a good chapter on this. The Typeclassopedia is another good document that describes Functor and Applicative (as well as other type classes; scroll down to the right chapter in that document).

Hope this helps!

What is "lifting" in Haskell?

Related

Recent Posts