Difference between revisions of "Lifting"

Lifting is a concept which allows you to transform a function into a corresponding function within another (usually more general) setting.

Lifting in general

We usually start with a (covariant) functor, for simplicity we will consider the Pair functor first. Haskell doesn't allow a type Pair a = (a, a) to be a functor instance, so we define our own Pair type instead.

data Pair a = Pair a a deriving Show
instance Functor Pair where
fmap f (Pair x y) = Pair (f x) (f y)

If you look at the type of fmap (Functor f => (a -> b) -> (f a -> f b)), you will notice that fmap already is a lifting operation: It transforms a function between simple types a and b into a function between pairs of these types.

lift :: (a -> b) -> Pair a -> Pair b
lift = fmap

plus2 :: Pair Int -> Pair Int
plus2 = lift (+2)
-- plus2 (Pair 2 3) ---> Pair 4 5

Note, however, that not all functions between Pair a and Pair b can constructed as a lifted function (e.g. \(x, _) -> (x, 0) can't).

A functor can only lift functions of exactly one variable, but we want to lift other functions, too:

lift0 :: a -> Pair a
lift0 x = Pair x x

lift2 :: (a -> b -> r) -> (Pair a -> Pair b -> Pair r)
lift2 f (Pair x1 x2) (Pair y1 y2) = Pair (f x1 y1) (f x2 y2)

plus :: Pair Int -> Pair Int -> Pair Int
plus = lift2 (+)
-- plus (Pair 1 2) (Pair 3 4) ---> Pair 4 6

In a similar way, we can define lifting operations for all containers that have "a fixed size", for example for the functions from Double to any value ((->) Double), which might be thought of as values that are varying over time (given as Double). The function \t -> if t < 2.0 then 0 else 2 would then represent a value which switches at time 2.0 from 0 to 2. Using lifting, such functions can be manipulated in a very high-level way. In fact, this kind of lifting operation is already defined. Control.Monad.Reader (see MonadReader) provides a Functor, Applicative, Monad, MonadFix and MonadReader instance for the type (->) r. The liftM (see below) functions of this monad are precisely the lifting operations we are searching for.

If the size of the containers isn't fixed, it's not always clear how to make lifting operations for them. The [] - type could be lifted using the zipWith-family of functions or using liftM from the list monad, for example.

Applicative lifting

This should only provide a definition of what lifting means (in the usual cases, not in the arrow case). It's not a suggestion for an implementation. I start with the (simplest?) basic operations zipL, which combines to containers into a single one and zeroL, which gives a standard container for ().

class Functor f => Liftable f where
zipL :: f a -> f b -> f (a, b)
zeroL :: f ()

liftL :: Liftable f => (a -> b) -> (f a -> f b)
liftL = fmap

liftL2 :: Liftable f => (a -> b -> c) -> (f a -> f b -> f c)
liftL2 f x y = fmap (uncurry f) \$ zipL x y

liftL3 :: Liftable f => (a -> b -> c -> d) -> (f a -> f b -> f c -> f d)
liftL3 f x y z = fmap (uncurry . uncurry \$ f) \$ zipL (zipL x y) z

liftL0 :: Liftable f => a -> f a
liftL0 x = fmap (const x) zeroL

appL :: Liftable f => f (a -> b) -> f a -> f b
appL = liftL2 (\$)

We need to postulate a few laws so that the definitions make sense. (Are they complete and/or minimal?)

assoc :: ((a, b), c) -> (a, (b, c))
assoc ~(~(x, y), z) = (x, (y, z))

{-
Identity:
fmap snd \$ zipL zeroL x === x
fmap fst \$ zipL x zeroL === x

Associativity:
fmap assoc \$ zipL (zipL x y) \$ z === zipL x \$ zipL y z
-}

Today we have the Applicative class that provides Applicative functors. It is equivalent to the Liftable class.

pure = liftL0
(<*>) = appL

zeroL = pure ()
zipL = liftA2 (,)

Since GHC 7.10, Applicative is a superclass of Monad.

Lifting is often used together with monads. The members of the liftM-family take a function and perform the corresponding computation within the monad.

return  :: (Monad m) => a -> m a
liftM   :: (Monad m) => (a1 -> r) -> m a1 -> m r
liftM2  :: (Monad m) => (a1 -> a2 -> r) -> m a1 -> m a2 -> m r

Consider for example the list monad (MonadList). It performs a nondeterministic calculation, returning all possible results. liftM2 just turns a deterministic function into a nondeterministic one:

plus :: [Int] -> [Int] -> [Int]
plus = liftM2 (+)
-- plus [1,2,3] [3,6,9] ---> [4,7,10, 5,8,11, 6,9,12]
-- plus [1..] []        ---> _|_ (i.e., keeps on calculating forever)
-- plus [] [1..]        ---> []

Every Monad can be made an instance of Liftable using the following implementations:

{-# OPTIONS -fglasgow-exts #-}
{-# LANGUAGE AllowUndecidableInstances #-}

instance (Functor m, Monad m) => Liftable m where
zipL  = liftM2 (\x y -> (x,y))
zeroL = return ()

Lifting becomes especially interesting when there are more levels you can lift between. Control.Monad.Trans (see Monad transformers) defines a class