Base cases and identities
(convert old hawiki page (Better categorization thoughts welcome))
Revision as of 12:14, 3 July 2007
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.
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  == sum ( ++ ) => 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  == product ( ++ ) -- (using xs = , ys = ) => 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
What are sensible base cases for these functions?
- , which appends a list of lists (e.g.concat).concat [,,[2,3]] == [1,2,3]
- , which takes a list of Bool values and logically "ands" (and) them together.&&
- , which takes a list of Bool values and logically "ors" (or) them together.||
- , which takes a list of bool values and logically "exclusive ors" them together.xor
- , which returns the GCD of a list of integers. (The GCD of two integers is the largest number which divides evenly into them both.)greatest_common_divisor
- , which returns the LCM of a list of integers. (The LCM of two integers is the smallest number which they both evenly divide into.)least_common_multiple
- , which composes a list of "endo"-functions e.g.:compose
- 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))