FPSE

Efficiency in Functional Programming

• Our main goal is code clarity, but in some cases, efficiency does matter.
• We already discussed this issue a bit (e.g. cons vs append, tail recursion).
• In this lecture, we go into more detail on efficiency considerations.
• We will conclude with some examples.

Tail recursion

• We covered this earlier: List.fold_left is tail-recursive whereas List.fold_right is not

let rec fold_left f acc ls =
  match ls with
  | [] -> acc
  | hd :: tl -> fold_left f (f acc hd) tl

let rec fold_right f ls acc =
  match ls with
  | [] -> acc
  | hd :: tl -> f hd (fold_right f tl acc)

• A tail-recursive function is a function where there is no work to do after returning from recursive calls
  • See how the last thing fold_left does is call fold_left.
  • Just directly return the result
• Observation: since there is no need to mark the call point to resume from, no stack is needed
  • We can overwrite the parameters going “down”, and return the base case as the final result of the recursion.
  • There is no need to pop off the stack.
  • See how in fold_right, once the recursive call to fold_right returns, we still need to do work: call f.
• Compilers can see which functions are tail recursive and then eliminate the stack.
• Moral: to save space/time, you may need to tail-call

Imperative vs functional data structures

Let us warm up by reviewing 'a list efficiency.

• hd and tl are O(1); that is to say, pattern matching is O(1).
• List.nth is O(n) – lists are not random access
• append l1 l2 is O(length l1) - cons each l1 elt onto l2 one by one

Remember that sub-lists are shared since they are immutable.

let l1 = [1;2;3;... n] in
let l2 = 0    :: l1 in
let l3 = (-1) :: l1 in ..

• l2 and l3 share l1.
• If lists were mutable, such sharing would not generally be possible.

List vs Array:

• Adding an element to the front (extending list) is constant time for list, O(n) for array.
  • Array needs to be copied to get more memory.
  • Several lists can share a tail due to referential transparency. They are sprawled across memory.
• Update of one element in an array is O(1); updating one element of a list is worst-case O(n), to re-build the whole list.
• Random access of nth element: O(n) list, O(1) array.
• If you want fast random access to a “list” that is not growing / shrinking, use an array.
  • If your array is not mutating at all, then use an immutable array, iarray.

Map vs Hashtbl:

• Map is implemented like the dict from the homework: a binary search tree.
• O(log n) worst case time for Map to look up, add, or change an entry
  • only the path to the changed node needs updating, all the sub-trees hanging off it are kept
• “O(1) amortized” for Hashtbl - will only matter for really big data sets.
• But, like arrays, hash tables can’t be shared, and you need to manually copy instead.
  • If you have a map, and you want to keep many versions of around, Map will beat Hashtbl because copying is free.

A Set is implemented like a Map without a key. It is a tree.

• Here is a summary of OCaml data structure complexity

Summary: functional data structures…

• feel like they should be much more inefficient, but are often “at worst a log factor”
• in a few cases are actually better because past states “persist for free”
  • e.g. sub-lists can be shared since copying never needed, etc
  • See Real World OCaml Hash table vs Map comparison (scroll down) for example benchmarks.
    • For standard uses, a mutable hashtable will be “O(1)” vs O(log n) for the corresponding Map operations
    • But if there are many minor variations on the Map/Hashset being created, the functional data structure will in fact be faster due to the sharing immutability can support.

In a few cases, speed is critical, and mutable structures are required.

Case Study: Monadic Minesweeper

• Let us analyze the complexity of different implementations of Minesweeper.
• Assume a grid of n elements (a square-root n by square-root n grid)

Our initial implementation using a list of strings

• Each call to get x y is O(sqrt n) since we need to march down the lists to find element (x,y)
• So O(sqrt n) for each inc operation so O(n * sqrt n) overall.

Our implementation using a functional 2D array

• The array is in fact never mutated, only used for random access to fixed array, so it is an iarray.
• Otherwise this implementation is the same as the above.
• get x y is now O(1) since it is an array – random access.
• O(1) for each inc operation so O(n) in total.

Stateful version using an array

• Instead of counting mines around each empty square once and for all, for each mine increments all its non-mine neighbors
• It is a fundamentally mutating alternative algorithm.
• O(n) as with the previous functional array version

Monadic state version

• A state monad version of the original minesweeper
• We will follow the data structure of the original minesweeper, the list of strings
• But do the imperative increment-the-mine-neighbors instead of the functional count-the-mines
• Each grid square increment will take O(n) since the whole list of strings has to be rebuilt with one change
  • there is some functional sharing of parts not incremented (as in list append above) but means 1/2 n = O(n)
• O(n) inc’s are performed total so it will be O(n^2).
• So a bit of a backfire

Imagine an alternative state monad implementation with Board state implemented as a Map from keys (i,j) to characters:

• Lookup and increment will be O(log n) on average since Map is implemented as a balanced binary search tree
  • one change to a Map’s tree is only log n because only one path in tree is changed, rest can be re-used
  • (yes, one path down a binary tree is only 1/(log n)-th of the tree nodes, and the sub-trees can be reused)
• So total time is O(n log n)

If you want to build these examples yourself, here is a zip with all of them.

Conclusion

• For Minesweeper, O(n^2) is in fact fine as the grids are always “tiny” in a CPU sense
• But if this grid was instead a large image (pixel grid) this would be intolerable

FP and paralellism briefly

• In pure FP with no side effects, any independent computation can be done in parallel
• Example: List.map could apply f on the list elements in parallel
  • but, reconstructing the list has to be in-order so only useful for slow-running f’s
  • Also fold and the like can’t be easily parallelized since the accum needs to be passed along sequentially
• Multiple function arguments can be evaluated in parallel if they contain no effects
  • Referential transparency in general makes parallelism much easier to get right
• OCaml also now has parallelism starting with OCaml 5 - here is a tutorial.

Writing more efficient functions

• We already covered tail recursion
  • Tail recursion principle: if the last action in a function is a recursive call, compiler can optimize away the call stack
  • Moral: optimize deep recursive functions (e.g. working on long lists) to be tail-recursive if possible
• Let us consider one more now.

Memoization

• If a function has no side effects it can easily be memoized
  • We saw in the homework how it could take an exponential fibbonicci to linear
  • In general memoization works when there are no effects in the function (and, we have an = defined on the arguments)
  • If the function is expensive and is often invoked on the same argument, this will be very effective
• Note that memoization implicitly needs a store for this past history
• Could use mutable store, but could also use a state monad
  • pass in and return the store in the memoized function