1 Functions Types, Currying, Partial application, Higher-order functions

All functions have a type, the function type:

length :: [a] -> Int
length [] = 0
length (x:xs) = 1 + length xs

The same way we think about the Either type constructor, and about the tuple type constructor (,), we can think about the function type type constructor (the arrow ->). They are all type constructors that take two arguments.

data Either a b = Left a | Right b

data (,) a b = (a, b)     -- pseudo code

data (->) a b = a -> b    -- pseudo code

This means that the (->) type constructor, when applied to two types a and b, creates a new type a -> b, where a is the input type and b the return type.

This beggets the question, what is the type of a function that takes two arguments? There are two ways to define multi-argument functions.

The first would be to think about functions that receive multiple arguments in a tuple.

prepend :: (Char, String) -> String
prepend (c, str) = c:str

You could even use it like this prepend('h', "ello"), which somewhat resembles the imperative style function call.

The second option is to have a function take one argument a, and return a function that takes another argument b and only then returns c.

prepend :: Char -> (String -> String)
prepend c = (\str -> c:str)

And this is the most common way to have multi-argument functions in functional programming languages. In Haskell, thinking about two argument functions and functions that return functions is really the same thing.

The most common way of writing the two argument function prepend in Haskell, read “prepend is a function that takes two arguments of type Char and String and returns String”, would be

prepend :: Char -> String -> String
prepend c str = c:str

The (Char, String) -> String version is said to be an uncurried function, while Char -> String -> String is said to be curried.

An advantage in using curried functions is the possibility to partially apply them.

We can define a new function that always prepends B in terms of prepend by partially applying prepend (that is, applying the function to a partial number of arguments)

prependB = prepend 'B'

Partial application is useful in everyday functional programming; A common example is passing partially applied functions to functions that take functions:

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

-- Given a list of strings, prepend C to them all
prependAll :: [String] -> [String]
prependAll strs = map (prepend 'C') strs

In functional programming, functions are first-class, meaning they can be passed as parameters and returned from functions. Functions used in those ways are said to be higher-order functions

As an end note on function types, notice that the “correct use” of -> type constructor is enforced by the kind system, the same way the usage of Either is enforced by the kind system. The kinds of these type constructors are:

type Either :: * -> * -> *
type (,)    :: * -> * -> *
type (->)   :: * -> * -> *

To have a function type we must supply both type arguments to the -> type constructor (i.e. Int -> Char is a valid type), but what happens if we partially apply the type constructor?

type (->) Int :: * -> *

type FunctionFromInt = (->) Int

type FunctionFromInt Char :: * -- equivalent to `Int -> Char`

2 Laziness

This section derives from A Gentle Introduction to Haskell

Suppose bot is defined by:

bot = bot

In other words, bot is a non-terminating expression. Abstractly, we denote the value of a non-terminating expression as |. Expressions that result in some kind of a run-time error, such as 1/0, also have this value. Such an error is not recoverable: programs will not continue past these errors.

A function f is said to be strict if, when applied to a nonterminating expression, it also fails to terminate. In other words, f is strict iff the value of f bot is bot. For most programming languages, all functions are strict. But this is not so in Haskell.

As a simple example, consider const1, the constant 1 function, defined by:

const1 x = 1

The value of const1 bot in Haskell is 1. Operationally speaking, since const1 does not need the value of its argument, it never attempts to evaluate it, and thus never gets caught in a nonterminating computation. For this reason, non-strict functions are also called lazy functions, and are said to evaluate their arguments lazily, or by need.

Another way of explaining non-strict functions is that Haskell computes using definitions rather than the assignments found in traditional languages. Read a declaration such as

v = 1/0

as define v as 1/0 instead of compute 1/0 and store the result in v. Only if the value (definition) of v is needed will the division by zero error occur. By itself, this declaration does not imply any computation. Programming using assignments requires careful attention to the ordering of the assignments: the meaning of the program depends on the order in which the assignments are executed. Definitions, in contrast, are much simpler: they can be presented in any order without affecting the meaning of the program.

