# Lifting

### From HaskellWiki

(Difference between revisions)

(General definition -> Applicative Functor) |
(→Arrow lifting: type signature of arr was missing parens) |
||

(6 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 33: | Line 33: | ||

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

− | In a similar way, we can define lifting operations for all containers that have "a fixed size", for example for the functions from <hask>Double</hask> to any value <hask>((->) Double)</hask>, which might be thought of as values that are varying over time (given as <hask>Double</hask>). The function <hask> \t -> if t < 2.0 then 0 else 2 </hask> 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. <hask>Control.Monad.Reader</hask> (see [[MonadReader]]) provides a <hask>Functor</hask>, <hask>Monad</hask>, <hask>MonadFix</hask> and <hask>MonadReader</hask> instance for the type <hask>(->) r</hask>. The <hask>liftM</hask> (see below) functions of this [[monad]] are precisely the lifting operations we are searching for. | + | In a similar way, we can define lifting operations for all containers that have "a fixed size", for example for the functions from <hask>Double</hask> to any value <hask>((->) Double)</hask>, which might be thought of as values that are varying over time (given as <hask>Double</hask>). The function <hask> \t -> if t < 2.0 then 0 else 2 </hask> 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. <hask>Control.Monad.Reader</hask> (see [[MonadReader]]) provides a <hask>Functor</hask>, <hask>Applicative</hask>, <hask>Monad</hask>, <hask>MonadFix</hask> and <hask>MonadReader</hask> instance for the type <hask>(->) r</hask>. The <hask>liftM</hask> (see below) functions of this [[monad]] are precisely the lifting operations we are searching for. |

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

− | == | + | == 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 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> | </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 | ||

− | + | zeroL = pure () | |

− | + | zipL = liftA2 (,) | |

− | + | </haskell> | |

− | + | ||

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

## Latest revision as of 22:41, 12 August 2013

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

## Contents |

## [edit] 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

## [edit] 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

## [edit] 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

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