Yesterday I was having lunch with some co-workers of mine and I mentioned ‘lifting’.
I gave a very general description of what it is and what it’s used for and of them said : ‘It sounds beautiful, but I have no idea what you’re talking about’.
So here’s an example.
The ‘metaphysical’ description goes something like this :
A lifting function takes a function that operates in a certain context as it’s argument and returns a transformation of that function that can operate in a different context.
A C# example :
Consider the following class which wrappes an int and that I have imaginatively called Wrapper :
public class Wrapper
{
public Wrapper(int value)
{
Value = value;
}
public int Value { get; private set; }
public override string ToString()
{
return string.Format("{0} wrapped", Value);
}
}
And then we have the following functions which operate on int’s.
public int Add(int a, int b)
{
return a + b;
}
public int Multiply(int a, int b)
{
return a * b;
}
We can then define a lifting function which unwraps the int’s, applies another function and then wraps up the result again.
public Wrapper Lift(Func<int, int, int> f, Wrapper a, Wrapper b)
{
return new Wrapper(f(a.Value, b.Value));
}
Then we can use the two functions above and apply them to instances of Wrapper like so :
Console.WriteLine(Lift(Add, new Wrapper(41), new Wrapper(1)));
results in : Wrapper 42
Console.WriteLine(Lift(Multiply, new Wrapper(333), new Wrapper(2)));
results in : Wrapper 666
Now I can’t think of a lot of situations (well I can’t think of any actually) where code like that would be useful in C# but let’s see what we can do with it in Haskell.
Translating above code :
data Wrapper = Wrapper Int deriving Show
It’s pretty identical to the C# Wrapper class although we don’t need all that boilerplate code.
The deriving Show part gives us a default ToString Implementation f.i.
Here’s the ‘lift’ function :
lift f (Wrapper a) (Wrapper b) = Wrapper (f a b)
Again similar to the C# example, although we can now use pattern matching and the compiler’s type inference capabilities to be ‘slightly’ less verbose.
We don’t have to define the add and multiply functions in Haskell as operators are functions as well, so there is no need to wrap them in yet more boilerplate code.
Let’s fire up the GHCI and verify that it behaves as expected.
>lift (+) (Wrapper 41) (Wrapper 1) Wrapper 42 >lift (*) (Wrapper 2) (Wrapper 333) Wrapper 666
Well that seems to work.
But even though everything is type checked at compile-time (Haskell being a static language just like C#), Haskell’s rich type system allows us to generalize even further to an extent that is simply not possible in C#.
The lift function does not touch the value of the Wrapper’s field, so it really could be anything and the function would still work.
Let’s change the definition of our Wrapper datatype to a more general version by introducing a type parameter.
data Wrapper a = Wrapper a deriving Show
The a is the type parameter, kind of like a generic in C#, albeit quite a bit more powerful.
Retrying the code again in the GHCI gives exactly the same result as before.
But now we can also do it for other types f.i. :
Doubles :
>lift (+) (Wrapper 41.5) (Wrapper 0.5) Wrapper 42.0
Concatenating strings :
>lift (++) (Wrapper "hello ") (Wrapper "world") Wrapper "hello world"
The types of the wrapped value don’t even have to be same as long as the function we’re lifting matches the parameters.
F.i. :
>let convertAndAppend a b = (read a):b >lift convertAndAppend (Wrapper "1") (Wrapper [2,3,4]) Wrapper [1,2,3,4]
‘read’ is similar to C#’s Parse(Int/Double/DateTime/…) functions and (:) is the operator for appending an element to a list.
So ‘a’ should be a string and ‘b’ should be a list of things that ‘a’ can be parsed into.
In Haskell the compiler is your friend, all this just works but when you try to do something nonsensical such as multiplying two strings you get a compile time error.
>lift (*) (Wrapper "hello ") (Wrapper "world")
<interactive>:1:6:
No instance for (Num [Char])
arising from a use of `*'
Possible fix: add an instance declaration for (Num [Char])
In the first argument of `lift', namely `(*)'
In the expression: lift (*) (Wrapper "hello ") (Wrapper "world")
In an equation for `it':
it = lift (*) (Wrapper "hello ") (Wrapper "world")
Now even though I already think all that kind of parametric polymorphism is pretty kewl and useful, let’s look at why lifting is such an integral part of the Haskell language.
Take the following data structure :
data Session = Session ClockTime ClockTime
Just a simple struct with two fields.
The first representing the beginning of a session, the second the end.
I could have made that more explicit by using record syntax, but I’m trying to keep things simple.
And then we have the following function that calculates the total number of seconds elapsed for a given session.
sessionLength (Session begin end) = tdSec $ diffClockTimes end begin
This is a ‘pure’ function.
Meaning it has no side-effects and every time we pass in the same Session parameter we can be sure we get the same result.
Now consider the following function :
timeIt = do begin <- getClockTime putStr "Timing, press any key to stop." getChar end <- getClockTime return $ Session begin end
This function gets the current time (through getClockTime), then waits for the user to press a key gets the current time again and returns a Session structure with both times filled in.
It’s pretty easy to see that this function is not referentially transparent.
It will return a different result every time we call it.
So what happens when we want to apply our pure function to the result of this ‘impure’ function.
>sessionLength timeIt
<interactive>:1:15:
Couldn't match expected type `Session'
with actual type `IO Session'
In the first argument of `sessionLength', namely `timeIt'
In the expression: sessionLength timeIt
In an equation for `it': it = sessionLength timeIt
The compiler starts moaning.
The error message already explains it but looking at the actual type of our functions will make things clearer if you’re not used to Haskell’s compiler errors.
>:type sessionLength sessionLength :: Session -> Int >:type timeIt timeIt :: IO Session
sessionLength takes a Session as a parameter and returns an Int (the number of seconds elapsed).
timeIt however, does not return a Session, but an IO Session.
So what’s this IO thing.
This is Haskell’s way of saying that we’re executing code that produces side-effects.
Seeing as the getClockTime function is impure, everything we do with the result of that will also be impure.
This kind of code is executed inside a specific context.
In this case the IO Monad.
And once something is inside a Monad it can never, ever, ever escape it.
This protects us from leaking side-effects into places where we don’t expect them.
It does however restricts us a little.
One solution would be to rewrite the sessionLength function to allow for side effects but that would deprive us of all of the advantages (such as ease of program verification for one) of pure code.
A better way to deal with this is lifting.
Although nothing is ever allowed out of the IO Monad, we _are_ allowed to bring things in.
More specifically we can lift pure functions into the IO Monad.
Similarly as in our Wrapper toy example the Control.Monad module defines a lifting function called liftM which does just that.
It takes a pure function and lifts it into the IO Monad context.
So this :
>liftM sessionLength timeIt Timing, press any key to stop. 2
Behaves exactly the way we want.
And now we can write most of our program and algorithms in a pure coding style and separate the side-effects in a very specific place that we then ofcourse unit-, or better yet, quickcheck-test like hell.
.
