# Unit 7: Tuples

## Introduction

The list is the main datatype used in a functional programming language, but, in Haskell, all the elements of a list have to be of the same type. Sometimes you need to make use of structured objects that contain components belonging to different types. Tuples fit the bill in Haskell. They can have two or more members and are written using parentheses. Here are some examples with their types:

``````("height", 7) :: ([Char], Int)
(10, 30, "time") :: (Int, Int, [Char])
(True, "eat", 8) :: (Bool, [Char], Int)
``````

Note that tuples can be nested, thus `((True, "eat"), 8)`, but note also that this is not the same as `(True, "eat", 8)`. The tuple `((True, "eat"), 8)` has two components, one of which is itself a tuple, whereas `(True, "eat", 8)` has three components. Two useful functions defined on tuples of length two are `fst` and `snd` which extract the first and second components, respectively:

``````fst :: (a,b) -> a
fst (x,_) = x

snd :: (a,b) -> b
snd (_,y) = y
``````

Tuples can be used inside ZF-expressions:

``````[ (x, y) | x <- [1, 2, 3], y <- "st" ]
``````

This evaluates to:

``````[ (1, 's'), (1, 't'), (2, 's'), (2, 't'), (3, 's'), (3, 't') ]
``````

## Quicksort revisited

Tuples have many uses. One of them is to enable you to define functions which return values that contain several pieces of information. For example, a more efficient version of Quicksort can be defined by using the function `split`:

``````split :: Ord a => a -> [a] -> ([a],[a])
split x [] = ([], [])
split x (y:ys)
| y < x     = (y:less, greater)
| otherwise = (less, y:greater)
where (less, greater) = split x ys
``````

Quicksort can now be defined as follows:

``````quick :: Ord a => [a] -> [a]
quick [] = []
quick [x] = [x]
quick (x:xs) = quick less ++ [x] ++ quick greater
where (less, greater) = split x xs
``````

## The function `zip`

The function `zip` takes two lists as its arguments and produces a list of tuples as its value. The ith tuple contains the ith elements of the two lists. The function `unzip` reverses this operation. Some examples should make the idea clear:

``````zip [7, 8, 2] "cat" = [(7, 'c'), (8, 'a'), (2, 't')]
zip [5, 1, 3, 4] "on" = [(5, 'o'), (1, 'n')]
unzip [(True, 8), (False, 3), (True, 11) ]
= ([True, False, True], [8, 3, 11])
``````

To illustrate the usefulness of `zip` consider the following problem: Calculate the scalar product of two vectors. In other words, define a function `sp` which does the following:

``````sp [x1, x2, ..., xn] [y1, y2, ..., yn]
= x1 * y1 + x2 * y2 + ... + xn * yn
``````

I will present the solution in several stages. Step 1:

``````  zip [x1, x2, ..., xn] [y1, y2, ... , yn]
= [(x1, y1), (x2, y2), ..., (xn, yn)]
``````

Let `xs` be `[x1, x2, ..., xn]` and `ys` be `[y1, y2, ..., yn]` and `times (x, y)` be `x * y`. Then step 2 is:

``````map times (zip xs ys) = [x1 * y1, x2 * y2, ..., n * yn]
``````

Step 3:

``````sum (map times (zip xs ys)) = x1 * y1 + x2 * y2 + ... + xn * yn
``````

Thus, the solution is:

``````sp :: Num => [a] -> [a] -> [a]
sp xs ys = sum (map times (zip xs ys))
where times (x, y) = x * y
``````

As another example of the usefulness of `zip` consider the following problem: Decide whether or not a list is in non-decreasing order. In other words, define a function `nondec` which does the following:

``````  nondec [x1, x2, ..., xn]
= x1 <= x2 && x2 <= x3 && ... && xn-1 <= xn
``````

I will present the solution in several stages. Step 1: Let `xs` be `[x1, x2, ..., xn]`. Then we have:

``````zip xs (tail xs) = [(x1, x2), (x2, x3), ..., (xn-1, xn)]
``````

Step 2: Define `leq (x, y) = x <= y`. Then we have:

``````  map leq (zip xs (tail xs))
= [x1 <= x2, 2 <= x3, ... , xn-1 <= xn]
``````

Step 3:

``````  and (map leq (zip xs (tail xs))
= x1 <= x2 && x2 <= x3 && ... && xn-1 <= xn
``````

So, the solution of the problem is as follows:

``````nondec :: Ord a => [a] -> Bool
nondec xs = and (map leq (zip xs (tail xs)))
where leq (x, y) = x <= y
``````

## Currying

In Haskell all prefix functions are one-place ones, but mathematicians often use functions that take two arguments like `f(x, y) = x + 7xy + 3y`. Currying is the process by which a two-place function can be represented by a one-place one. To illustrate the idea consider these two definitions:

``````minof2 :: Ord a => a -> a -> a
minof2 x y
| x <= y    = x
| otherwise = y

mint :: Ord a => (a, a) -> a
mint (x, y)
| x <= y    = x
| otherwise = y
``````

The function `mint` isn't really a two-place function. It is a one-place function whose argument is a two-tuple. However, it well mimics the mathematician's two-place function as substituting a value for `x`, say, but not also for `y`, does not result in a coherent expression, whereas substituting a value for `x` in `minof2` does: `minof2 83`, for example, is a coherent expression that could be supplied as an argument to `map`. Currying is the process of turning a two-place function into a one-place one and Haskell contains the predefined functions `curry` and `uncurry` which mimic currying and uncurrying:

``````curry :: ((a, b) -> c) -> a -> b -> c
curry f x y = f (x, y)

uncurry :: (a -> b -> c) -> (a, b) -> c
uncurry g (x, y) = g x y
``````

Using `curry` and `uncurry` the functions `minof2` and `mint` can be defined in terms of each other:

``````minof2 = curry mint
mint = uncurry minof2
``````

## The function `zipWith`

In order to explain how `zipWith` works it will be useful to have uncurried versions of the operators `*` and `<=`. These can be defined like this:

``````times (x, y) = x * y
times = uncurry (*)

leq (x, y) = x <= y
leq = uncurry (<=)
``````

The function `zipWith` is defined as follows:

``````zipWith op xs ys = map (uncurry op) (zip xs ys)
``````

To see why `zipWith` is useful, recall the definitions of the scalar product of two vectors `sp` and the function which determines whether or not a list of numbers is in non-decreasing order `nondec`:

``````sp xs ys = sum (map times (zip xs ys))
where times (x, y) = x * y
nondec xs = and (map leq (zip xs (tail xs))
where leq (x, y) = x <= y
``````

Using `zipWith` these can be defined more concisely like this:

``````sp xs ys = sum (zipWith (*) xs ys)
nondec xs = and (zipWith (<=) xs (tail xs))
``````

Using `zipWith` the memoised definition of the Fibonacci numbers can be made even more elegant:

``````fiblist = 0 : 1 : zipWith (+) fiblist (tail fiblist)
``````

More information on `zip` can be found in section 4.4, "Zip", pp. 116–120, of Bird, Introduction to Functional Programming using Haskell (1998). More information on `curry` can be found in chapter 1 of the same book.