Lifting
From HaskellWiki
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.