Types in Haskell

Question

I'm kind of new in Haskell and I have difficulty understanding how inferred types and such works.

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

What EXACTLY does that mean?

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

What are the differences between these?

And the inferred type of

foldr map is [a] -> [a -> a] -> [a]

But why is it that?

THANKS!

Answer 1

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)

Answer 2

In Haskell, a lower case variable is a type variable. Whereas Char just means Char, a or b could mean Char, or Bool or Integer, or some other type. The key is, all as will be the same type. And all bs will be the same type.

For example, map takes as its first argument a function which takes one variable of type a and returns another of type b. Then map returns a new function which takes a list of type a. This new function returns a list of type b.

Suppose you had a function increment which added one to an integer. map increment [1,2,3] would ultimately return a list [2,3,4].

The earlier definition of map with the type variables replaced would look like:

map :: increment -> [1,2,3] -> [2,3,4]

and increment, BTW, would look like

increment :: Integer -> Integer

The reason it is written funny is because you can partially apply functions. Here I'll make a new function based on the partial applicaiton of map:

incrementList = map increment

Then you could use

incrementList [1,2,3]

which would produce the same result

Answer 3

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).

Answer 4

The lowercase letters in the type declarations are type variables. This means that when there is an a this must be the same type.

Bracketed (eg (a -> b)) subexpressions tend to mean that the function accepts a function as one of its parametres.

Rectangular brackets indicate a list of something.

So map accepts these arguments:

• (a -> b) a function that accepts one argument
• [a] a list that the first argument function can act on

and produces [b] a list as a result.

We can decode (.) the same way:

• (a -> b) is a function that accepts a single argument
• (c -> a) is a function that produces the same typa as the argument to the first function
• c an argument of the same type that the second function uses

However Haskell can do a neat thing and that is if you omit an argument it returns a function that has the remaining signature. So (.) is commonly used to chain functions.

Let's say we have 2 functions ord :: Char -> Int which takes a character and returns it's integer representation and add32 :: Int -> Int that adds 32 to it's argument.

When we write upcaseVal = add32 . ord the function upcaseVal now has the signature upcaseVal :: Char -> Int because the (.) function would have left it with c -> b and we substitue thes in the function definition.

So foldr map would have to be like this:

1. foldr's first argument is a function that takes 2 arguments which map is.
2. Since the functions output has to be of the same type as the second argument ((a -> b -> b) we see that in map a = b

Thus the final type will be:

(b -> b) -> [b] -> [b] -> b -> [b] -> b

But I guess that doesn't have to bother you that much since the compiler deals with stuff like this most of the time.