развернуть функцию в схеме - PullRequest
Новая
       10

развернуть функцию в схеме

3 голосов
/ 15 февраля 2012

Цель: реализовать функцию unfold, используя только два аргумента.

Аргументы:

  • первый аргумент - это f, который принимает начальное значение некоторого типа I и возвращает ноль или пару минусов из двух элементов (первый из этих двух - следующий элемент, который входит в список некоторого типа А, а следующий начальный - снова значение некоторого типа 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)

Это должно быть результатом, но это не так. Что я делаю не так?

1 Ответ

5 голосов
/ 15 февраля 2012

Сначала должно быть (unfold descending 5).Тогда f создаст пару, и вы будете использовать оба ее компонента, 

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

Но это имеет ужасную вычислительную сложность, поскольку вызывает (f init) три раза за итерацию.Скромное let связывание исправляет это. 

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