zip function requires also a second list, how can

Question

I started learning Haskell and found a nice exercise. It's the following:

grouping: Int -> [Student]->[(Team, Student)]
grouping teamNumber = zip ys
                      where ...

So, the exercise wants that i try to fill the rest. The function should do the following: Example : grouping 2 ['Mark','Hanna','Robert','Mike','Jimmy'] = [(1,'Mark'),(2,'Hanna'),(1,'Robert'),(2,'Mike'),(1,'Jimmy')].

So, we are building teams which consists of two Students, and the last Student 'Jimmy' has no teammates.

Then, I also look up what the predefined function zip does. It gets two list arguments and connects each element of the lists to a tuple to build a list of tuples.

My idea: 1) I try to build two functions "grab" and "infinite". They are looking as following:

grap :: Int -> [a] -> [a]
grab _ [] = []
grab n (x:xs) = if n <= 0 then [] else x : grab (n-1) xs  

infinite :: Num a => a -> [a]
infinite x = x : infinite(x+1)

So, what they do is: With infinite I want to create an infinite list. And grap should take n elements of that. Example grap 2 (infinite 1) = [1,2].

I use these two in the first line of my where-declaration to fulfill the given function from above. So, I have:

grouping: Int -> [Student]->[(Team, Student)]
grouping teamNumber = zip ys
                      where 
                      xs = grap teamNumber (infinite 1)

So, xs is now my first list of zip, especially the integer-list.

But now my question: zip as predefined function requires also a second list, especially the list of the names of the students, but in the given function they give zip only one argument, namely the ys as a list. How can I understand that?

Answer 1

Currying can be a bit confusing when you first encounter it. Here's the deal, pretty much (there are some technicalities I'm going to ignore).

The basic concept is this: in Haskell, every function takes just one argument. If you want to simulate a function that takes two arguments, there are two ways to do this:

Tuples

You can write a function that takes a tuple. This is the conventional approach in Standard ML, but is typically only used in Haskell in cases where it is very particularly the most sensible thing to do:

distanceFromOrigin :: (Double, Double) -> Double
distanceFromOrigin (x, y) = sqrt (x^2 + y^2)

Currying

You can write a curried function. The concept behind currying is that when you apply a function to an argument you can get another function back that takes a second argument. I'll write this out very explicitly to begin with, using lambda notation:

product :: Double -> (Double -> Double)
product x = \y -> x * y

Suppose I start with (product 3) 4. I can reduce (product 3) first to get

(\y -> 3 * y) 4

Then I can finish off the job, getting 12.

Haskell offers a bit of syntax to help with this sort of thing. First off, it lets me write

product x y = x * y

to mean

product x = \y -> x * y

Secondly, it makes function application left-associative, so I can write product 3 4 to mean (product 3) 4.

Finally, it makes the -> type constructor right-associative, so I can write product :: Double -> Double -> Double instead of product :: Double -> (Double -> Double).

Answer 2

In Haskell, the following is equivalent:

f = (\x      y -> ..x..y..  )
f = (\x -> (\y -> ..x..y.. ))  -- this equivalence is known as "currying"
f     x =  (\y -> ..x..y.. )   -- partially applying f with x gives (\y->...)
f     x      y =  ..x..y..

((\x -> ...) is of course Haskell's notation for anonymous, so called "lambda" functions (\ being a reminder for the Greek letter λ.)

In Haskell, functions are just like other values, so there's no special syntax for function calls, or "function pointers" etc.. As for the types, the above naturally entails

f ::  a ->   b ->   t
f     x ::   b ->   t  -- the result of calling f w/ x (of type a) has type b->t
f     x      y ::   t  -- when f :: a->b->t, x :: a, y :: b, then f x y :: t

Stare at it for a moment.

So that's that about currying. Function calls are denoted just by juxtaposition in Haskell, and so it associates to the left (f x y is really ((f x) y)). And because Haskell definitions are automatically curried, the arrows in types associate to the right (a->b->c is really a->(b->c)).

Answer 3

Type of `grouping teamNumber`

Look carefully at the type of grouping :: Int -> [Student]->[(Team, Student)], and the arguments that are being declared for its declaration

grouping :: Int        -> [Student]->[(Team, Student)]
grouping    teamNumber =  ...

What is the return type (the type on the right-hand side of the equals sign) if grouping is provided with all the arguments listed on the left-hand side of the equals sign?

Answer

The type on the right-hand side of the equals sign is [Student]->[(Team, Student)]. In Haskell, a function that takes two arguments and returns a result can be equivalently seen or defined as a function that takes the first argument and returns a (function that takes the second argument and returns the result). So we could say, for example, that the expression

grouping 3 :: [Student]->[(Team, Student)]

(grouping 3) is a function that takes a list of students and returns a list of those students, labeled in 3 groups. Presumably, if (grouping 3) were applied to the list of students from your example, we would have

(grouping 3) [   'Mark' ,   'Hanna' ,   'Robert' ,   'Mike' ,   'Jimmy' ] =
             [(1,'Mark'),(2,'Hanna'),(3,'Robert'),(1,'Mike'),(2,'Jimmy')]

Type of `zip ys`

What does currying have to do with the following type and expression?

zip :: [a] -> [b] -> [(a, b)]
zip    ys

What would the type of zip ys be if, for example, ys :: [Bool]?

What does this have to do with your question?

When you consider this together with the type of grouping teamNumber, how does this tell you what the type of ys needs to be in your exercise?

Putting it all together

From the exercise code (ignoring the types and the where clause) we have:

grouping teamNumber = zip ys

Two things can only be = in Haskell if their types will unify. In this case, the type of grouping teamNumber must unify with the type of zip ys.

From the first part, we know that the type of grouping teamNumber is [Student]->[(Team,Student)].

From the second part, we know that zip ys has the type [b] -> [(a, b)], where a is a type such that ys has the type [a].

Therefore, we know that (~ is type equality in Haskell)

[Student]->[(Team,Student)] ~ [b] -> [(a, b)]

These will unify if we substitute the following for the type variables b and a

b ~ Student
a ~ Team

Now, we know the type of ys is [a], which, if we make the same substitution, is [Team].

Therefore, the types will be correct if ys :: [Team].

Conclusion

If you can provide a ys :: [Team], you can produce a function from students to students tagged with their team ([Student]->[(Team,Student)]) by passing the ys as the first argument to zip. Such a function is exactly what grouping needs to return when it has been applied to the single argument, teamNumber :: Int.