7

I usually hear the term lifting, when people are talking about map, fold, or bind, but isn't basically every higher order function some kind of lifting?

Why can't filter be a lift from a -> Bool to [a] -> [a], heck even the bool function (which models an if statement) can be considered a lift from a -> a to Bool -> a. And if they are not, then why is ap from the Applicative type class considered a lift?

If the important thing is going from ... a ... to ... f a ..., then ap wouldn't fit the case either: f (a -> b) -> f a -> f b

1 Answer 1

18

I'm surprised no one has answered this already.

A lifting function's role is to lift a function into a context (typically a Functor or Monad). So lifting a function of type a -> b into a List context would result in a function of type List[a] -> List[b]. If you think about it this is exactly what map (or fmap in Haskell) does. In fact, it is part of the definition of a Functor.

However, a Functor can only lift functions of one argument. We also want to be able to deal with functions of other arities as well. For example if we have a function of type a -> b -> c we cannot use map. This is where a more general lifting operation comes into the picture. In Haskell we have a lift2 for this case:

lift2:: (a -> b -> c) -> (M[a] -> M[b] -> M[c]) 

where M[a] is some particular Monad (like List) parameterized with a given type a.

There are additional variants of lift defined as well for other arities.

This is also why filter is not a lifting function as it doesn't fit the type signature required; you are not lifting a function of type a -> bool to M[a] -> M[bool]. It is, however, a higher-ordered function.

If you want to read more about lifting the Haskell Wiki has a good article on it

Sign up to request clarification or add additional context in comments.

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.