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.
