# Functions as data

The notion of functions being actual data

## Illustration

The notion of "functions as data" is closely related to the notion of higher-order functions. 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
```

Ralf Lämmel edited this article at Sat, 04 Jun 2022 11:31:47 +0200

## User contributions

This user never has never made submissions.

## Syntax for editing wiki

For you are available next options:

will make text bold.

will make text italic.

will make text underlined.

will make text striked.

will allow you to paste code headline into the page.

will allow you to link into the page.

will allow you to paste code with syntax highlight into the page. You will need to define used programming language.

will allow you to paste image into the page.

is list with bullets.

is list with numbers.

will allow your to insert slideshare presentation into the page. You need to copy link to presentation and insert it as parameter in this tag.

will allow your to insert youtube video into the page. You need to copy link to youtube page with video and insert it as parameter in this tag.

will allow your to insert code snippets from @worker.

## Syntax for editing wiki

For you are available next options:

will make text bold.

will make text italic.

will make text underlined.

will make text striked.

will allow you to paste code headline into the page.

will allow you to link into the page.

will allow you to paste code with syntax highlight into the page. You will need to define used programming language.

will allow you to paste image into the page.

is list with bullets.

is list with numbers.

will allow your to insert slideshare presentation into the page. You need to copy link to presentation and insert it as parameter in this tag.

will allow your to insert youtube video into the page. You need to copy link to youtube page with video and insert it as parameter in this tag.

will allow your to insert code snippets from @worker.