Haskell Study Plan
Posted by alpheccar - Feb 15 2007 at 18:13 CEST
I have recently convinced one of my friends to learn Haskell. But, he finds it very difficult. He is making a big effort and really wants to learn it but the beginning is hard and he may have spent too much time writing Java code.
So, to help him, I have written a short Haskell study plan. It may interest some other people so I decided to take the risk to post it on my blog. It is very informal and subjective but I think it is a good summary of the problems I had to solve myself to learn Haskell. So, when reading the post don't forget it was initially written for a friend and may look a bit too personal at some places. But, I don't have the energy to write another version.
Forget the imperative world
I think the most difficult for someone coming from the imperative world (Java, C etc...) is to look at program development in a totally different way : forget about state, control flow and time. A software is no more a succession of instructions changing a state.
You have to think in a totally different way : a software is a combination of data transformers. You have some very powerful filters that you apply to data. You have combinators used to create complex filters from more simpler ones. A combinator is itself a kind of filter. There is no more any idea of state or time evolution. Once you have described the transformations to be applied to data to get the solution of your problem, the execution of the software must be understood as an algebraic simplification of your transformations. When no more simplification is possible you have your result.
Control flow is needed for what ? Most of the time it is needed to process some data which have a recursive structure (like a tree) or to extract some data from a structured object. For the former case, you use the powerful data transformers fold, map, iter, scan ... For the latter case you use pattern matching. In the unfrequent cases when you need more, you just use a recursive function.
Of course, nothing prevent you from reintroducing the notions of control flow, state and time in Haskell but you do it in a controlled way and only when needed. Most of the time, you should avoid these notions. If you use them too often it means you are still thinking in the imperative way. You must think in an algebraic way : you are really using an algebra of programming.
The data transformers generally respect some rules. For instance :
map f . map g = map (f.g)
In C, that kind of equivalence cannot be asserted because the order of evaluation matters (because of side effects and non local state). So, it is not possible to define an algebra of programming. Something as simple as f(x) + f(x) = 2 f(x) is generally wrong in C. It depends on f. In Haskell f+f is 2f so you can define an algebra of programming.
So, the first step for learning Haskell is to start learning the algebra of programming. Look at the Prelude. Learn the basic functions like map, fold etc.. Learn how to use them.
Types are your friends. In C, types are used as a documentation and as an help for the compiler to generate better code. But they won't protect you from runtime errors because you can easily cast a value into the wrong type.
Types in Haskell are much much more powerful. They are strong so will prevent most of the runtime errors (a division by zero will raise an exception and is not detected at compile time by the types). Haskell types are a partial specification of your functions but giving a lot of information. Types are constraints on what a function is allowed to do or not. (I'll talk about that later in this post).
The types are very flexible and it is the first strongly and statically typed language that I meet which is as pleasant to use as dynamically typed languages like Lisp. In fact, I only see one remaining reason for using dynamically typed languages : reflexivity when it is really needed (which is not so frequent). But I am less and less certain that advantage is compensating the problems with dynamic types : even if you are careful, are a good programmer, build the right abstractions you'll have too many details to check that could be more easily handled by the compiler. And, it is generally translated into much more unit tests and more exceptions at runtime and also more difficulty to prevent "leaky" abstractions.
So, in Haskell you have to learn a bit about how to decode types and understand them. No need to be an expert in type theory or logic. It is easy. For instance,
map :: (a -> b) -> [a] -> [b]
The type of map is saying that map is taking as argument a function of type a -> b and a list of type [a] and is returning a list of type [b]. From the type we can nearly deduce what map is doing to the list.
Another weird thing is that a function of two variables has a type like:
f :: a -> b -> c
f :: (a,b) -> c
Because you have to think about algebra : f 1 is not enough to get a result because f is needing two arguments but with one argument you can already start the simplification process and partially evaluate f.
So, f 1 is a new function which is needing one argument. Don't forget : evaluation of a program is simplifying an algebraic expression. Forget state, forget time, forget control flow.
Is it useful ? Of course !
map (+1) l
We add 1 to all element of a list. So, we have partially evaluated the function + using just one argument. We get a new function and we finish the evaluation of this new function on each element of the list.
The list may even be infinite !
map (+1) [1..]
Indeed, Haskell is lazy : it will first simplify the function definition and then it will simplify the arguments which are still needed. So, values will be computed only when needed.
An infinite list is a data generation process that will generate elements only when needed by the data transformer which is consuming the list elements.
In the previous example, we should limit the consumption since map is consuming every element:
take 4 $ map (+1) [1..]
When a software is beginning to be complex, you have to modularize it and control what is visible from the clients of your modules. Modules are used for that : they allow to "encapsulate" your implementation and control what is visible from the outside. Since there is nothing new here, I won't detail. Most languages have similar features with more or less power.
When we write:
map :: (a -> b) -> [a] -> [b]
we have a function which can work with list of any type. It is the same function with the same definition for any kind of list.
Sometimes, we want to vary the definition according to the type. For instance, addition of integers, fractions and reals are implemented differently even if from a mathematical point of view we can see integers embedded into fractions and fractions into reals. So, we can say that it is always an addition.
First, we define the property of having an addition operation
class Add a where add :: a -> a -> a
Then, we say that some type has the property of having an addition and we define it
instance Add Int where add x y = ...
It looks like OO but it is different. The instance are not runtime objects. It is not 3 or 4 which are instances of Add. It is Int !
instance means that the type has some property. It is another way to specify what a program can do and constrain it.
For instance, if I later decide to build an average function, I'll need an addition so I'll have to give this information:
average :: (Add a) => [a] -> a
For any type which can be added, I am able to compute an average of a list of elements of that type ... huh ? No ! I need also a division by integers (length of the list). It is another property:
class IntegerDivide a where div :: a -> Int -> a
average :: (Add a, IntegerDivide a) => [a] -> a
So, class are used to specify properties of the types. The properties are not always unrelated. For instance,
class (Eq a, Show a) => Num a where
Any type which has the property of being a Number has also the property of being testable for equality and has also the property of being printable. The => must be read backward.
Said differently : you need to have the property Eq a and Show a to be able to have the property Num a.
But, not all types which have the Eq and Show properties are numbers.
Here again, we see that types are specifications and are allowing the developer to control how the functions can be used or not.
There is one very important property that a type can have : being a Monad !
In previous sections I explained that types are useful as a partial specifications and as constraints.
Let's see a very common and useful example : a controlled environment. We want to compute in a controlled environment and be sure that nothing can leak out of that environment or only through specific gateways.
So, we have a type:
data Controlled a
Let's assume we have a string in that controlled environment:
myString :: Controlled String
We'd like to be able to compute the length of the string in the controlled environment. We cannot use the standard length function because its type is:
length :: String -> Int
(The standard length function has a more general type but it does not matter for the current explanation).
We'd like to have a function returning the length in the controlled environment since we want to prevent anything from leaking out of that controlled area. So, the type should be:
controlledLength :: String -> Controlled Int
But then we have a type mismatch. The function is expecting a String but we just have a Controlled String
But we are lucky, we have a magic operator : the bind operator which can extract the value from its controlled environment and transmit it to a function if and only if the function is returning its result in the same controlled environment. The bind combinator is >>= so we can write
myString >>= controlledLength
Now that we have computed the length in a controlled environment we'd like to be able to use that result in other parts of the software which are not under control. We can do it if the controlled environment is providing a function to escape from the controlled area. But, once we have escaped, the environment is lost. We cannot access it any more .
In general, when these escape functions are available they are named runXXX. So, here we may have a runControlled with type:
runControlled :: Controlled a -> a
The controlled environment may require some additional data so the function may be more general. It depends on the controlled environment where the computation is taking place.
That kind of controlled environment is called a Monad !.
So, you want do to IO, just compute in IO. You need state, Just use State s where s is the type of your state. You need indeterminacy and logic programming, just use LogicT or the simpler list monad. You want configuration information just use Reader. You need a log : just use Writer. You want to mix several controlled environments like a State and IO : StateT s IO.
People are liking OO because OO is providing a controlled environment : State is encapsulated and can only be changed through a controlled interface. Here we are generalizing the idea : we are not just encapsulating State, we are encapsulating computation strategies : state, control flow, side effects, containers etc ...
You cannot escape from IO because IO is controlled by the dark side : the operating system. the runIO is in fact main and the OS is the consumer of your IO actions.
Monad are possible thanks to the type system. Without the type system it will be difficult to prevent information from leaking out of your controlled environment so Monads no more make as much sense without a type system.
So, do you still think Monads are hard ? Is the idea of working in a controlled environment difficult ? Monads are cool : you can build the controlled environments that you want and combine them as you want. You can define computations for a given environment and reuse them later so that they become a bit like new keywords for a specific language. For instance, in the IO environment you can define a computation loop of type:
loop :: Int -> (Int -> IO a) -> IO a
Since the output type is IO a, you can reuse that function in any IO computation:
do putStrLn "Start of the loop" loop 10 $ \i -> do putStrLn ("Loop iteration:" ++ (show i)) putStrLn "end of loop"
do is just a notation when the use of >>= may make the code less readable.
Type can constrain how to use functions and force some properties to be respected.
newtype List a s = List [a]
The previous definition is just defining a new kind of list. But, look at the s parameter on the left. It is not used on the right ! It is just a tag that will be used to force some properties to be respected.
Let's define two new types:
data Safe data Unsafe
These types are special because there is nothing on the right side of the data definition. So there is no data constructor.
You won't be able to create a value of type Safe or Unsafe. These types are phantom ones. They won't be used at runtime but they will be used at compile time to tag definitions and force some constraints.
createList :: List a Unsafe
A new list is Unsafe because it is empty so we cannot get its head.
sTail :: List a s -> List a Unsafe
The result of the special tail (not the standard one from Prelude) is Unsafe because the resulting list may be empty
sAdd :: a -> List a s -> List a Safe
If you add an element to the list then the resulting list is Safe
sHead :: List a Safe -> a
sHead can be applied only to safe lists. So, the typechecker will prevent us from applying head to an empty list ! We have defined a property that we want to be respected by our lists and we have explained to the typechecker how to check it for us. Of course, it will work only if people use the API we have defined. So we must hide the List constructor. But module are used for that. We need to define a module where we control the API which is exported.
It is possible to do much much more with phantom types. I won't give an example because I would not like you to leave that study plan now. But remember that with types you are really writing partial specifications constraining how your functions are going to behave.
We'd like to mix several values of different types in the same list ! So, we have to hide the types. We could do something like:
data H = forall a. H a
The type variable a is not visible on the left because of the forall. The type variable is not free. It is used by the forall. So, a is hidden from the outside. Now, you can write something like
myList = [H (1::Int), H "Hello", H (2.4::Float)]
But, it is not very useful if you cannot do something with these objects.
You cannot have access to the value hidden in H directly because:
f :: H -> a
will not typecheck. The a in the forall for H is distinct from the a defined by function f.
So, to be able to use the values hidden in H, you need to specify they have a common interface. After all, if you decided to mix them in the same list it is probably because you wanted to apply the same kind of transformation to each value.
So, let's define a class:
class MyOperation a where isNumber :: a -> Bool
And some instances:
instance MyOperation Int where isNumber _ = True
instance MyOperation Float where isNumber _ = True
instance MyOperation String where isNumber _ = False
and we need one more instance for H
instance MyOperation H where isNumber (H a) = isNumber a
but it won't work ! Indeed, we need to tell Haskell that H is not containing any kind of value but only the one with a isNumber function.
So, let's write:
data H = forall a. MyOperation a => H a
Now, you can mix several different kind of values in the same list and process them with a given function. But, even if all values have type H there is no risk of mixing a String with a Int. You have the flexibility and the security.
GADT : Generalized Algebraic Data Type
Imagine you'd like to build a calculator. You may define a new data type like:
data Term = I Int | V [Int] | Plus Term Term
But there is a problem : You could write Plus (I 1) (V [4,2,3]) where the list is a vector. Unfortunately, with the standard abstract data type you do not have enough flexibility to avoid this problem. With GADT you can use typechecking to prevent some values to be built because they have no meaning. So, you can define some new constraints:
data Term a where I :: Int -> Term Int V :: [Int] -> Term [Int] Plus :: Term a -> Term a -> Term a
Now our data constructor are not forced to create a value of type Term. We can create a value of type Term a and this a can be used to enforce some constraints a bit like with phantom types.
In the previous definition we tell Haskell that Plus can only be applied to Term of the same type and we also say that I and V are generating Term of different type.
So, we prevent the developer from building values like Plus (I 1) (V [4,2,3]).
So, to understand Haskell you need to forget time, control and state and think about data flow, data transformer, algebra of programming.
Evaluation of a program is simplification of an algebraic expression and not evolution of a State in time.
You need to learn types and how they are used to document, enforce properties, partially specify a behavior, control the evaluation environments.
You need to understand lazy evaluation which allows to separate data generation from data consumption and is key to be able to prevent optimization from leaking through the APIs.
For instance, you may develop as if a file was totally loaded into memory when it is in fact loaded block per block on a needed basis. But, as a consumer of the file content you do not need to know how the content is generated and made available to the client of the API.