Skip to content

The Connection Between Functions and Containers

This section is entirely optional reading, but I thought it would be instructive to explore the connection between functions and containers in a bit greater depth. This connection is grounded in mathematics and also provides a theoretical foundation for a number of useful programming abstractions. Let's explore two examples.

Fast Computation of Fibonacci Numbers via Memoization

Recall our original definition of Fibonacci numbers that we started with when discussing recursion:

fib :: Integer -> Integer
fib 0 = 0
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)

That's a function of type Integer -> Integer. We can also view it as a container that stores the \(n\)th Fibonacci number \(F_n\) at index \(n\). When we defined the list of Fibonacci numbers we defined in the chapter on lazy evaluation,

fibonaccis :: Integer
fibonaccis = 0 : 1 : zipWith (+) fibonaccis (tail fibonaccis)

we constructed such a container of all Fibonacci numbers explicitly.

And now for the round-trip. How do we convert this container back into a function? The list type supports an indexing operator that I didn't discuss before because it is expensive compared to the constant-time element access that arrays support. Remember, to access an array element at index i, we use arr ! i. The operator to access the ith element in a list is (!!):

GHCi
>>> [1,2,3,4,5] !! 2
3

List elements are indexed starting at 0. Note that the cost of xs !! i is proportional to i because we cannot simply access the ith list element, as we would be able to do in an array. We have to walk down the list to find the ith list element:

(!!) :: [a] -> Int -> a
[]     !! _ = error "List index out of bounds"
(x:_)  !! 0 = x
(_:xs) !! n = xs !! (n - 1)

With the help of (!!), we can implement our original fib function quite easily:

fib n = fibonaccis !! n

This is not just an exercise in converting between functions and containers. Our new implementation of fib n is much faster than the old implementation: Building fibonaccis takes constant time per element. fib n spends linear time to find the nth element in this list. Thus, fib n takes linear time to compute the nth Fibonacci number:

GHCi
>>> fibonaccis = 0 : 1 : zipWith (+) fibonaccis (tail fibonaccis)
>>> fib n = fibonaccis !! n
>>> fib 10000
336447648764317832666216120051075433103021484606800639065647699746800814421666623681555955136337
340255820653326808361593737347904838652682630408924630564318873545443695598274916066020998841839
338646527313000888302692356736131351175792974378544137521305205043477016022647583189065278908551
543661595829872796829875106312005754287834532155151038708182989697916131278562650331954871402142
875326981879620469360978799003509623022910263681314931952756302278376284415403605844025721143349
611800230912082870460889239623288354615057765832712525460935911282039252853934346209042452489294
039017062338889910858410651831733604374707379085526317643257339937128719375877468974799263058370
657428301616374089691784263786242128352581128205163702980893320999057079200643674262023897831114
700540749984592503606335609338838319233867830561364353518921332797329081337326426526339897639227
234078829281779535805709936910491754708089318410561463223382174656373212482263830921032977016480
547262438423748624114530938122065649140327510866433945175121615265453613331113140424368548051067
658434935238369596534280717687753283482343455573667197313927462736291082106792807847180353291311
767789246590899386354593278945237776744061922403376386740040213303432974969020283281459334188268
176838930720036347956231171031012919531697946076327375892535307725523759437884345040677155557790
564504430166401194625809722167297586150269684431469520346149322911059706762432685159928347098912
847067408620085871350162603120719031720860940812983215810772820763531866246112782455372085323653
057759564300725177443150515396009051686032203491632226408852488524331580515348496224348482993809
050704834824493274537326245677558790891871908036620580095947431500524025327097469953187707243768
259074199396322659841474981936092852239450397071654431564213281576889080587831834049174345562705
202235648464951961124602683139709750693826487066132645076650746115126775227486215986425307112984
411826226610571635150692600298617049454250474913781151541399415506712562711971332527636319396069
02895650288268608362241082050562430701794976171121233066073310059947366875

The original definition of fib n takes exponential time:

