Personal tools

Functions not data structures

From HaskellWiki

(Difference between revisions)
Jump to: navigation, search
 
(Added Categorie FAQ)
 
(2 intermediate revisions by one user not shown)
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>
  +
  +
[[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.