# Functions not data structures

### From HaskellWiki

(Difference between revisions)

(Migrating from old wiki) |
|||

Line 1: | Line 1: | ||

− | + | Sometimes the best way to represent data is using a function. | |

+ | |||

+ | [[Church encoding]] can be used to represent any [[algebraic data type]] using only functions. | ||

+ | |||

+ | Another example is the following, not very efficient, implementation of a FiniteMap: | ||

+ | |||

+ | <haskell> | ||

+ | type FiniteMap key elt = key -> Maybe elt | ||

+ | |||

+ | emptyFM :: FiniteMap key elt | ||

+ | emptyFM = \k' -> Nothing | ||

+ | |||

+ | addToFM :: (Eq key) => FiniteMap key elt -> key -> elt -> FiniteMap key elt | ||

+ | addToFM m k v = \k' -> if (k == k') then Just v else m k' | ||

+ | |||

+ | delFromFM :: (Eq k) => FiniteMap key elt -> key -> FiniteMap key elt | ||

+ | delFromFM m k = \k' -> if (k == k') then Nothing else m k' | ||

+ | |||

+ | lookupFM :: (Eq k) => FiniteMap key elt -> key -> Maybe elt | ||

+ | lookupFM m k = m k | ||

+ | </haskell> | ||

+ | |||

+ | [[Run time compilation]] uses functions not data structures to implement an interpreter. | ||

+ | |||

+ | [[Category:Idioms]] |

## Revision as of 06:17, 20 July 2010

Sometimes the best way to represent data is using a function.

Church encoding can be used to represent any algebraic data type using only functions.

Another example is the following, not very efficient, implementation of a FiniteMap:

type FiniteMap key elt = key -> Maybe elt emptyFM :: FiniteMap key elt emptyFM = \k' -> Nothing addToFM :: (Eq key) => FiniteMap key elt -> key -> elt -> FiniteMap key elt addToFM m k v = \k' -> if (k == k') then Just v else m k' delFromFM :: (Eq k) => FiniteMap key elt -> key -> FiniteMap key elt delFromFM m k = \k' -> if (k == k') then Nothing else m k' lookupFM :: (Eq k) => FiniteMap key elt -> key -> Maybe elt lookupFM m k = m k

Run time compilation uses functions not data structures to implement an interpreter.