# Is a trace table useful in functional programming?

A trace table is a technique used to test algorithms.

"The table usually takes the form of a multi-column, multi-row table; With each column showing a variable, and each row showing each number input into the algorithm and the subsequent values of the variables." ~ Wikipedia

Whereas in a pure functional language the variables do not change their values, this technique has some use?

It is less useful in a pure functional language (or even when programming in pure style in an otherwise impure language). However, you can still make use of it by interpreting it a little differently: e.g. in a recursive function, the parameter binding may not change its value in the function, but for every recursive call, the same parameter will be bound to a different value, so if you re-interpret the recursive calls as a sequence, the parameter still appears to change its binding over time (even though it actually is a different binding in a different dynamic scope (stack frame)).

All of the examples of trace tables I have been able to find during a quick search involve looping, and tail-recursion is essentially the pure way of looping. Take the "canonical" tail-recursive factorial example:

``````factorial n = fact' n 1
where
fact' 0 acc = acc
fact' n acc = fact' (n-1) (n*acc)
``````

You can easily create a trace table for the tail-recursive helper function `fact'`, let's take the factorial of 4:

``````n    acc
--------
4     1
3     4
2    12
1    24
0    24
--------
ret: 24
``````

Technically speaking, `n` and `acc` don't change, rather there are 5 different `n`s and `acc`s. But you can still think of it this way.

However, thinking about data flow is often more useful than thinking about state changes in pure functional programming. And thinking in higher-level, more abstract concepts such as maps, folds, scans, monoids, monads, functors, arrows, semigroups, etc. E.g. `factorial` can trivially be expressed as a `fold`:

``````factorial 0 = 1
factorial n = foldl1 (*) [1..n]
``````