haskell . quest

Caput Primum. De Functione Pura — concerning the pure function

function, pure of all worldly entanglement, is the smallest covenant in computation: given the same input, it returns the same output, and disturbs nothing. It does not log; it does not write to a file; it does not call across the wire. It is, in the precise sense the schoolmen meant, a relation — a fragment of the eternal multiplication table, looked up rather than performed.

You may protest that this is a poor sort of program. A program, you say, must do something. We answer: it does. It returns. The doing of computation in Haskell is the relation between what is said and what is meant; the rest, as we shall see in the seventh chapter, is plumbing. ‌

square 7

The function above promises a number and gives a number; it makes no promises about the world. Notice the rubric above the slab: it is the type signature, written in vermilion when the signature is the heart of the lesson. Read the colon-colon as has the type; read the arrow as becomes. ☞ ‌

double (square 5)

Compose two pure functions and you have a third pure function, larger than either, as honest as both. This compositionality — the property that the meaning of the whole is the meaning of the parts — is the lever upon which the rest of the language rests.

Caput Secundum. De Typo et Genere — concerning type and kind

ype, in this language, is a promise the compiler keeps. Where another tongue might let you add a number to a sentence and silently coerce one to the other, Haskell refuses: a value of type Int is not a value of type String, and the boundary is sacrosanct. The reward for this severity is a kind of liberty: when a program compiles, very large classes of error are already excluded.

add 19 23

Read Int -> Int -> Int right-to-left at first, then learn to read it left-to-right: given an Int, return a function that, given an Int, returns an Int. Every function in Haskell takes one argument; multi-argument functions are an illusion produced by stacking. This trick is called currying, after the logician. ‌

(add 5) 12

Apply add to a single number; what you have left is itself a function, awaiting its second argument. This is partial application, and it is the most quietly useful tool in the book. We shall see it again every chapter hereafter.

Caput Tertium. De Recursione — concerning recursion

ecursion is the way functional languages count, walk, search, and remember. Where the imperative writes a loop with a counter, the functional writes a function that calls itself on a smaller problem and trusts the base case to halt. The factorial is the canonical example, and it remains so because nothing else is quite as honest:

fact 6

The base case is the bottom step on the stair: fact 0 = 1. The recursive case is every other step: fact n = n * fact (n - 1). To trust recursion, you must trust the smaller problem. To trust the smaller problem, you must remember that someone — you, two minutes ago — already wrote the function. ‌

sumTo 10

Lists, in turn, are recursive by nature: a list is either empty or a head followed by another list. To consume a list is to write a function with two clauses, one per shape, and to let the structure of the data tell you the structure of the program.

len [1, 2, 3, 4, 5]

Caput Quartum. De Functoribus — concerning functors

unctor is a word the schoolmen would have understood: it is a thing that, when you apply a function inside it, gives you back a thing of the same shape, with the function having done its work upon the contents. A list is a functor; map is its proof. A Maybe is a functor; you may apply a function to its contents and the absence-or-presence is preserved.

map square [1, 2, 3, 4]

The shape is preserved; the contents are transformed. This is what every functor does, in every language, even when it is not given the name. The name is a gift the mathematicians made to programmers: by calling this what it is, you may now reason about it. ‌

fmap double (Just 21)

Caput Quintum. De Applicativis — concerning applicatives

pplicative functors permit the function itself to live inside the box. Where the plain functor maps a function over a contents, the applicative may take a function-in-a-box and apply it to a value-in-a-box, producing a result-in-a-box. The mechanism is the operator <*>, pronounced ap, and it is gentle.

pure 42

pure lifts a value into the smallest box that will hold it. For Maybe, that is Just. For lists, it is the singleton list. The applicative class promises both pure and ap, and it asks you to obey four small laws.

Caput Sextum. De Monadibus — concerning monads

onads are the chapter every Haskell book is too eager to begin with and too late to finish. We will be brief, because brevity is the only honest way: a monad is a functor with a way of flattening. If you have a box-of-a-box, the monad lets you collapse it to a single box. The operator is >>=, pronounced bind.

safeDiv 84 2

The monad is not a metaphor about burritos, nor about boxes, nor about programmable semicolons, although it is gently each of these. It is, more honestly, the smallest interface that lets you sequence computations whose later steps depend on the results of their earlier steps. The do-notation is sugar; the bind is the substance. ‌

Caput Septimum. De IO — concerning the world

IO is the chapter where the world enters the manuscript. A pure function does not print; an IO action does. The trick of Haskell is that the world is itself a value, threaded through the program by the IO monad, and the compiler makes certain that the threading is done in order. Effects do not leak; they are listed.

greet "pilgrim"

We render here only the pure portion of an IO program; the printing is left to the run-time. But notice the shape: the same arrow notation, the same composition, the same purity in the parts. The world is added at the very last moment, and only at the boundary that is named main.

Caput Octavum. De Lazinitate — concerning laziness

aziness, in this language, is not vice but virtue: an expression is not evaluated until its value is required. This permits infinite data structures, which would terminate any strict language at once, but which here merely sit on the page like a quiet library, consulted page by page rather than read end to end. The list [1..] is a perfectly fine inhabitant of memory.

take 5 [10, 20, 30, 40, 50, 60, 70]

With take we can ask for only as much of an infinite list as we need, and the rest never inconveniences us. The reader will, in time, find this idiom less surprising than its absence in other languages. It is, in any case, why the demon ⊥ sleeps so peacefully in the margin: he is here, but he need never be summoned. ‌

head (take 3 [100, 200, 300, 400])