2

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?

1 Answer 1

5

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 ns and accs. 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]

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.