SICP 問題 4.50

ランダムな順に探すrambを実装する．

(use srfi-27)
(define (random-car lst)
  (list-ref lst (random-integer (length lst))))

(define (rember item lst)
  (cond ((null? lst) '())
        ((eq? (car lst) item) (cdr lst))
        (else (cons (car lst)
                    (rember item (cdr lst))))))

(define (analyze-amb exp)
  (let ((cprocs (map analyze (amb-choices exp))))
    (lambda (env succeed fail)
      (define (try-next choices)
        (if (null? choices)
            (fail)
            ((car choices) env succeed (lambda ()
                                         (try-next (cdr choices))))))
      (try-next cprocs))))

(define (analyze-ramb exp)
  (let ((cprocs (map analyze (amb-choices exp))))
    (lambda (env succeed fail)
      (define (try-next choices)
        (if (null? choices)
            (fail)
            (let ((first (random-car choices)))
              (first env succeed (lambda ()
                                   (try-next (rember first choices)))))))
      (try-next cprocs))))

(define (ramb? exp) (tagged-list? exp 'ramb))

(define (analyze exp)
  (cond ((self-evaluating? exp) (analyze-self-evaluating exp))
        ((quoted? exp) (analyze-quoted exp))
        ((variable? exp) (analyze-variable exp))
        ((assignment? exp) (analyze-assignment exp))
        ((definition? exp) (analyze-definition exp))
        ((amb? exp) (analyze-amb exp))
        ((ramb? exp) (analyze-ramb exp))
        ((if? exp) (analyze-if exp))
        ((lambda? exp) (analyze-lambda exp))
        ((let? exp) (analyze (let->combination exp)))
        ((begin? exp) (analyze-sequence (begin-actions exp)))
        ((cond? exp) (analyze (cond->if exp)))
        ((application? exp) (analyze-application exp))
        (else (error "Unknown expression type: ANALYZE" exp))))

test

;;; Amb-Eval input:
(ramb 1 2 3 4 5 6)

;;; Starting a new problem
;;; Amb-Eval value:
6

;;; Amb-Eval input:
try-again

;;; Amb-Eval value:
5

;;; Amb-Eval input:
try-again

;;; Amb-Eval value:
1

;;; Amb-Eval input:
try-again

;;; Amb-Eval value:
4