Iteration in Racket I - State

I find great joy in using programming languages idiomatically. Following the conventions and thoroughly using the features of a language helps write shorter and simpler programs. Compared to using a library, readers of the program will be more likely to be familiar with the abstractions, and even if unfamiliar it will be easier to learn about them and more useful due to them being more applicable.

Racket’s iterations and comprehensions are an excellent example of very powerful abstractions built right into the language. The for/* forms capture many iteration patterns in a generic and systematic way. Different for/* forms differ in what they do with the results of the iteration, but they all take the same options and give them meanings that make sense for each pattern.

I want to show you an example of using the for/fold form to write a very brief and readable program. Let’s consider the following problem posed by @cassidoo in her newsletter:

Given an array where each element is the price of a given stock on that index’s day, choose a single day to buy a stock and a different day (in the future/later in the array) to sell the stock to maximize your profit. Return the maximum profit that you can get from a given input. If you can’t profit, return 0.

For example, maximumProfit([7, 1, 5, 3, 6, 4]) would return 5, because it’s best to buy on day 2, and sell on day 5, for a profit of 6 - 1 = 5.

Rather than checking every possibility we can use dynamic programming to go over the array once, keeping track of the best solution so far an seeing if we can improve it. Something like this:

#!/usr/bin/Python

def maximum_profit(days):
    # By definition, the worst profit is 0
    best_profit = 0
    # Initially the cheapest you can buy is the day one's price
    best_price = days[0]

    # For each day
    for price in days:
        # You could sell, maybe beating the best profit
        best_profit = max(best_profit, price - best_price)
        # Or you could buy, if the price is the best so far
        best_price = min(best_price, price)

    return best_profit

assert maximum_profit([7, 1, 5, 3, 6, 4]) == 5
assert maximum_profit([2, 10, 1, 8]) == 8
assert maximum_profit([1]) == 0

This Python version relies on an imperative iteration with two side effects (updating best_profit and updating best_price). Racket is a functional language so on principle we avoid mutation and iterate by doing recursion. Here’s a possible version:

#lang racket

(define (max-profit-helper days best-price best-profit)
  (cond
    [(empty? days) best-profit]
    [else
     (let ([price (first days)])
       (max-profit-helper (rest days)
                          (min best-price price)
                          (max best-profit (- price best-price))))]))

(define (max-profit% days)
  (max-profit-helper days (first days) 0))

(println (max-profit% '(7 1 5 3 6 4))) ; 5
(println (max-profit% '(2 10 1 8))) ; 8
(println (max-profit% '(1))) ; 0

It’s a little cumbersome. Compared to the Python version we have to inspect the recursive function to understand we are iterating over days. And because we need to keep track of two pieces of state, we need to split the function into a recursion helper and the function proper.

Recursion is a very general mechanism, but for/* and friends capture more specific patterns of iteration through a sequence. In our case, the idea of going through a sequence element by element, accumulating some sort of state, is the concept of folding, and the corresponding Racket iteration is called for/fold.

Rewriting our solution using for/fold looks like:

#lang racket

(define (max-profit days)
  (for/fold ([best-price (car days)]
             [best-profit 0]
             #:result best-profit)
            ([price days])
    (values (min best-price price)
            (max best-profit (- price best-price)))))

(println (max-profit '(7 1 5 3 6 4))) ; 5
(println (max-profit '(2 10 1 8))) ; 8
(println (max-profit '(1))) ; 0

Which I think is even better than the Python version:

1. The specific iteration pattern is explicitly named (fold).
2. We can accumulate two values independently (the best price and the best profit), but only use one as the final result via #:result.
3. The body of the for/fold is a pure function that performs a single complete iteration step. Nothing gets updated until the function is complete, so computing best-price before best-profit does not cause a bug like it would in the Python version.

I encourage you to take a look at the Racket guide on iterations and comprehensions and to take a look there first whenever you are considering any sort of iterative or even recursive process.