GHCi
>>> :{
  | fib 0 = 0
  | fib 1 = 1
  | fib n = fib (n - 1) + fib (n - 2)
  | :}
>>> fib 100
^CInterrupted.

We made this gain in efficiency exactly because when using fibonaccis to store all Fibonacci numbers, we replace the costly evaluation of \(F_n\) with a simple table lookup. That is the essence of memoization or, in flashier programmer's lingo, caching, a common technique for speeding up code by avoiding to recompute values over and over again. Memoization is also the core idea behind dynamic programming, which we applied to find the longest common subsequence of two strings.

Implementing Finite Automata: Flexibility via Functions

The second example does not improve the efficiency of our code but uses the duality between containers and functions to build better abstractions. Recall a deterministic finite automaton (DFA) from CSCI 2115. Here is how we implemented it in Python in that course:

dfa.py
class DFA:

    def __init__(self, start, is_accepting, delta):
        self.start        = start
        self.is_accepting = is_accepting
        self.delta        = delta

    def accepts(self, string):
        state = self.start
        for ch in string:
            state = self.delta[(state, ch)]
        return self.is_accepting[state]

In this implementation, is_accepting is an array of Booleans. The sth entry in this array stores whether s is an accepting state. delta is a dictionary representing our transition function. For each pair (state, ch), delta stores the state to which the DFA should transition when reading the character ch in state state.

That's a perfectly fine implementation. Here's the DFA over the alphabet \(\{0, 1\}\) that accepts a string if and only if the number of 1s is even:

Python
>>> from dfa import DFA
>>> dfa = DFA(
...     0,
...     [True, False],
...     {
...         (0,'0'): 0,
...         (0,'1'): 1,
...         (1,'0'): 1,
...         (1,'1'): 0
...     }
... )
>>> dfa.accepts("001100100100")
True
>>> dfa.accepts("001100100101")
False

Here's the same code in Haskell:

DFA.hs
import Data.Array
import Data.List

newtype State = State Int
  deriving (Eq, Ord, Ix)

data DFA = DFA
    { start       :: State
    , isAccepting :: Array State Bool
    , delta       :: Array (State, Char) State
    }

accepts :: DFA -> String -> Bool
accepts dfa string = isAccepting dfa ! foldl' nextState (start dfa) string
  where
    nextState state ch = delta dfa ! (state, ch)

Again, this works as expected:

GHCi
>>> :l DFA.hs
[1 of 1] Compiling Main             ( DFA.hs, interpreted )
Ok, one module loaded.
>>> :{
  | dfa = DFA
  |     { start       = State 0
  |     , isAccepting = listArray (State 0, State 1) [True, False]
  |     , delta       = listArray ((State 0, '0'), (State 1, '1')) [State 0, State 1, State 1, State 0]
  |     }
  | :}
>>> dfa `accepts` "001100100100"
True
>>> dfa `accepts` "001100100101"
False

Conceptually, it's a bit awkward though. In our definition of a DFA in CSCI 2115, \(D = (S, \Sigma, \delta, s_0, F)\), we were given a set of states \(S\), an alphabet \(\Sigma\), a transition function \(\delta : S \times \Sigma \rightarrow S\), a start state \(s_0 \in S\), and a set of accepting states \(F \subseteq S\). When implementing a DFA, the state set and the alphabet are implicit, so we are left with representing \(\delta\), \(s_0\), and \(F\). The point I want you to focus on is that \(\delta\) is a function, not a lookup table, in the definition of a DFA. Programs are always easier to understand if they mirror exactly what we are trying to model. So what we would really like is for our DFA to store a transition function delta :: State -> Char -> State instead of a lookup table. When it comes to representing the accepting states, we could actually do this using the Set data type from the Data.Set module, but arguably what we really want is a function isAccepting :: State -> Bool, not a set or lookup table, because that's the question we ask at the end: Is the state we reach after reading the entire string accepting?1

