Comparing revisions for page Functions as data

  == Headline ==

The notion of functions being actual data

== Illustration ==

The notion of "functions as data" is closely related to the notion of [[higher-order function]]s. If one wishes to make a difference, then "functions as data" could be meant to focus on the aspect that functions may appear within data structures. The following illustration focuses on this aspect indeed.

Consider the following routine code for evaluating [[reverse polish notation]]:


-- Evaluation of RPN via stack
eval :: RPN -> Int
eval = loop empty
  where
    -- Loop over input
    loop :: Stack Int -> RPN -> Int
    loop s i =
      if null i
        then if size s == 1
               then top s
               else rpnError
        else
          loop (step (head i) s) (tail i)


Now let's assume that we want to parametrize this code in the stack ''implementation''. Thus, we would need to pass a data structure to the eval function such that this structure essentially lists all the stack operations needed. The corresponding data structure can be set up as a record type like this:


data StackImpl s a =
  StackImpl {
    getEmpty :: s a,
    getPush :: a -> s a -> s a,
    getPop :: s a -> s a,
    getTop :: s a -> a,
    getSize :: s a -> Int
  }


A record for a specific stack implementation can be constructed like this:


import qualified SimpleStackADT as Simple

simpleImpl :: StackImpl Simple.Stack a
simpleImpl = StackImpl {
   getEmpty = Simple.empty,
   getPush = Simple.push,
   getPop = Simple.pop,
   getTop = Simple.top,
   getSize = Simple.size
 }


The parameterized version of the RPN evaluator looks like this:


-- Evaluation of RPN via stack
eval :: forall s. StackImpl s Int -> RPN -> Int
eval si = loop (getEmpty si)
  where
    -- Loop over input
    loop :: s Int -> RPN -> Int
    loop s i =
      if null i
        then if getSize si s == 1
               then getTop si s
               else rpnError
        else
          loop (step (head i) s) (tail i) 


The parametrization boils down to this type:


StackImpl s Int


That is, the type variable ''s'' stands for the type constructor used by a specific stack implementation.

We need to pick a stack implementation when invoking the evaluator:


main = do 
          print $ eval simpleImpl sample


== Metadata ==

* [[relatesTo::Higher-order function]]
* [[relatesTo::https://people.eecs.berkeley.edu/~bh/ssch8/part3.html]]