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

hgiesel
  • 5,430
  • 2
  • 29
  • 56

1 Answers1

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

melston
  • 2,198
  • 22
  • 39