展开方案中的函数

Goal:实施unfold仅使用两个参数的函数。

论据：

• 第一个参数是 f，它接受某种类型 I 的初始值并返回 nil 或两个元素的 cons 对（这两个元素中的第一个是某种类型 A 的列表中的下一个元素，下一个初始值又是某些类型 I）。
• 第二个参数是某种类型 I 的初始值，返回的是类型 A 的项目列表。

这是我到目前为止所拥有的，我不确定为什么它不起作用：

(define (descending i)
  (if (= i 0)
    (list)
    (cons i (- i 1))))

(define nil (list))

(define (unfold f init)
  (if (eq? (f init) '())
    (list)
    (cons init (unfold f (f init)))))

(unfold (descending 5))

应该评估为

'(5 4 3 2 1)

这应该是结果，但不是。我究竟做错了什么？

首先，应该是(unfold descending 5). Then f会产生一对，你会使用它的两个组成部分，

(define (unfold f init)
  (if (eq? (f init) '())
      (list)
      (cons (car (f init)) (unfold f (cdr (f init))))))

但这具有可怕的计算复杂性，因为它称为(f init)每次迭代三次。一个谦虚的let https://docs.racket-lang.org/reference/let.html#%28form._%28%28lib._racket%2Fprivate%2Fletstx-scheme..rkt%29._let%29%29绑定可以解决这个问题。

(define (unfold f init)
  (let ((r (f init)))
    (if (empty? r) ;; instead of (eq? r '())
        (list)
        (cons (car r) (unfold f (cdr r))))))

和尾递归形式使用named let https://docs.racket-lang.org/guide/let.html#%28part._.Named_let%29

(define (unfold f init)
  (let loop ((acc empty)
             (state (f init)))
    (if (empty? state)
        (reverse acc)
        (loop (cons (car state) acc)
              (f (cdr state))))))

并使用match https://docs.racket-lang.org/reference/match.html.

(define (unfold f init)
  (let loop ((acc empty)
             (state (f init)))
    (match state
      ((cons x next)
       (loop (cons x acc)
             (f next)))
      (empty
       (reverse acc)))))