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)