Personal tools

Base cases and identities

From HaskellWiki

(Difference between revisions)
Jump to: navigation, search
(old wiki)
 
(Added a link to Wikipedia for "endomorphism")
 
(3 intermediate revisions by 2 users not shown)
Line 1: Line 1:
http://haskell.org/hawiki/BaseCasesAndIdentities
+
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:
  +
  +
<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 [http://en.wikipedia.org/wiki/Endomorphism endomorphism] in [[category theory]]))
  +
  +
-- [[User:StefanLjungstrand]]
  +
  +
[[Category:Style]]
  +
[[Category:Idioms]]

Latest revision as of 09:12, 30 December 2008

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.

[edit] 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)
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

[edit] 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