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)

Further reading

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

© Antoni Diller (24 September 2021)