3 Recursion: Inductive Method

Inspired on AMD - Teórica 3.

A well defined recursive function does case analysis over its parameters.

The base cases are the ones that don’t lead to recursive calls of the function. The general cases are those that lead to, directly or indirectly, recursive calls of the function.

The inductive method helps the programmer reason about the logical properties of the problem to solve: * The trivial case should be dealt with trivially * The general case should be dealt with by reducing the problem to a simpler problem When reducing the problem to a simpler one, assume the simpler one is already solved, and try to form the result based on that answer. In practice, the simpler problem is solved by the recursive call.

fact 0 = 1
fact n = n * fact (n-1)

length [] = 0
length (x:xs) = 1 + length xs

Analysing these recursive functions, we note that when dealing with the general case (the non-trivial case), they both reduce the original problem to a simpler instance of the same problem. the length function reduces the original problem length (x:xs) to the simpler length xs, and the function fact reduces the problem fact n to the simler problem fact (n-1).

Assuming the simpler problem is already solved (what is the length of xs?), we can just think about the step to take to the solution, which is add 1 to the recursive call result.

4 Recursive data structures

Data structures can use themselves to define themselves, or in other words, define themselves recursively. When they do so, they can be called recursive data types.

data Tree a = Leaf | Node a (Tree a) (Tree a)

A Tree here is defined in terms of other Trees. A Tree of as can be either a Leaf or a Node with a value of type a and two subtrees.

Recursive data types are expressive kinds of structures and a very idiom in functional programming. For example, we can clearly express a simple calculator language through a recursive data type Expr.

data Expr = Const Int
          | Add Expr Expr
          | Mult Expr Expr

This way, we can represent numerical expressions in through our datatype:

-- 5
Const 5

-- 6 * 2
Mult (Const 6) (Const 2)

-- 2 + 3 * 4
Mult (Add (Const 2) (Const 3)) (Const 4)

And easily define recursive operations on it:

calculate :: Expr -> Int
calculate (Const i) = i
calculate (Add x y) = calculate x + calculate y
calculate (Mult x y) = calculate x * calculate y

Because of Haskell’s laziness, we can even make infinite values of this recursive type.

Write a function that creates an infinite tree of length n given n :: Int

infiniteTree :: Int -> Tree a
infiniteTree = undefined

What about an expression that infinitely adds n?

-- infiniteAdd 5 <=> 5 + 5 + 5 + ... + 5 + ... + 5 + ...
infiniteAdd :: Int -> Expr
infiniteAdd = undefined

One can then write functions to make use of these infinite structures. For example, a function that given an infinite expression of adding n, adds n k amount of times (that is, a function that multiplies n by k through creating an infinite addition expression).

The most common example of an infinite structure is the infinite list and operations on it

