Base cases and identities

From HaskellWiki

Sometimes it's hard to work out what the base case of a function should be. Sometimes you can work it out by examining the identities of your operations.

1 Examples

As a simple example, consider the function sum, which takes a list of numbers and adds them:

sum [] = ???
sum (x:xs) = x + sum xs

where `???` is yet to be determined. It's not obvious what the `sum` of an empty list should be, so let's try to work it out indirectly.

The sum function is about adding things. For non-degenerate cases at least, we want `sum` to obey these rules:

sum [x] == x
sum xs + sum ys == sum (xs ++ ys)

sum [] + sum [0] == sum ([] ++ [0])
 => sum [] + 0 == 0
 => sum [] == 0

...and there's our base case.

Similarly, for the `product` function:

product [x] == x
    product xs * product ys == product (xs ++ ys)
 => product [] * product [1] == product ([] ++ [1])    -- (using xs = [], ys = [1])
 => product [] == 1

In both of these cases, the base case is the identity of the underlying operation. This is no accident, and the reason should be obvious:

product [] * product [x] == product ([] ++ [x])
 => product [] * x == x

It follows that `product []` should be the identity for multiplication.

Sometimes there is no identity. Consider this function, for example, which returns the minimum value from a list:

minimum [x] == x
    minimum xs `min` minimum ys == minimum (xs ++ ys)
 => minimum [] `min` minimum [x] == minimum ([] ++ [x])
 => minimum [] `min` x == x

minimum [x] = x
minimum (x:xs) = x `min` minimum xs

2 Exercises

What are sensible base cases for these functions?

• concat
  , which appends a list of lists (e.g.
  concat [[1],[],[2,3]] == [1,2,3]
  ).
• and
  , which takes a list of Bool values and logically "ands" (
  &&
  ) them together.
• or
  , which takes a list of Bool values and logically "ors" (
  ||
  ) them together.
• xor
  , which takes a list of bool values and logically "exclusive ors" them together.
• greatest_common_divisor
  , which returns the GCD of a list of integers. (The GCD of two integers is the largest number which divides evenly into them both.)
• least_common_multiple
  , which returns the LCM of a list of integers. (The LCM of two integers is the smallest number which they both evenly divide into.)

-- User:AndrewBromage

• compose
  , which composes a list of "endo"-functions e.g.:

compose [recip,(** 2),sin,(* 2 * pi)] = recip . (** 2) . sin . (* 2 * pi) = \x -> recip (sin (x * 2 * pi) ** 2)

("endo"-function meaning that the function returns something of the same type as it as it takes as input, (from EndoMorphism in category theory))

-- User:StefanLjungstrand

Categories: Style | Idioms