Difference between revisions of "Base cases and identities"
(old wiki) |
BrettGiles (talk | contribs) (convert old hawiki page (Better categorization thoughts welcome)) |
||
Line 1: | Line 1: | ||
+ | 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. |
||
− | http://haskell.org/hawiki/BaseCasesAndIdentities |
||
+ | |||
+ | ==Examples== |
||
+ | As a simple example, consider the function sum, which takes a list of numbers and adds them: |
||
+ | |||
+ | <haskell> |
||
+ | sum [] = ??? |
||
+ | sum (x:xs) = x + sum xs |
||
+ | </haskell> |
||
+ | |||
+ | 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: |
||
+ | |||
+ | <haskell> |
||
+ | sum [x] == x |
||
+ | sum xs + sum ys == sum (xs ++ ys) |
||
+ | </haskell> |
||
+ | |||
+ | Substituting <hask>xs = []</hask> and <hask>ys = [0]</hask> gives us: |
||
+ | |||
+ | |||
+ | <haskell> |
||
+ | sum [] + sum [0] == sum ([] ++ [0]) |
||
+ | => sum [] + 0 == 0 |
||
+ | => sum [] == 0 |
||
+ | </haskell> |
||
+ | |||
+ | ...and there's our base case. |
||
+ | |||
+ | Similarly, for the `product` function: |
||
+ | |||
+ | |||
+ | <haskell> |
||
+ | product [x] == x |
||
+ | product xs * product ys == product (xs ++ ys) |
||
+ | => product [] * product [1] == product ([] ++ [1]) -- (using xs = [], ys = [1]) |
||
+ | => product [] == 1 |
||
+ | </haskell> |
||
+ | |||
+ | 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: |
||
+ | |||
+ | <haskell> |
||
+ | product [] * product [x] == product ([] ++ [x]) |
||
+ | => product [] * x == x |
||
+ | </haskell> |
||
+ | |||
+ | 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: |
||
+ | |||
+ | <haskell> |
||
+ | minimum [x] == x |
||
+ | minimum xs `min` minimum ys == minimum (xs ++ ys) |
||
+ | => minimum [] `min` minimum [x] == minimum ([] ++ [x]) |
||
+ | => minimum [] `min` x == x |
||
+ | </haskell> |
||
+ | |||
+ | The only sensible value for <hask>minimum []</hask> is the maximum possible value for whatever type <hask>x</hask> has. Since there is no such value in general (consider <hask>x :: Integer</hask>, for example), <hask>minimum []</hask> has no sensible value. Better to use a <hask>foldr1</hask> or <hask>foldl1</hask> pattern instead: |
||
+ | |||
+ | <haskell> |
||
+ | minimum [x] = x |
||
+ | minimum (x:xs) = x `min` minimum xs |
||
+ | </haskell> |
||
+ | |||
+ | ==Exercises== |
||
+ | What are sensible base cases for these functions? |
||
+ | |||
+ | * <hask>concat</hask>, which appends a list of lists (e.g. <hask>concat [[1],[],[2,3]] == [1,2,3]</hask>). |
||
+ | * <hask>and</hask>, which takes a list of Bool values and logically "ands" (<hask>&&</hask>) them together. |
||
+ | * <hask>or</hask>, which takes a list of Bool values and logically "ors" (<hask>||</hask>) them together. |
||
+ | * <hask>xor</hask>, which takes a list of bool values and logically "exclusive ors" them together. |
||
+ | * <hask>greatest_common_divisor</hask>, which returns the GCD of a list of integers. (The GCD of two integers is the largest number which divides evenly into them both.) |
||
+ | * <hask>least_common_multiple</hask>, 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]] |
||
+ | |||
+ | * <hask>compose</hask>, which composes a list of "endo"-functions e.g.: |
||
+ | ::<hask>compose [recip,(** 2),sin,(* 2 * pi)] = recip . (** 2) . sin . (* 2 * pi) = \x -> recip (sin (x * 2 * pi) ** 2)</hask> |
||
+ | :("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]] |
||
+ | |||
+ | [[Category:Tutorials]] |
Revision as of 18:52, 15 May 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.
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)
Substituting xs = []
and ys = [0]
gives us:
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
The only sensible value for minimum []
is the maximum possible value for whatever type x
has. Since there is no such value in general (consider x :: Integer
, for example), minimum []
has no sensible value. Better to use a foldr1
or foldl1
pattern instead:
minimum [x] = x
minimum (x:xs) = x `min` minimum xs
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.)
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))