I was wondering why all of the programming languages I know treat key-value containers (i.e. sequences and associative arrays) differently from functions. From mathematics, I’m used to thinking of key-value containers as functions of one argument, taking a key as input and giving a value as output. Treating key-value containers as functions would have some nice effects, such as allowing the free use of infinite containers and allowing the use of function composition in place of the higher-order function normally called `map`

.

Here’s my guess: one major difference between key-value containers and functions in most programming languages is that the values in containers are precomputed, while the values of functions are computed only when the function is called on the argument. This can be illustrated if we try using function composition in place of `map`

in Racket:

```
(define (my-map f xs)
(lambda (i)
(f (xs i))))
(define (my-sequence i)
(match i
(0 1)
(1 4)
(2 9)))
(define (write-and-square x)
(writeln x)
(* x x))
(writeln "squared-list:")
; displays 1, 4 and 9
(define squared-list (map write-and-square (list 1 4 9)))
(writeln "my-sequence-squared created:")
; nothing displayed
(define my-sequence-squared (my-map write-and-square my-sequence))
(writeln "my-sequence-squared accessed:")
(writeln (my-sequence-squared 0)) ; displays 1 and 1
(writeln (my-sequence-squared 1)) ; displays 4 and 16
(writeln (my-sequence-squared 2)) ; displays 9 and 81
```

When we use Racket’s `map`

function to define `squared-list`

, the members of the list have `write-and-square`

applied right away, and we see the side-effect of the function. But when we use our `my-map`

function, the evaluation of `write-and-square`

on a given key is delayed until the value the key maps to is actually requested. This is a sort of lazy evaluation. Although lazy evaluation has its uses, it can lead to inefficiency if a key is accessed repeatedly and the value it maps to is fully recomputed again and again needlessly without a cache being stored in memory.

To deal with this, we can use memoization. However, since an arbitrary function may have an infinite domain, we have to choose which values to memoize. Here’s a Racket function for carrying out the memoization (using some `eval`

black magic to dynamically write a pattern match):

```
(define (memoize mapping keys)
(define cases (map (lambda (key)
(list key (mapping key))) keys))
(lambda (key)
(eval (append
(list 'match key)
cases
(list (list '_ (list mapping key)))))))
```

And here’s a test showing the function has the expected behaviour.

```
(writeln "my-sequence-squared-2 created:")
; displays nothing
(define my-sequence-squared-2 (my-map write-and-square my-sequence))
(writeln "my-sequence-squared-3 created:")
; displays 1 and 4
(define my-sequence-squared-3 (memoize my-sequence-squared-2 (list 0 1)))
(writeln "my-sequence-squared-3 accessed:")
(my-sequence-squared-3 1) ; displays 16
(my-sequence-squared-3 2) ; displays 9 and 81
```

Now, for functions with finite domain, a natural default is to memoize all of the values. But how do we do that? Given an arbitrary function, we don’t know whether its domain is finite, and even if its domain is finite, we don’t know how to iterate through all of the domain’s members. So we can’t just add some extra code in `my-map`

saying something like “if the function has a finite domain, memoize each of the values of the composition”. Our options are to either require users of `my-map`

to explicitly memoize whatever specific values need memoizing, or add some extra information to the functions themselves specifying whether they have a finite domain and how they can be iterated over, which `my-map`

can then take advantage of.

A natural way to supply this information is to use objects of a distinct type, a “container type”, instead of functions on finite domains. Any object with a container type can be assumed to be finite. Furthermore, we can have multiple container types, each associated with their own iteration protocol.

This, then, is the purpose, or at least a purpose, of having containers as a distinct concept from functions. Containers are functions together with the necessary additional information required to memoize all of their values behind the scenes whenever they are composed.

Source code for this blog post (note: the last couple of lines give an error when the file is run in DrRacket, but if you type them into the REPL after running the rest of the program they work fine, so I assume the problem is DrRacket’s and not mine 🙂 )