3

After writing the Collatz sequence generating function the regular way:

(define (colatz-seq #;starting@ n)
  (cond ((= n 1) '())
        ((even? n) (cons (/ n 2) (colatz-seq (/ n 2))))
        ((odd? n) (cons (+ (* n 3) 1) (colatz-seq (+ (* n 3) 1))))))

I wanted to write it using unfold:

(define (next-colatz-step n)
  (cond ((even? n) (/ n 2))
        ((odd? n) (+ (* n 3) 1))))

(define (one? n)
  (= n 1))

(define (colatz-seq #;starting@ n)
  (unfold one? next-colatz-step next-colatz-step n))

And it works as expected however i couldn't get it to work without using "next-colatz-step" as both the second and third parameter of unfold. Why? It seems kinda of odd to provide the same argument to two params.

1 Answer 1

3

Notice that in both of your solutions you're excluding the starting element in the sequence, and that in the unfold-based solution the generated sequence is somehow lagging behind one position, that's why you had to pass next-colatz-step twice.

If we start from the given n number, the second argument for unfold is just the identity procedure, which seems more natural. But that leaves us with the problem that the last value (which should always be 1, assuming that the Collatz conjecture is true) is now missing. That's why now we have to provide an additional procedure for generating the tail of the list. Try this:

(require srfi/1)

(define (one? n)
  (= n 1))

(define (next-collatz-step n)
  (cond ((even? n) (/ n 2))
        (else (+ (* 3 n) 1))))

(define (last-value n)
  (list n))

(define (collatz-seq n)
  (unfold one? identity next-collatz-step n last-value))

(collatz-seq 10)
=> '(10 5 16 8 4 2 1)
3
  • why does: (define (one n) (list 1)) have n as param even tough it's not used?
    – X10D
    Dec 11, 2016 at 1:08
  • @X10D that's because unfold expects a one-arg procedure as its last argument, but we already know that the last value has to be 1. However, I updated it to use the parameter, at that point in the recursion n is 1. Dec 11, 2016 at 2:31
  • One might also write the body of collatz-seq as (unfold one? identity next-collatz-step n list).
    – Meow
    May 8, 2018 at 5:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.