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.
AOC 2021 Index