4sum

One more from Programming Praxis, this time we’re dealing with summing combinations of a sequence. More formally, given a secquence S, either choose four elements s_1 through s_4 from S such that s_1 + s_2 + s_3 + s_4 = 0 or verify that it isn’t possible. This immediately makes me about working through possible solutions until we find one and then bailing out, ergo call/cc:

(define (4sum ls)
(call/cc (lambda (exit)
(for-each (lambda (i)
(for-each (lambda (j)
(for-each (lambda (k)
(for-each (lambda (l)
(when (= 0 (+ i j l k))
(exit (list i j k l))))
ls))
ls))
ls))
ls)
(exit #f))))

It may look funny, but it works great:

~ (4sum '(2 3 1 0 -4 -1))
(2 2 0 -4)

~ (4sum '(3 1 0 -4))
(3 1 0 -4)

~ (4sum '(1 1 1 1))
#f

I think that this may have been the first time that I legitimately used call/cc without being told to do so and I have to admit… I’m a convert. It’s kind of powerful. (Even if I’m not using a fraction of what I’m capable of.)

Alternatively, we can write a more Rackety solution, using for*/first to loop over the values and return the first matching case:

(define (4sum ls)
(for*/first ([i (in-list ls)]
[j (in-list ls)]
[k (in-list ls)]
[l (in-list ls)]
#:when (= 0 (+ i j k l)))
(list i j k l)))

Under the hood, it’s doing much the same thing, so it really comes down to which style looks more natural to you.