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)))))
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)