[1..] -- [1,2,3,4,5,6,7......

take 5 [1..] -- [1,2,3,4,5]

Could you write a generator of infinite lists starting at n?

data List a = Nil | Cons a (List a)

infList :: n -> List a
infList = undefined

5 Type Classes

Previously we saw parametric polymorphism, and how a function needed to treat the polymorphic types agnostically, that is, the polymorphic type could be instanced by any type and the expression would still be valid. A common example is the map function

map :: (a -> b) -> [a] -> [b]
map _ [] = []
map f (x:xs) = f x:map f xs

In which the elements of the list are treated agnostically – they could have any type and this function would still typecheck.

Sometimes, however, we desire a function to be polymorphic over just some types, for example, a function polymorphic over all types for which equality (==) is defined.

We don’t want to define multiple equal functions just with different types, neither do we want a fully polymorphic function because equality isn’t defined for all types (e.g. the Exprs we created previously).

allEqual1 :: [Int] -> Bool
allEqual2 :: [Char] -> Bool
allEqual3 :: [Bool] -> Bool
allEqual4 :: [a] -> Bool -- how to compare a?

That’s where type-class polymorphism (also known as ad-hoc polymorphism) comes into play. We can define a type class which corresponds to a set of types which have certain operations defined for them, and we can define type-class polymorphic functions which can only be called on types which instance the said type-class.

Let’s define a type class for equality. Any type that instances this type class Eq, or in other words, any type that belongs to the set of types that support the equality comparison (==), well, can be compared using ==.

      + --- class name
      |
      v
class Eq a where
    (==) :: a -> a -> Bool
      ^
      |
      + --- operation that must be defined for all instances of `Eq`

We can then define type-class polymorphic functions such as allEqual, which take a polymorphic type a, as long as a instances Eq (Eq a => a).

             + -- Constraint
             |          + -- Function type, where `a` must instance `Eq`
             v          v
            _____   ___________
allEqual :: Eq a => [a] -> Bool
allEqual [] = True
allEqual [x] = True
allEqual (x:y:xs) = x == y && allEqual xs

If we then called allEqual on a list of Expr, it still wouldn’t work – that’s because Expr doesn’t instance Eq (how do you compare two Expr?)

allEqual [Const 5, Const 5, Add (Const 6) (Const 7)]

To define an instance of a type class for some type, we use the instance keyword in the following way:

         + --- class name
         |   + --- instancing type
         v   v
instance Eq Expr where
 -- (==) :: Expr -> Expr -> Bool
    (==) x y = case (x,y) of
        (Const i, Const j) -> i == j
        (Add z w, Add k p) -> z == k && w == p
        (Mult z w, Mult k p) -> z == k && w == p
        (_, _) -> False

After which allEqual [Const 2, Const 2] would return True.

6 Type Classes Kinds, Constraints

Let’s begin with this set up

data Box a = MkBox a

class Eq a where
    (==) :: a -> a -> a

allEqual :: Eq a => [a] -> Bool

And now let’s revisit kinds. The kind of a simple type such as Int, is *. The kind of a type constructor such as Box is * -> * The kind of a type constructor applied to a type, such as Box Int is *.

type Int :: *
type Box :: * -> *
type Box Int :: *

Now imagine there existed a kind called MagicalKind, and we could define type operators that returned types of this kind

type Magic :: * -> MagicalKind

The Magic type operator receives a * and returns MagicalKind. * is a kind, MagicalKind is a kind, and their combination through the kind arrow (->) is also a kind.

If we applied Magic to some type, say, Int, we’d get something of kind MagicalKind.

type Magic Int :: MagicalKind

There are other kinds besides * and kinds constructed with ->. There exists an important kind called Constraint, and there exist type operators that return types of kind Constraint.

Those type operators are defined through type classes. Our Eq class has a kind:

type Eq :: * -> Constraint

Which means that Eq applied to Int, Eq Int, has kind Constraint.

It’s the kind system that enforces the correct usage of constraints and type classes. Going back to the set up of this section, how could we create an instance of Eq for Box?

instance Eq Box where
    (==) = undefined

This would actually not compile! Why? Let’s inspect the kinds.

type Eq :: * -> Constraint
type Box :: * -> *
type Box a :: *

When we write Eq Box, Eq is expecting a type of kind *, but we pass it Box of kind * -> *!

A correct instance could be formulated as follows

instance Eq (Box a) where
    (Box x) == (Box y) = True -- We define two boxes to be always equal

Now, Box a has kind *, and so Eq (Box a) is correctly formulated.

Finally, let’s look at the Constraint kind. When defining a type class polymorphic function, we use the => symbol. On the left side of the symbol we must have constraints, and on the right, types. The kind system also enforces this.

allEqual :: Eq a => [a] -> Bool

This is a correct function definition. Eq a has kind Constraint, and so it can comfortably sit on the left side of =>. If we were, however, to write

allEqual :: Box a => [a] -> Bool

We’d get an error complaining about how Box a should have kind Constraint, but in reality has kind *.

Suggested reading: Type Classes