View source for Functions not data structures

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>

[[Runtime compilation]] uses functions not data structures to implement an interpretation layer.

[[Category:Idioms]]
[[Category:FAQ]]