So let's change the definition of our DFA type to look more natural:

DFA.hs
import Data.Array
import Data.List

newtype State = State Int deriving (Eq, Ord, Ix)

data DFA = DFA
    { start       :: State
    , isAccepting :: State -> Bool
    , delta       :: State -> Char -> State
    }

accepts :: DFA -> String -> Bool
accepts dfa string = isAccepting dfa ! foldl' nextState (start dfa) string
  where
    nextState state ch = delta dfa ! (state, ch)

We also need to change our implementation of accepts to replace the lookups of values in our delta and isAccepting arrays with the corresponding function applications:

DFA.hs
import Data.Array
import Data.List

newtype State = State Int deriving (Eq, Ord, Ix)

data DFA = DFA
    { start       :: State
    , isAccepting :: State -> Bool
    , delta       :: State -> Char -> State
    }

accepts :: DFA -> String -> Bool
accepts dfa = isAccepting dfa . foldl' (delta dfa) (start dfa)

I don't know about you, but I find this implementation more natural. In essence, our new delta function does exactly the same as the helper function nextState in our previous implementation.

This new DFA type is also more flexible. For simple DFA, we can define the functions delta and isAccepting directly:

GHCi
>>> :r
[1 of 1] Compiling Main             ( DFA.hs, interpreted )
Ok, one module loaded.
>>> :{
  | dfa = DFA
  |     { start       = State 0
  |     , isAccepting = \(State i)    -> i == 0
  |     , delta       = \(State i) ch -> State $ if ch == '1' then (1 - i) else i
  |     }
  | :}
>>> dfa `accepts` "001100100100"
True
>>> dfa `accepts` "001100100101"
False

For more complicated DFA, nobody prevents us from building lookup tables again and implementing isAccepting and delta as lookup functions:

GHCi
>>> acceptingStates = listArray (State 0, State 1) [True, False]
>>> deltaTable      = listArray ((State 0, '0'), (State 1, '1')) [State 0, State 1, State 1, State 0]
>>> :{
  | dfa = DFA
  |     { start       = State 0
  |     , isAccepting =         (!) acceptingStates
  |     , delta       = curry $ (!) deltaTable
  |     }
  | :}
>>> dfa `accepts` "001100100100"
True
>>> dfa `accepts` "001100100101"
False

Where the initial implementation forced us to always use lookup tables, the new implementation gives us a choice.

  1. So, while I go to great lengths here to argue that representing delta as a function instead of a lookup table is good because it matches our definition of a DFA, I choose to deviate from the definition of a DFA by having a function isAccepting :: State -> Bool instead of a set of accepting states. This may seem a bit inconsistent. The real reason why I did this is because we don't do anything with the set of accepting states except test membership of a state in this set, which is best represented as a function.

    However, I have a better justification for this choice, at least if you like mathematical abstractions. We can argue that subsets of a set \(S\) and Boolean functions with argument type \(S\) are the exact same thing. When we define our set of accepting states \(F\), it is as a subset of \(S\), \(F \subseteq S\). The set of all subsets of \(S\) is called the powerset of \(S\). \(F\) is simply an element of this power set. Many mathematicians use \(2^S\) to refer to the power set of a set \(S\). This makes some sense because at least there are exactly \(2^{|S|}\) subsets of \(S\). However, the real justification of this notation is deeper: In category theory, we use \(D^C\) to denote the set of all functions from the set \(C\) to the set \(D\) (at least as long as we work in the category of sets and functions between them). We also often use 2 to denote the 2-element set, say \(2 = \{\text{False}, \text{True}\}\). So, \(2^S\) is the set of all functions \(f : S \rightarrow 2\). But these functions are in one-to-one correspondence to the subsets of \(S\), via the definition \(S_f = \{ x \in S \mid f(x) = \text{True} \} \subseteq S\). Thus, in essence, subsets of \(S\) and Boolean functions \(S \rightarrow 2\) are two representations of the exact same concept. ↩