展开方案中的功能 [英] unfold function in scheme

问题描述

目标:仅使用两个参数来实现unfold函数.

Goal: implement unfold function using only two arguments.

参数:

• 第一个参数f是f，它采用类型I的初始值，并返回nil或两个元素的cons对(这两个中的第一个是A列表中的下一个元素，下一个是初始值)再次具有某些I型值).
• 第二个参数是类型I的初始值，返回值是类型A的项目列表.

这是我到目前为止的内容，我不确定为什么它不起作用:

This is what I have so far and I am not sure why it is not working:

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

这应该是结果，但不是.我在做什么错了?

This should be the result but isn't. What am I doing wrong?

推荐答案

首先，它应该是(unfold descending 5).然后f将产生一对，并且您将使用它的两个分量，

First, it should be (unfold descending 5). Then f would produce a pair and you would use both components of it,

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

但是这具有非常大的计算复杂性，因为它每次迭代调用(f init) 3次.谦虚的

But this has awful computational complexity as it calls (f init) three times per iteration. A humble let binding remedies this.

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

以及使用命名为let

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

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

这篇关于展开方案中的功能的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！