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 s1 through s4 from S such that s1+s2+s3+s4 = 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.)

All
By category