We are given three different commands:
forward X increases the horizontal position by X units.
down X increases the depth by X units.
up X decreases the depth by X units.
Given a long list of these, we are to compute the final depth and horizontal position of the submarine. This is straightforward. We define a type of movement commands:
data Command = Forward Int | Down Int | Up Int
We then have a function move : [Command] → ⟨Int, Int⟩. Clearly this is a catamorphism:
move = foldr f ⟨0, 0⟩
f : Command → (Int × Int) → (Int × Int);
f (Forward k) ⟨x, y⟩ = ⟨x + k, y⟩;
f (Down k) ⟨x, y⟩ = ⟨x, y + k⟩;
f (Up k) ⟨x, y⟩ = ⟨x, y - k⟩
We’d like to replace the right fold with a (strict) left fold. Define:
f′ = flip f
Then by some quick informal calculations, we have that f associates with f′:
f c ⟨0, 0⟩ = f′ ⟨0, 0⟩ c
f c (f′ ⟨x, y⟩ d) = f c ⟨x + k, y + l⟩
= ⟨x + k + m, y + l + n⟩
= f′ ⟨x + k, y + l⟩ c
= f′ (f d ⟨x + k, y + l⟩) c
So we can write
move = foldl f′ ⟨0, 0⟩
The commands are the same, but their meaning is a bit different now.
down X increases your aim by X units.
up X decreases your aim by X units.
forward X does two things:
So now the 2D state of the submarine is only altered by a forward command, and the sub has an additional state variable, the aim. aim also starts at 0.
The skeleton of the program is mostly the same. We need a new gene [const ⟨0, 0, 0⟩, g] for the move catamorphism. We’re only interested in the final horizontal position and depth, though, so we extract the initial two elements of the result with an aux. function.
move : [Command] → (Int × Int)
move = first_two ∘ foldl g ⟨0, 0, 0⟩
first_two ⟨x, y, _⟩ = ⟨x, y⟩
g : (Int × Int × Int) → Command → (Int × Int × Int)
g ⟨x, y, a⟩ (Forward k) = ⟨x + k, y + (a * k), a⟩
g ⟨x, y, a⟩ (Down k) = ⟨x, y, a + k⟩
g ⟨x, y, a⟩ (Up k) = ⟨x, y, a - k⟩
The new gene component g simply encodes the semantics for the movement commands.