# Lifting

### From HaskellWiki

(Difference between revisions)

(→Applicative lifting: link to Applicative Functor) |
(→Applicative lifting) |
||

(2 intermediate revisions by 2 users not shown) | |||

Line 9: | Line 9: | ||

fmap f (Pair x y) = Pair (f x) (f y) | fmap f (Pair x y) = Pair (f x) (f y) | ||

</haskell> | </haskell> | ||

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

<haskell> | <haskell> | ||

lift :: (a -> b) -> Pair a -> Pair b | lift :: (a -> b) -> Pair a -> Pair b | ||

Line 86: | Line 86: | ||

In principle, <hask>Applicative</hask> should be a superclass of <hask>Monad</hask>, but chronologically <hask>Functor</hask> and <hask>Monad</hask> were before <hask>Applicative</hask>. | In principle, <hask>Applicative</hask> should be a superclass of <hask>Monad</hask>, but chronologically <hask>Functor</hask> and <hask>Monad</hask> were before <hask>Applicative</hask>. | ||

− | Unfortunately, inserting <hask>Applicative</hask> between <hask>Functor</hask> and <hask>Monad</hask> in the subclass hierarchy would break a lot of existing code and thus has not been done as of today (2011). | + | Unfortunately, inserting <hask>Applicative</hask> between <hask>Functor</hask> and <hask>Monad</hask> in the subclass hierarchy would break a lot of existing code and thus has not been done as of today (2011). This is still true as of Jan 2013. |

== Monad lifting == | == Monad lifting == |

## Revision as of 10:15, 19 January 2013

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

## Contents |

## 1 Lifting in general

We usually start with a (covariant) functor, for simplicity we will consider the Pair functor first. Haskell doesn't allow atype Pair a = (a, a)

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

fmap

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

fmap

a

b

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

Pair a

Pair b

\(x, _) -> (x, 0)

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

Double

((->) Double)

Double

\t -> if t < 2.0 then 0 else 2

Control.Monad.Reader

Functor

Applicative

Monad

MonadFix

MonadReader

(->) r

liftM

[]

zipWith

liftM

## 2 Applicative lifting

This should only provide a definition 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 operationszipL

zeroL

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 -}

Applicative

Liftable

pure = liftL0 (<*>) = appL zeroL = pure () zipL = liftA2 (,)

Applicative

Monad

Functor

Monad

Applicative

Applicative

Functor

Monad

## 3 Monad lifting

Lifting is often used together with monads. The members of theliftM

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

liftM2

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..] ---> []

Monad

Liftable

{-# OPTIONS -fglasgow-exts #-} {-# LANGUAGE AllowUndecidableInstances #-} import Control.Monad instance (Functor m, Monad m) => Liftable m where zipL = liftM2 (\x y -> (x,y)) zeroL = return ()

Control.Monad.Trans

class MonadTrans t where lift :: Monad m => m a -> t m a -- lifts a value from the inner monad m to the transformed monad t m -- could be called lift0

m

t m

liftM

## 4 Arrow lifting

Until now, we have only considered lifting from functions to other functions. John Hughes' arrows (see Understanding arrows) are a generalization of computation that aren't functions anymore. An arrowa b c

b

c

arr

pure

arr :: (Arrow a) => b -> c -> a b c

is also a lifting operation.