как написать последовательность Коллатца, используя разворачивание в схеме/рэкете?

После написания функции генерации последовательности Коллатца обычным способом:

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

Я хотел написать это, используя 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))

И он работает, как и ожидалось, однако я не мог заставить его работать без использования «next-colatz-step» в качестве второго и третьего параметра развертывания. Почему? Кажется странным предоставлять один и тот же аргумент двум параметрам.


scheme racket collatz
person X10D    schedule 10.12.2016    source источник

Ответы (1)


arrow_upward
3
arrow_downward

Обратите внимание, что в обоих ваших решениях вы исключаете начальный элемент в последовательности, а в решении на основе unfold сгенерированная последовательность каким-то образом отстает от одной позиции, поэтому вам пришлось передать next-colatz-step дважды.

Если мы начнем с заданного числа n, вторым аргументом для unfold будет просто процедура identity, что кажется более естественным. Но это оставляет нам проблему, заключающуюся в том, что последнее значение (которое всегда должно быть 1, если предположить, что гипотеза Коллатца верна) теперь отсутствует. Поэтому теперь мы должны предоставить дополнительную процедуру генерации хвоста списка. Попробуй это:

(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)
person Óscar López    schedule 10.12.2016
comment
почему: (define (one n) (list 1)) имеет n в качестве параметра, даже если он не используется? - person X10D; 11.12.2016
comment
@ X10D это потому, что unfold ожидает процедуру с одним аргументом в качестве своего последнего аргумента, но мы уже знаем, что последним значением должно быть 1. Однако я обновил его, чтобы использовать параметр, в этот момент рекурсии n is 1. - person Óscar López; 11.12.2016
comment
Можно также написать тело collatz-seq как (unfold one? identity next-collatz-step n list). - person Meow; 08.05.2018