Types in Haskell

If you take the example of

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

This means that map takes 2 arguments

  1. A function from type a to type b
  2. A list of type a

And it returns

  1. A list of b

You can already see the pattern here, but it'll be clearer when we substitute 'a' and 'b'

  • a = String
  • b = Int

So this type definiton will be

map :: (String -> Int) -> [String] -> [Int]

so now it's a function that takes a String and returns and Int, and a list of Strings and returns a list of Ints.

Say our function that takes a String and returns and Int is read. read uses the string you give it to convert it to something different. Because we put it into an Int context here, it will convert the string to int

map read ["1", "2", "112", 333"]

This will result in

[1, 2, 112, 333]

because map takes your function read and maps (applies) it to every element of the list. You don't have to TELL read it's argument like read "1", or read n, because map takes care of that for you.

And that's really all there is to it. The type of a function only says which types it takes and what type it returns. Of course, there's also currying, but you'll get to that later either on purpose or not! It basically means, that a function does not take many arguments, but only one. Say you take the function +. If you evaluate 1+2, it returns a function which takes another number which is added to 1, and because there IS another number here, 2, it will use that. You could have evaluated it as (1+) and pass it on, possibly added the number some time later. It is clearer when you don't have the infix syntax of +. It could have been written (+) 1 2, so first this statement becomes (+) 1 , which is of type (simplified! I won't introduce the Num typeclass here) Int -> Int. So (+) 1 (or (1+) for that matter) is just ANOTHER function you can apply a value to, at which point the result will be able to calculate to 3.

Here's how this looks in practice: (Ignore the (Num a) => part here if it confuses you, it's a concept you will later learn more about. Just replace the a types here with Int if you want, and ignore the (Num a) => part completly.)

 (+)  :: (Num a) => a -> a -> a
 (+2) :: (Num a) => a -> a
(1+)  :: (Num a) => a -> a
(1+2) :: (Num a) => a

Prelude> (+2) 5
7
Prelude> map (+3) [1,2,3]
[4,5,6]

And to your second question: you don't define inferred types AT ALL. They are called "inferred", because the compiler/interpreter "infers" (read: computes) the types itself, without you explicitly naming them.

About the foldX differences: They all do the exact same thing: reduce a list to a single value. The difference between the functions is merely the internal definition. foldl folds the list from the left, and foldr does it to the right.

So to sum up a list, you can use all of them like this...

foldl1 (+) [1,2,3] == 6
foldr (+) 0 [1,2,3] == 6
foldl (+) 0 [1,2,3] == 6

You see, except for foldl1, you supply a function to fold, a starting value (accumulator) and a list to fold. fold1 has it's own accumulator, you don't give it your own.

In practice, you should better use foldr, because unlike fold it's suitable for BIG lists without crashing due to a stack overflow (tee, hee). And exception to this rule is foldl' (notice the "'"!) in Data.Map - it's a strict fold that is also suitable for big lists.

If you want to give functions their types yourself (if you wrote them), consider this example:

double :: Int -> Int
double n = 2 * n

Or in a haskellish way

double :: Int -> Int
double = (*2)

The first line of both the examples (double :: Int -> Int) is what you're looking for. It's how you can force the compiler or interpreter to identify the function - you can omit then, and the compiler/interpreter will find them out (and sometimes even in a better way than one would first think of)


Functions in Haskell use a notation called currying. A definition like

plus :: Int -> Int -> Int

means that plus is a function that takes two Ints and returns a value of the the rightmost type (which is Int again). More into detail, currying means you work with partially applied functions which allows you to write code like

plus1 :: Int -> Int
plus1 = plus 1

Lowercase identifiers in type signatures indicate a so called type variable that can be thought as a place-holder for any possible type.

The definition

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

therefore means For any types a and b, map takes a function from a to b and a list of a's, from which it produces a list of b's.

Let's take an example

map show [1, 2, 3]

We see, the given list is a list of Int's, so a = Int. Furthermore, map should apply show to each element, which returns a String. Since show has to fit the type a -> b from the definition, we can deduce that b = String.

Our expression returns a [b], so the result is a [String].

To make such signatures even clearer, we can write it using a more verbose syntax

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

This now explicitly states map is supposed to work with all types a and b.


For the folds, take a look on their definitions. Given above knowledge, the type signatures should be self-explaining when it's clear what the functions are supposed to do.

Example: factorial n = foldl (*) 1 [1..n]

The signature of foldr map becomes.

foldr map :: [a] -> [a -> a] -> [a]

You can also obtain these by simply typing :t foldr map into the Haskell interpreter (GHCi).