Learn to program in Haskell, lesson 1.5

[Ari Rahikkala]

(it's called lesson 1.5 because it turns out I said I would explain higher-order functions in this lesson, but... it would have become overwhelmingly long if I had done that, so I decided not to)

First, let's install GHC, the Haskell implementation that currently doesn't really have any competition for serious development. You'll probably want the new-style Windows installer. The installation should be straightforward, but there's a little snag that I find quite annoying that has to be removed once the installation is complete:

Go to the properties of the shortcut for GHCi and add the flag "-fno-monomorphism-restriction" to the command (i.e. there's a text line input box that looks like "c:\whatever\the\path\to\ghc\is\ghci.exe", change the end to "ghci.exe -fno-monomorphism-restriction"). It'll be a while before I can explain the rather technical reason behind the restriction, but since it basically trades programmer convenience for predictability of performance, and we care a lot more about convenience than porformance at this point, we'll turn it off.

Now that you've got a working Haskell implementation, a few things will change. One, you will never have to evaluate an expression by hand again - GHC will do it for you. Two, we won't be using the <> shorthand from lesson 1 anymore - since an expression is equal to its value, if I want to say that some expression evaluates to something, I'll just use the equality operator (==). Three, when I mention operators (such as the equality operator there, or plus or minus, etc.), I will write them in parentheses, since that is (for a reason that we'll learn later) the way it's done by Haskell users.

Start up ghci. Every expression we've used so far will work in it, except that when you define a name in ghci, you need to prefix the line with "let". Here's an example ghci session doing a few of the things we did in lesson 1. The lines beginning with Prelude> are stuff written by me (except for the "Prelude>" itself):

Code: Select all

   ___         ___ _
  / _ \ /\  /\/ __(_)
 / /_\// /_/ / /  | |      GHC Interactive, version 6.6, for Haskell 98.
/ /_\\/ __  / /___| |      http://www.haskell.org/ghc/
\____/\/ /_/\____/|_|      Type :? for help.

Loading package base ... linking ... done.
Prelude> (\x -> x + 6) 5
11
Prelude> let average x y = (x + y) / 2
Prelude> average 2 4 == 3
True
Prelude> let seven = 7
Prelude> let max x y = if x > y then x else y
Prelude> average (max seven 10) 0
5.0

You can quit ghci by entering :q and find out the type of an expression by entering :t expression.

Type, you ask? Every Haskell expression has a type. The type tells Haskell what it is and what it isn't allowed to do with that expression. For instance, you can switch the truth value of a Bool around with the function not: True becomes False and False becomes True. You do not need to figure out the types of your expressions yourself - Haskell will infer them for you.

The most important types for now are:
- Char, the type of single characters of text
- String, aka [Char], the type of lists (sequences) of characters, i.e. pieces of text. In general, a type inside square brackets means "a list of things of this type".
- Integer, the type of whole numbers
- Bool, the type of truth values

Functions have types, too. For instance, the type of not - the function that flips truth values around - is Bool -> Bool. This means "give me a Bool and I will evaluate to a Bool". The type of gcd is slightly more general than what we can deal with so far, but a good approximation is Integer -> Integer -> Integer. This means "give me two Integers and I will evaluate to an Integer". length :: [a] -> Int means "length wants you to give it a list of things so it can evaluate to an int" - the meaning of the "a" (standing for "something") here will be explained later.



Since Haskell knows the type of each expression, and what can be done with each type, it can tell you if you try to do impossible things by mistake. For instance, try flipping around the truth value of a string (a piece of text), though, and this is what you get:

Code: Select all

Prelude> not "hello"

<interactive>:1:4:
    Couldn't match expected type `Bool' against inferred type `[Char]'
    In the first argument of `not', namely `"hello"'
    In the expression: not "hello"
    In the definition of `it': it = not "hello"

Here GHC is saying that the function not expected its argument to be a Bool, but it was a list of characters instead.

Another type error that you'll commonly come across involves typeclasses, which will be elaborated on later. Here's an example of an error involving them, though:

Code: Select all

Prelude> not 5

<interactive>:1:4:
    No instance for (Num Bool)
      arising from the literal `5' at <interactive>:1:4
    Possible fix: add an instance declaration for (Num Bool)
    In the first argument of `not', namely `5'
    In the expression: not 5
    In the definition of `it': it = not 5

What GHC is saying here, in essence, is that it can't use a number as a truth value, although it's giving us the benefit of doubt and saying that maybe we should tell it how to do exactly that. Let's not do that, though...



Exercises:

Ask GHCi about the types of various expressions. Here's a couple of example expressions to try:

"hello"
("hello, " ++)
"hello, " ++ "world"
(++)
1
1 + 2
1 + 2.5
(+)

A lot of the types have features that will look strange for now. This is because of Haskell's polymorphism features which help you get a lot more work done with far fewer functions. They will be handled later.

Play around with the various functions in the Haskell Prelude - the reason why it says "Prelude" on the command line is that you have access to the Prelude functions. Try ones like replicate, length, (++), (:), minimum and maximum to play with lists, for instance. The full list of names defined in the Prelude can be found at http://www.haskell.org/onlinereport/sta ... elude.html or by pressing tab twice at an empty GHCi prompt. Try to use types to help you match up useful expressions - Haskell programmers often say that the type system alone is strong enough that a randomly created expression might be useful if it type-checks.

Try functions like map, foldr and filter, too. They are some of the most commonly used functions in Haskell, but since they're all higher-order functions I'm going to defer explaining them in-depth to the next lesson. Here's a couple of examples of what they do, though:

Code: Select all

map (\x -> x + 1) [1,2,3] == [2,3,4] -- map takes a function and a list as its arguments, and applies the function to each value in the list

filter (\x -> x > 0) [1, -5] == [1] -- filter takes a predicate (a function that evaluates to a truth value) and a list as its arguments and throws out all of the values that don't match the predicate (make it evaluate to True when given as an argument to it)

foldr (+) 0 (map (+ 1) [1,2,3]) == foldr (+) 0 [2,3,4] == 9 -- the full meaning of this line will be explained later...

If a function like repeat, cycle or iterate makes the screen fill up with text, don't worry - just press ctrl-c and it will stop.




Lessons will be posted at a slightly slower pace from now on, depending on how well people seem to be taking them in, so as to avoid overloading people and making them think they're falling behind. If at any part you feel I'm going too slowly, you can just go http://haskell.org/haskellwiki/Books_and_tutorials and try out the many tutorials over there.


Thought of the day: Yes, these lessons are rather concise. That's because I work to keep them short: If I were to just let go and write out everything I thought interesting, these lessons would definitely be a lot lengthier - and a lot harder to understand, too, since I would constantly be going off on irrelevant tangents. Besides, Haskell is a concise language, so by symmetry, lessons about it should be concise.

[Ari Rahikkala]

It's going to be at least a couple of days before the next lesson. Please post comments, suggestions, thoughts, criticism, etc. here. I haven't told you much about what you can *do* with Haskell yet - you can use it as something of a rather functional desk calculator at this point, and I'm going do my best to pick up examples of... interesting bits of Haskell code to include in the later lessons, but... it's still going to be a while before you can do a lot of meaningful things. That's the way it is in any programming language, especially with this kind of approach, starting from elementary mathematics.

Anyway, though, if you do have any thoughts (or dreams maybe?) about what you could possibly do if you knew a programming language decently well, please do air them here - if I can, I will try to take the later lessons in that direction.

Also, any questions raised will be duly answered.

[Jonas]

What a lessons

[Ari Rahikkala]

Yes... and the experiment is also bearing fruit: It seems that people *are* overwhelmed by this, therefore... I will have to remould lessons 1 and 1.5 into a more palatable form before we can continue. Before I can do that, I'll have to gather up good *reasons* for taking the course... partly by finding them myself, partly by asking people what they would *like* to learn.

It'll be at least a week until I can do that, though, since while my parents did tell they're moving to a new house they didn't mention they're renovating it, too, and helping out at that is taking pretty much all of my time...

[Neike Taika-Tessaro]

The type tells Haskell what it is and what it isn't allowed to do with that expression.

Prelude> :t Ari Rahikkala
Ari Rahikkala :: Person that rockz0rs sockz0rs

The type of gcd is slightly more general than what we can deal with so far, but a good approximation is Integer -> Integer -> Integer. This means "give me two Integers and I will evaluate to an Integer".

I've understood the syntax in that I've committed to memory, but for the life of me, no one has ever managed to explain to me why it's written like that. I know writing Integer -> (Integer -> Integer) is pretty much the same thing, but that's where any attempt at understanding the reasons behind the syntax fails me.

Do you happen to know why it's written like that, rather than, say, Integer Integer -> Integer? Or (Integer,Integer) -> Integer? I mean, I can see from toying with :t (see musings a few paragraphs down) that Integer -> Integer -> Integer, if given only one parameter, is thus still of a valid type (even if that type will never hold a value, as far as I can tell)... but is that the reason for it?

*goes crosseyed - since 'Integer' as a word suddenly looks all funny*

Here GHC is saying that the function not expected its argument to be a Bool, but it was a list of characters instead.

[...] What GHC is saying here, in essence, is that it can't use a number as a truth value, although it's giving us the benefit of doubt and saying that maybe we should tell it how to do exactly that.

I know you said you'd elaborate on it later, but: why doesn't the GHC give you the benefit of doubt about [Char] -> Bool? As in, what makes Integer special? At first I thought that maybe there is an internal mapping of Integer -> Bool for some values of Integer, e.g. 1 and 0, but not 1 and not 0 yield the same error message. So it begs the question what about the types is different.

Code: Select all

Prelude> :t "hello"
"hello" :: [Char]
Prelude> :t ("hello,"++)
("hello,"++) :: [Char] -> [Char]

I expect this is because (++) is [a] -> [a] -> [a]... meaning, (++) expects two parameters, meaning, (++) is a binary operator. I noticed this doesn't actually evaluate to anything - I expect it's like doing something like:

Code: Select all

Prelude> length

Function, without the parameter: has a type, but doesn't evaluate to anything.

Yes?

Code: Select all

Prelude> :t "hello, " ++ "world"
"hello," ++ "world" :: [Char]
Prelude> :t (++)
(++) :: [a] -> [a] -> [a]

String concatenation! (Yes, I'm proud of discovering the obvious.)

Code: Select all

Prelude> :t 1
1 :: (Num t) => t
Prelude> :t 1 + 2
1 + 2 :: (Num t) => t
Prelude> :t 1 + 2.5
1 + 2.5 :: (Fractional t) => t
Prelude> :t (+)
(+) :: (Num a) => a -> a -> a

Can you explain the =>? If you say polymorphism, I expect it has something to do with class hierarchies... 'parent of', perhaps? I don't, though, yet, see how that would make sense, but I've vowed to myself to muse aloud during the taking of these lessons. I think best when I type. Whee.

Play around with the various functions in the Haskell Prelude - the reason why it says "Prelude" on the command line is that you have access to the Prelude functions. Try ones like replicate, length, (++), (:), minimum and maximum to play with lists, for instance.

I did this and thought I'd share my thought-processes during the whole thing here. Not sure if that's sane, or anything, but I figure, what's the harm? (I deliberately hadn't read your elaborations on the functions yet.)

Code: Select all

Prelude> minimum "hello"
'e'

This made my day. I was stunned first, then realised 'e' comes before 'h', 'l' and 'o' in the alphabet... so minimum finds the minimal value in a list, not the minimal index... that was unexpected. Very sane, though.

Code: Select all

Prelude> maximum "hello"
'o'
Prelude> length "hello"
5
Prelude> :t (:)
(:) :: a -> [a] -> [a]

Hm. What's this?

Code: Select all

Prelude> 'e' : "hello"
"ehello"

Ooh. Gotcha.

Though that took me two attempts, because I tried "e" : "hello" first. And suddenly I'm thankful for my deep love of Object Pascal... lest I might have despaired. But, that's right, 'e' is Char, "e" is [Char] (with one element).

Maybe this'll save others the headache, here.

Code: Select all

Prelude> :t minimum
minimum :: (Ord a) => [a] -> a
Prelude> :t maximum
maximum :: (Ord a) => [a] -> a

Again, I feel a bit helpless with the =>, so this doesn't tell me much, other than that I don't understand it yet. *makes note to get back to this later*

Code: Select all

Prelude> :t length
length :: [a] -> Int
Prelude> :t replicate
replicate :: Int -> a -> [a]

Aha. A function that expects two parameters... a number and something. And it returns a list of something. Ah, I think I can hazard what this does. A list of the second parameter, repeated as often as the first parameter dictates?

Code: Select all

Prelude> replicate 2 "hello"
["hello","hello"]

[[Char]]?

Code: Select all

Prelude> :t replicate 2 "hello"
replicate 2 "hello" :: [[Char]]

Yes! Rocks!

Try functions like map, foldr and filter, too.

Code: Select all

Prelude> :t map
map :: (a -> b) -> [a] -> [b]

That's interesting... it expects a function and a list, and returns a list. I'm thinking of PHP's array_map(). Lesh see. *plugs it in*

Code: Select all

Prelude> map length ["hello","world"]
[5,5]

Spot-on!

Code: Select all

filter :: (a -> Bool) -> [a] -> [a]

Expects a function that turns something into a truth value, and a list of somethings, and returns a list of somethings... hum. I'm thinking it returns all values from the [a] parameter for which (a -> Bool) is True.

At this point, I forgot about let. Damnit. Okay, once I remembered it:

Code: Select all

Prelude> let longer x = length x > 1
Prelude> filter longer ["h","el","lo!"]
["el","lo!"]

Spiffy. ^_^

Code: Select all

foldr :: (a -> b -> b) -> b -> [a] -> b

foldr expects three parameters:
- a function that expects two parameters, and returns a value of the type of the second parameter
- something that has the second parameter of the first parameter's function's type (yeesh, what a mouthful)
- a list of somethings with the type of the first parameter of the first parameter's function's type (just as bad!)

And returns something of the type of its second parameter.

*stare*
*stare*
*stare*

WTH?

*looks it up in the dictionary called Ari, marking this one as a fail, grumbling.*

foldr (+) 0 (map (+ 1) [1,2,3]) == foldr (+) 0 [2,3,4] == 9 -- the full meaning of this line will be explained later...

Applies the operator (+) [binary operator, thus a -> a -> a, which matches the condition a -> b -> b, though I'm not sure what one would want with the extra flexibility... or rather, why isn't it purely flexible, a -> b -> c? Why does the second parameter dictate the type?] on all elements of the list, successively... what's with the 0, though? What does that do - or, in this case, not do? Would it be added (or rather, first-parameter-ed) to the result?

Somehow, I don't feel much smarter (about foldr) just yet.

*hops to next lesson*

[Ari Rahikkala]

I've understood the syntax in that I've committed to memory, but for the life of me, no one has ever managed to explain to me why it's written like that. I know writing Integer -> (Integer -> Integer) is pretty much the same thing, but that's where any attempt at understanding the reasons behind the syntax fails me.

The reason is somewhat simple and deep. Let's see if I can explain it in a small space...

Think back to the lambdas. Let's take a trivial function definition as an example:

plus x y = x + y
plus = \x y -> x + y -- equivalent to the above

Now, imagine what happens when you try to call plus with a single argument. It's somewhat difficult to define a good behaviour for this case: Maybe the compiler should warn you for using the wrong number of arguments? That wouldn't be a very convenient thing to do, though - what if you want to give a function some of its arguments now and some later? Maybe we should look at the function definition in a different way:

plus = \x -> \y -> x + y

Now plus is a function of *one* argument that returns *another* function of one argument. For instance with simple rewriting,

plus 3 == \y -> 3 + y

The process of transforming a function of n arguments into a function of 1 argument returning a function of n - 1 arguments is called currying and Haskell does it automatically to all of your functions.

(even if that type will never hold a value, as far as I can tell)

But Integer -> Integer *is* inhabited by values, just as Integer -> Integer -> Integer is. One of them, for instance, is \y -> 3 + y. Now meditate on the connection between currying and the way types are written in Haskell .

Incidentally, this is part of the reason why I've tried to make it explicit that functions are just values that take arguments. You could just as well say that values are functions that take zero arguments. Also meditate on this.

I know you said you'd elaborate on it later, but: why doesn't the GHC give you the benefit of doubt about [Char] -> Bool? As in, what makes Integer special? At first I thought that maybe there is an internal mapping of Integer -> Bool for some values of Integer, e.g. 1 and 0, but not 1 and not 0 yield the same error message. So it begs the question what about the types is different.

Because typeclasses are open but datatypes aren't, i.e. wait for the next lesson .



I see I'll have a lot to tell about typeclasses soon enough . The next lesson will, therefore, contain a lot of information about them... and a lot of other enlightening stuff... but here's Possibly the Shortest Introduction Ever to the Forms of Polymorphism in Haskell:

Haskell has parametric polymorphism, which basically means using type variables. Things that are written with a small first letter in a type are type variables. In a way, a type variable stands for "something". By default, a type variable can be anything - it can be an Integer, it can (Eq a => a -> [a] -> Bool), it can be a computation whose effect is to make your computer play sounds. Because it can be absolutely anything, the language can't allow you to do anything with values of the type but refer to them and pass them on.

Typeclasses are a form of ad-hoc polymorphism, although a particularly nice form of it - if someone has told you that ad-hoc polymorphism isn't really useful, you really should go back and slap them in the face with typeclasses . Basically, where a type variable can stand for absolutely anything, typeclasses allow you to restrict its polymorphism - state that the variable can not actually be of just any type. If the language knows, for instance, that a type is in the class of things that are numbers, it can allow you to do numeric operations on it - which it would not have been able to do without restricting the type.

Several typeclasses are predefined in the Prelude. For instance, Eq is the class of things that can be compared for equality - thus, the type of (==), which is (Eq a => a -> a -> Bool) means "give me two things of the same type, that is a type that can be compared for equality, and I'll give you a truth value". Ord is the class of things that can be sorted, Num is the class of all numbers, Show is the class of things that can be shown, etc..

More on this, and especially your question about flexibility (and what these words that I've been using, "the same type", really mean), on the next lesson, which is to be released... soon, I hope. Probably tomorrow. I'm a bit too tired to write concise prose at the moment .

[Neike Taika-Tessaro]

Ari! You're around! <3

Haskell does it automatically to all of your functions.

Freaky. Okay, that's pretty much all I needed to know there. Thanks for the explanation.

Because typeclasses are open but datatypes aren't, i.e. wait for the next lesson .

But- *reads "wait for the next lesson"* Argh.

If the language knows, for instance, that a type is in the class of things that are numbers, it can allow you to do numeric operations on it - which it would not have been able to do without restricting the type.

So it is like 'parent of'. Gotcha. Again, this was the bit I needed to know. (But don't think I don't appreciate your elaboration! Au contraire.)

Why does Haskell make a difference between datatypes and typecl- argh, okay, I'll wait for the next lesson. *flexes fingers nervously*

Thanks for your answers.