# Lifting

### From HaskellWiki

(Difference between revisions)

(→Lifting in general: instance Applicative MonadReader) |
(→Applicative lifting) |
||

(4 intermediate revisions by 3 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 37: | Line 37: | ||

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

− | == Monad lifting == |
+ | == Applicative lifting == |

− | Lifting is often used together with [[monad]]s. The members of the <hask>liftM</hask>-family take a function and perform the corresponding computation within the monad. |
||

− | <haskell> |
||

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

− | </haskell> |
||

− | Consider for example the list monad ([[MonadList]]). It performs a [[Non-determinism |nondeterministic calculation]], returning all possible results. <hask>liftM2</hask> just turns a deterministic function into a nondeterministic one: |
||

− | <haskell> |
||

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

− | </haskell> |
||

− | |||

− | Lifting becomes especially interesting when there are more levels you can lift between. <hask>Control.Monad.Trans</hask> (see [[Monad transformer]]s) defines a class |
||

− | <haskell> |
||

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

− | </haskell> |
||

− | lift takes the side effects of a monadic computation within the inner monad <hask>m</hask> and lifts them into the transformed monad <hask>t m</hask>. We can easily define functions which lift functions between inner monads to functions between transformed monads. Then we can perform three different lifting operations: |
||

− | <hask>liftM</hask> can be used both to transform a pure function into a function between inner monads and to a function between transformed monads, and finally lift transforms from the inner monad to the transformed monad. Because of the purity of Haskell, we can only lift "up". |
||

− | |||

− | == 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 arrow <hask>a b c</hask> stands for a computation which transforms values of type <hask>b</hask> to values of type <hask>c</hask>. The basic primitive <hask>arr</hask>, aka <hask>pure</hask>, |
||

− | <haskell> |
||

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

− | </haskell> |
||

− | is also a lifting operation. |
||

− | |||

− | == Applicative Functor == |
||

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 operations <hask>zipL</hask>, which combines to containers into a single one and <hask>zeroL</hask>, which gives a standard container for (). |
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 operations <hask>zipL</hask>, which combines to containers into a single one and <hask>zeroL</hask>, which gives a standard container for (). |
||

<haskell> |
<haskell> |
||

Line 92: | Line 59: | ||

appL :: Liftable f => f (a -> b) -> f a -> f b |
appL :: Liftable f => f (a -> b) -> f a -> f b |
||

appL = liftL2 ($) |
appL = liftL2 ($) |
||

− | </haskell> |
||

− | |||

− | Now, for example every <hask>Monad</hask> can be made an instance of <hask>Liftable</hask>: |
||

− | <haskell> |
||

− | {-# OPTIONS -fglasgow-exts #-} |
||

− | {-# OPTIONS -fallow-undecidable-instances #-} |
||

− | import Control.Monad |
||

− | |||

− | instance (Functor m, Monad m) => Liftable m where |
||

− | zipL = liftM2 (\x y -> (x,y)) |
||

− | zeroL = return () |
||

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

Line 120: | Line 76: | ||

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

+ | Today we have the <hask>Applicative</hask> class that provides [[Applicative functor]]s. It is equivalent to the <hask>Liftable</hask> class. |
||

+ | <haskell> |
||

+ | pure = liftL0 |
||

+ | (<*>) = appL |
||

− | Applicative functors were introduced by several people under different names: |
+ | zeroL = pure () |

− | * Ross Paterson called them [http://www.haskell.org/arrows/arrows/Control.Sequence.html Sequence] |
+ | zipL = liftA2 (,) |

− | * Conor McBride called them [http://www.haskell.org/pipermail/haskell/2004-July/014315.html Idiom] |
+ | </haskell> |

− | * The same kind of structure is used in the [http://www.cs.uu.nl/groups/ST/Software/UU_Parsing/index.html UU Parsing-Combinators]. |
||

+ | 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). This is still true as of Jan 2013. |
||

+ | |||

+ | == Monad lifting == |
||

+ | |||

+ | Lifting is often used together with [[monad]]s. The members of the <hask>liftM</hask>-family take a function and perform the corresponding computation within the monad. |
||

+ | <haskell> |
||

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

+ | </haskell> |
||

+ | Consider for example the list monad ([[MonadList]]). It performs a [[Non-determinism |nondeterministic calculation]], returning all possible results. <hask>liftM2</hask> just turns a deterministic function into a nondeterministic one: |
||

+ | <haskell> |
||

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

+ | </haskell> |
||

+ | |||

+ | Every <hask>Monad</hask> can be made an instance of <hask>Liftable</hask> using the following implementations: |
||

+ | <haskell> |
||

+ | {-# OPTIONS -fglasgow-exts #-} |
||

+ | {-# LANGUAGE AllowUndecidableInstances #-} |
||

+ | import Control.Monad |
||

+ | |||

+ | instance (Functor m, Monad m) => Liftable m where |
||

+ | zipL = liftM2 (\x y -> (x,y)) |
||

+ | zeroL = return () |
||

+ | </haskell> |
||

+ | |||

+ | Lifting becomes especially interesting when there are more levels you can lift between. <hask>Control.Monad.Trans</hask> (see [[Monad transformer]]s) defines a class |
||

+ | <haskell> |
||

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

+ | </haskell> |
||

+ | lift takes the side effects of a monadic computation within the inner monad <hask>m</hask> and lifts them into the transformed monad <hask>t m</hask>. We can easily define functions which lift functions between inner monads to functions between transformed monads. Then we can perform three different lifting operations: |
||

+ | <hask>liftM</hask> can be used both to transform a pure function into a function between inner monads and to a function between transformed monads, and finally lift transforms from the inner monad to the transformed monad. Because of the purity of Haskell, we can only lift "up". |
||

+ | |||

+ | == 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 arrow <hask>a b c</hask> stands for a computation which transforms values of type <hask>b</hask> to values of type <hask>c</hask>. The basic primitive <hask>arr</hask>, aka <hask>pure</hask>, |
||

+ | <haskell> |
||

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

+ | </haskell> |
||

+ | is also a lifting operation. |
||

[[Category:Idioms]] |
[[Category:Idioms]] |

## 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.