How to analyse a function in Haskell?

Question

Hi everyone Haskell newbie here. I'm really confused about how to look at a curried function.

For example, here is a function definition

zipWith' :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith' _ [] _ = []
zipWith' _ _ [] = []
zipWith' f (x:xs) (y:ys) = f x y : zipWith' f xs ys

When I call

zipWith' (zipWith' (*)) [[1,2,3],[3,5,6]] [[3,2,2],[3,4,5]]

I understand that

zipWith' :: (a -> b -> c) -> [a] -> [b] -> [c]

is equivalent to

zipWith' :: (a -> b -> c) -> ([a] -> ([b] -> [c]))

But what I don't understand is the way/order to look at it. Should we analyse it from left to right? Such as look at the (a -> b -> c) first and then apply the [a] in to the (a -> b -> c) and lastly apply ([b] -> [c]) into (a -> b -> c) -> [a]? Or is it the other way round?

And if you don't understand what I'm asking (sorry :( ), could you just show me how you think when you see this kind of problems? I freak out whenever I see these functions and it usually takes me a while to figure out :P

Answer 1

Left to right.

In fact you can see it with 4 different point of view

zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
--  take a function, 2 list and returns a list
zipWith (*)  :: [a] -> [b] -> [c]
-- new function which takes 2 list and returns a new one
zipWith (*) [1,2,3] :: [b] -> [c]
-- new function which takes a list a produce a new one
zipPwith * [1,2,3] [3,5,6] :: [c]
-- a function without argument, or a value (equivalent in Haskell)

Or right to left :-)

zipPwith * [1,2,3] [3,5,6] :: [c]
-- a function without argument, or a value (equivalent in Haskell)    
zipWith (*) [1,2,3] :: [b] -> [c]
-- new function which takes a list a produce a new one 
zipWith (*)  :: [a] -> [b] -> [c]
-- new function which takes 2 list and returns a new one 
zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
--  take a function, 2 list and returns a list

Answer 2

In this case it might be helpful to think of the nested lists as (2-dimensional) matrices.

A =  ( 1 2 3 )   B =  ( 3 2 2 )  -->  result = ( 3  4  6 )
     ( 3 5 6 )        ( 3 4 5 )                ( 9 20 30 )

The outer zip' combines the rows from A and B and the inner zip combines a pair of rows into another row, and so it is clear the result will have the same shape as the inputs.

It also might be helpful to realize that zipWith (*) is just component-wise multiplication of vectors. In fact there is a pattern:

zipWith (*)                     -- component-wise * on 1-d matrices
zipWith (zipWith (*))           -- component-wise * on 2-d matrices
zipWith (zipWith (zipWith (*))) -- component-wise * on 3-d matrices
...

and of course (*) can be replaced by any binary operation.

Some other list functions and their matrix interpretations:

• map - iterate over all of the rows
• transpose - transpose rows and columns
• concat - flatten the first dimension (i.e. all rows into a single row)

As an exercise you might try implementing matrix multiplication with list operations.

Answer 3

So, let's start with zipping function. It's type is a -> (b -> c). It takes as a parameter of type a, and returns function which transforms b to c. It is isomorphic to it's uncurried equivalence (a, b) -> c, the difference is that we fix first parameter, to get function which now requires only b to return c.

So this is what the zipper's type mean. Now let's move on to zipWith'. It takes as a parameter zipping function (explained above). It returns something of type [a] -> ([b] -> [c]), which is pretty similiar to zipper function. We can say that zipWith' lifts zipping function to work with lists -zipWith' returns a function witch takes a list of as, and returns function which takes list of bs and returns list of cs.

In your example we have zipWith' (*). For simplicity assume that (*) is of type Int -> (Int -> Int) (in reality it is more general - (Num a) => a -> (a -> a). Then we have a ~ b ~ c ~ Int and zipWith' (*) :: [Int] -> ([Int] -> [Int]). Then zipWith' (*) takes as a parameter a list of Ints and returns a function which transforms one list of Ints to another. So it can be used to zip two lists of lists of as. And this is exactly what happens.

Answer 4

Curried functions look scarier than they are. One way of thinking about how they work is uncurrying them. For instance:

(++) :: [t] -> [t] -> [t]

Becomes, when uncurried:

(++) :: ([t], [t]) -> [t]

In my eyes, that's all the explanation needed, but here's a more detailed one, that might explain it fully:

A function of type a -> b takes an argument of type a and returns an argument of type b. Remember that a -> b is in itself a concrete type and could take the place of b in the first, making a function of something like a -> (b -> c).

Let's say that a function f is of type a -> b -> c, which is as above. What does that mean? It is a function that returns a function! That is how currying works. The idea of functions returning other functions allows us to partially apply functions, limiting or specifying their traits.

---

Let's now make our own function specifying that:

func :: a -> [a] -> [a]
func = \elem -> ( \list -> elem : list )

The lambda expressions here have been written in such a way that it should be obvious what the type means: the first lambda (\elem -> ...) constructs the other based on it's input.

---

Now, let's have a look at zipWith:

zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]

The first argument to zipWith is a function, which in itself takes two arguments. Not too crazy.

The second argument is a list which can be passed to the function, because of the type variables defined.

The third argument is another list that can be passed to the function after the first.

The return value is a list of the resultant type of the function we passed to zipWith first.