Personal tools

Functions not data structures

From HaskellWiki

(Difference between revisions)
Jump to: navigation, search
 
(Migrating from old wiki)
Line 1: Line 1:
http://haskell.org/wikisnapshot/FunctionsNotDataStructures.html
+
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.