Wadler's Blog

Here are analogues of sum, product, and exponentiation for lists. Each takes two lists of values, of types a and b, and forms the list of all values of sum, product, and function (exponent) types.

type Sum a b = Either a b
type Prod a b = (a,b)
type Exp a b = [(b,a)] -- represents functions from b to a

(+++) :: [a] -> [b] -> [Sum a b]
xs +++ ys = map Left xs ++ map Right ys

(***) :: [a] -> [b] -> [Prod a b]
xs *** ys = [ (x,y) | x <- xs, y <- ys ]

(^^^) :: [a] -> [b] -> [Exp a b]
xs ^^^ [] = [ [] ]
xs ^^^ (y:ys) = [ (y,x):e | x <- xs, e <- xs^^^ys ]

The first two of these are already built-in to Haskell, in the form of append and list-comprehensions. The third is also quite useful, and I suggest it should be added to the standard List module. For example, if you want to form a truth table for the list of variables in names, your can do so using [True,False]^^^names to form all 2^n mappings of names to truth variables (where n is the length of names).

In case you doubt whether these actually correspond to sum, product, and exponentiation, here are Peano's definitions:

m+0 = m
m+(n+1) = (m+n)+1

m*0 = 0
m*(n+1) = (m*n)+m

m^0 = 1
m^(n+1) = (m^n)*m

And here are the above operations, rewritten to correspond to Peano's definitions:

(+++) :: [a] -> [b] -> [Sum a b]
[] +++ ys = map Right ys
(x:xs) +++ ys = Left x : (xs +++ ys)

(***) :: [a] -> [b] -> [Prod a b]
[] *** ys = []
(x:xs) *** ys = map f (ys +++ (xs *** ys))
  where
  f (Left y) = (x,y)
  f (Right p) = p

(^^^) :: [a] -> [b] -> [Exp a b]
xs ^^^ [] = [ [] ]
xs ^^^ (y:ys) = map g (xs *** (xs ^^^ ys))
  where
  g (x,e) = (y,x):e