Part 1

Scan a list of positive integers and give the number of times an integer was greater than the previous one.

Ignoring input, this is a function [ℕ] → ℕ, so it is clearly expressible as some sort of fold.

We could express it recursively by

depth_changes : [ℕ] → ℕ
depth_changes []            = 0
depth_changes [_]           = 0
depth_changes (x ∷ x′ ∷ xs) = if x < x’;
                                then 1 + (depth_changes xs);
                                else depth_changes xs

Clearly we’re pairing up each element with its successor, so why not factor this as some function count_changes : [(ℕ × ℕ)] → ℕ after a zip?


depth_changes xs = count_changes (zip xs (tail xs))

The recursive equations for count_changes are straightforward:

count_changes []            = 0
count_changes (⟨m, n⟩ ∷ ps) = if m < n;
                                then 1 + count_changes ps
                                else count_changes ps

This gives the following left fold:

count_changes = foldl f 0

f c ⟨m, n⟩ = if m < n then c + 1 else c

Alternatively, we could write this as a tupled fold. The base value could include the first number of the list to avoid introducing a spurious change, but here we take a slightly dumber approach: just subtract 1 from the result.

depth_changes ns = (fst (foldl compare ⟨0, 0⟩ ns)) - 1

compare : (ℕ × ℕ) → ℕ → (ℕ × ℕ)
compare ⟨c, m⟩ n = if m < n; then (c + 1, n); else (c, n)

I think I prefer the zipped version, which decomposes the problem nicely.

Part 2

Now we want to compute the number of times the sum over a sliding window increases. In the following example, we compare the sum over the "A window" with the sum over the B window, and so on.


199  A
200  A B
208  A B C
210    B C D
200  E   C D
207  E F   D
240  E F G
269    F G H
260      G H
263        H

The sums over two consecutive windows are always given by

w1 = x1 + x2 + x3
w2 = x2 + x3 + x4

and thus w1 < w2 iff x1 < x4. So we can avoid repetitive summing by reading the list in groups of four and comparing the first and last element of each group.

The following reflects an inaccurate understanding of the problem:

We can express this by window_changes = count compare_w ∘ chunks 4 where chunks divides a list into sublists of length ≤ 4.

This gives a much lower answer for test input, because these windows aren’t sliding! Using this strategy, you get this variation on the above diagram:


199  A
200  A B
208  A B
210    B
200  C
207  C D
240  C D
269    D
260  E
263  E F
...

We can devise a “sliding” list-chunker which gives successive sublists; e.g.

windows 3 [a, b, c, d, e]
    = [[a, b, c], [b, c, d], [c, d, e]]

This can be specified by the recursive equation

windows k []        = []
windows k (x ∷ xs′) = take k (x ∷ xs′) ∷ windows k xs′

Since the second equation depends on xs′, windows cannot be defined directly as a catamorphism. It’s more interesting to define it as an anamorphism:

windows k = unfoldr (frame k)

frame : Int → [α] → Maybe ([α], [α])
frame _ []       = Nothing
frame k (x : xs) = Just (take k (x : xs), xs)

So we can express all of the “frame overlaps” of interest by

filter length_four ∘ windows 4

Then it’s a matter of counting the increasing sums:

count compare_w ∘ filter length_four ∘ windows 4

where

count : (a → Bool) → [a] → ℕ;
count p ≡ length ∘ filter p

which can be expressed easily as the catamorphism

count p = foldl (λc x → if p x; then c + 1; else c) 0

This produces the right answer, but since we have a hylomorphism, it would be nice to “deforest” it through fusion. The first step is to fuse the count and filter; instead of using cata fusion, though, we simply combine the predicates compare_w and length_four–since, in fact, the domain of compare_w is restricted to length-four lists, anyway:


increasing : [ℕ] → Bool
increasing ns = (length ns == 4) ∧ (ns !! 0 < ns !! 3)

So now the hylomorphism is clear. We have the hylo operator for single-argument unfold as


hylo : (α → β → β) → β → (γ → Maybe (α, γ)) → γ → β
hylo f e g b = case g b of {
                 Nothing → e;
                 Just (x, b′) → f x (hylo f e g b′) }

characterized by


h = hylo f e g b ⇔ h = foldr f e . unfoldr g b

Thus


  depth_changes

=   { result above }

  count increasing ∘ windows 4

=   { count def., switching to foldr (second duality theorem) }

  foldr (λc ns → if increasing ns; then c + 1; else c) 0 ∘ windows 4

=   { windows def. }

  foldr (λc ns → if increasing ns; then c + 1; else c) 0
    ∘ unfoldr (frame k)

=   { hylo u.p. }

  hylo (λc ns → if increasing ns; then c + 1; else c)
       0
       (frame k)

where the base element b is the list argument. We can actually generalize this as a "counting" hylo which counts the number of notionally-constructed type that satisfy a given predicate:


count_hylo p g b = hylo (λc x → if p x; then c + 1; else c) 0 g b

Then we have


depth_changes = count_hylo increasing (frame k)

This is pretty compact. It does use space bounded by 4n for an input n-list, and clearly there are going to be list-scanning solutions which use constant space. It’s worth considering how we could derive those.

AOC 2021 Index

Home