Переводите функции Q и P из The Little Schemer в Common Lisp? - PullRequest
Новая
       43

Переводите функции Q и P из The Little Schemer в Common Lisp?

3 голосов
/ 11 ноября 2009

В главе 9 «Маленького интрижка» автор представляет следующие две функции 

(define Q 
  (lambda (str n) 
    (cond 
      ((zero? (remainder (first$ str ) n)) 
        (Q (second$ str ) n)) 
      (t (build (first$ str ) 
        (lambda ( ) 
          (Q (second$ str ) n))))))) 

(define P
  (lambda (str)
    (build (first$ str)(lambda () (P (Q str (first$ str)))))))

и предлагает, чтобы они оценивались со следующим исполнением: 

(frontier (P (second$ (second$ int)))  10)

Как бы вы написали функции P и Q в Common Lisp?

(Я перевел Y-Combinator сам, но мне это кажется сложным)

- Вспомогательные функции - 

(define frontier
  (lambda (str n)
    (cond
      ((zero? n) (quote ()))
        (t (cons (first$ str) (frontier (second$ str) (sub1 n)))))))

(define str-maker
  (lambda (next n)
    (build n (lambda () (str-maker next (next n))))))

(define int (str-maker add1 0))

(define second$
  (lambda (str)
    ((second str))))

(define first$ first)

(define build
  (lambda (a1 a2)
    (cond
      (t (cons a1
        (cons a2 (quote ())))))))))

(define first
  (lambda (p)
    (cond
       (t (car p)))))

(define second
  (lambda (p)
    (cond
      (t (car (cdr p))))))

(define add1 
  (lambda (n)
    (+ 1 n)))

(define remainder 
  (lambda  (n m)
    (cond
      (t (- n (* m (/ n m ))))))

(Отказ от ответственности - это не вопрос домашнего задания - это для моего понимания и изучения)

1 Ответ

6 голосов
/ 13 ноября 2009

Я предположил:

  • В определении P с помощью "(Q (str (first $ str)))" вы имели в виду: "(Q str (first $ str))", так как Q является функцией с двумя аргументами.
  • build - это помощник, который создает что-то, над чем работают первый $ и второй $: list

Имея это в виду, прямой перевод Scheme на Common Lisp дает: 

(defun first$ (list) (first list))
(defun second$ (list) (funcall (second list)))
(defun build (a b) (list a b))

(defun frontier (str n)
  (if (zerop N)
    ()
    (cons (first$ str) (frontier (second$ str) (1- n)))))

(defun str-maker (next n)
  (list n (lambda () (str-maker next (funcall next n)))))

(setq int-maker (str-maker #'1+ 0))

(defun Q (str n)
  (if (zerop (rem (first$ str) n))
    (Q (second$ str) n)
    (list (first$ str) (lambda () (Q (second$ str) n)))))

(defun P (str)
  (list (first$ str) (lambda () (P (Q str (first$ str))))))

(frontier (P (second$ (second$ int-maker))) 10)

Чья последняя строка возвращает: 

(2 3 5 7 11 13 17 19 23 29)

хорошо известная серия, поэтому я предполагаю, что перевод успешен: -)

...