Lifting
From HaskellWiki
(Difference between revisions)
(→Applicative lifting) 

(One intermediate revision by one user not shown) 
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 fglasgowexts #} {# 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.