Lifting

From HaskellWiki

(Difference between revisions)

Current revision

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

1 Lifting in general
2 Applicative lifting
3 Monad lifting
4 Arrow lifting

1 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 containers don't have fixed size, 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.

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 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 (,)

In principle,

Applicative

should be a superclass of

Monad

, but chronologically

Functor

and

Monad

were before

Applicative

. Unfortunately, inserting

Applicative

between

Functor

and

Monad

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.

3 Monad lifting

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 #-}
import Control.Monad
 
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

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

lift takes the side effects of a monadic computation within the inner monad

m

and lifts them into the transformed monad

t m

. We can easily define functions which lift functions between inner monads to functions between transformed monads. Then we can perform three different lifting operations:

liftM

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

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 arrow

a b c

stands for a computation which transforms values of type

b

to values of type

c

. The basic primitive

arr

, aka

pure

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

is also a lifting operation.

Retrieved from "http://www.haskell.org/haskellwiki/Lifting"

Category: Idioms

@@ Line 9: / Line 9: @@
     fmap f (Pair x y) = Pair (f x) (f y)
 </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>
 lift :: (a -> b) -> Pair a -> Pair b
@@ Line 33: / Line 33: @@
 </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.
-== 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.
-== General definition ==
-Here are two alternative approaches: [[User:RossPaterson]] calls this <hask>Sequence</hask> (http://www.haskell.org/arrows/arrows/Control.Sequence.html) and [[User:ConorMcBride]] calls it <hask>Idiom</hask> (http://www.haskell.org/pipermail/haskell/2004-July/014315.html). Also note that the same kind of structure is used in the UU Parsing-Combinators (http://www.cs.uu.nl/groups/ST/Software/UU_Parsing/index.html).
 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 ().
@@ Line 94: / Line 59: @@
 appL :: Liftable f => f (a -> b) -> f a -> f b
 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>
@@ Line 121: / Line 75: @@
 -}
 </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]]

Personal tools

Views