Search code examples
schemeracketcollatz

how to write Collatz sequence using unfold in scheme/racket?


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.


Solution

  • 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)