Difference between revisions of "Functions not data structures"
Jump to navigation
Jump to search
(Added Categorie FAQ) |
|||
| (2 intermediate revisions by one other user not shown) | |||
| Line 1: | Line 1: | ||
| + | Sometimes the best way to represent data is using a function. |
||
| − | http://haskell.org/wikisnapshot/FunctionsNotDataStructures.html |
||
| + | |||
| + | [[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> |
||
| + | |||
| + | [[Runtime compilation]] uses functions not data structures to implement an interpretation layer. |
||
| + | |||
| + | [[Category:Idioms]] |
||
| + | [[Category:FAQ]] |
||
Latest revision as of 22:47, 1 November 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
Runtime compilation uses functions not data structures to implement an interpretation layer.