158

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?

Improve this question
1

5 Answers 5

Reset to default
204

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
Improve this answer
Sign up to request clarification or add additional context in comments.

15 Comments

It's probably worth reminding that lifts should respect the standard laws lift id == id and lift (f . g) == (lift f) . (lift g).
Lifts are indeed "a category or something". Carlos has just listed the Functor laws, where id and . are the identity arrow and arrow composition of some category, respectively. Usually when speaking of Haskell, the category in question is "Hask", whose arrows are Haskell functions (in other words, id and . refer to the Haskell functions you know and love).
This should read instance Functor Foo, not instance Foo Functor, right? I'd edit myself but I'm not 100% sure.
Lifting without an Applicative is = Functor. I mean you have 2 choices : Functor or Applicative Functor. The first lifts single parameter functions the second multi parameter functions. Pretty much that's it. Right? It's not rocket science :) it just sounds like it. Thanks for the great answer btw!
@atc: this is partial application. See wiki.haskell.org/Partial_application
|
42

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!

Improve this answer

Comments

26

Let's start with an example (some white space is added for clearer presentation):

> import Control.Applicative > replicate 3 'a' "aaa" > :t replicate replicate :: Int -> b -> [b] > :t liftA2 liftA2 :: (Applicative f) => (a -> b -> c) -> (f a -> f b -> f c) > :t liftA2 replicate liftA2 replicate :: (Applicative f) => f Int -> f b -> f [b] > (liftA2 replicate) [1,2,3] ['a','b','c'] ["a","b","c","aa","bb","cc","aaa","bbb","ccc"] > ['a','b','c'] "abc"

liftA2 transforms a function of plain types to a function of same types wrapped in an Applicative, such as lists, IO, etc.

Another common lift is lift from Control.Monad.Trans. It transforms a monadic action of one monad to an action of a transformed monad.

In general, "lift" lifts a function/action into a "wrapped" type (so the original function gets to work "under the wraps").

The best way to understand this, and monads etc., and to understand why they are useful, is probably to code and use it. If there's anything you coded previously that you suspect can benefit from this (i.e. this will make that code shorter, etc.), just try it out and you'll easily grasp the concept.

Improve this answer

Comments

4

I wanted to write an answer because I wanted to write it from a different point of view.

Let's say you have a functor like for example Just 4 and you wanted to apply a function on that functor for example (*2). So you try something like this:

main = print $ (*2) (Just 4)

And you'll get an error:

No instance for (Num (Maybe a0)) arising from an operator section • In the expression: * 2

Ok that fails. To make (*2) work with Just 4 you can lift it with the help of fmap.

The type signature of fmap:

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

Link: https://hackage.haskell.org/package/base-4.16.0.0/docs/Prelude.html#v:fmap

The fmap function takes an a -> b function, and a functor. It applies the a -> b function to the functor value to produce f b. In other words, the a -> b function is being made compatible with the functor. The act of transforming a function to make it compatible is lifting.

In o.o.p. terms this is called an adapter.

So fmap is a lifting function.

main = print $ fmap (*2) (Just 4)

This produces:

Just 8
Improve this answer

Comments

0

According to this shiny tutorial, a functor is some container (like Maybe<a>, List<a> or Tree<a> that can store elements of some another type, a). I have used Java generics notation, <a>, for element type a and think of the elements as berries on the tree Tree<a>. There is a function fmap, which takes an element conversion function, a->b and container functor<a>. It applies a->b to every element of the container effectively converting it into functor<b>. When only first argument is supplied, a->b, fmap waits for the functor<a>. That is, supplying a->b alone turns this element-level function into the function functor<a> -> functor<b> that operates over containers. This is called lifting of the function. Because the container is also called a functor, the Functors rather than Monads are a prerequisite for the lifting. Monads are sort of "parallel" to lifting. Both rely on the Functor notion and do f<a> -> f<b>. The difference is that lifting uses a->b for the conversion whereas Monad requires the user to define a -> f<b>.

Improve this answer

5 Comments

I gave you a mark down, because "a functor is some container" is troll-flavored flame-bait. Example: functions from some r to a type (let's use c for variety), are Functors. They do not "contain" any c's. In this instance, fmap is function composition, taking an a -> b function and an r -> a one, to give you a new, r -> b function. Still no containers.Also, if I could, I'd mark it down again for the final sentence.
Also, fmap is a function, and doesn't "wait" for anything; The "container" being a Functor is the whole point of lifting. Also, Monads are, if anything, a dual idea to lifting: a Monad lets you use something that has been lifted some positive number of times, as if it had only been lifted once - this is better known as flattening.
@BMeph To wait, to expect, to anticipate are the synonyms. By saying "function waits" I meant "function anticipates".
@BMeph I would say that instead of thinking of a function as a counterexample to the idea that functors are containers, you should think of function's sane functor instance as a counterexample to the idea that functions aren't containers. A function is a mapping from a domain to a codomain, the domain being the cross product of all of the parameters, the codomain being the output type of the function. In the same way a list is a mapping from the Naturals to the inner type of the list (domain -> codomain). They become even more similar if you memoize the function or don't keep the list.
@BMeph one of the only reason lists are thought of as more like a container is that in many languages they can be mutated, whereas traditionally functions cannot. But in Haskell even that isn't a fair statement as neither can be mutated, and both can be copy-mutated: b = 5 : a and f 0 = 55 f n = g n, both involve pseudo-mutating the "container". Also the fact that lists are typically stored completely in memory whereas functions are typically stored as a calculation. But memoizing / monorphic lists that aren't stored between calls both break the crap out of that idea.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.