今天我使用Scheme解决了n皇后问题，但是与相同版本的Python相比，它非常慢。当N = 8时，Scheme需要90秒以上!我知道一个原因是我不能在Scheme中使用生成器，我的代码必须首先形成大列表，这对于内存和计算来说是一个噩梦。
Scheme中关于生成器的主题很少，这一个是我发现的唯一一个可能有用的，但遗憾的是它在球拍或chez Scheme中都不起作用。
实际上，我只想要一个简单版本的python生成器，也就是说，不形成整个列表，每次只给我一个值。即:
(range 100000) ; will consume a large memory
(define g (generator 100000)) ; will do nothing
(next g) ;0 <-you call it with next one time, it returns one value
(next g) ;1
;...
(next g) ;100000
(next g) ;return a value that indicates the end, such as #f.
如果这是困难的，任何相关的链接或类似的实现主题也赞赏。我真的找腻了。谢谢!
这是我的N-queen Scheme代码，如果需要的话:
(define (range n)
(define (recur n)
(if (= n -1)
'()
(cons n (recur (- n 1)))))
(recur (- n 1)))
(define (flatten a)
(if (null? a)
'()
(append (car a) (flatten (cdr a)))))
(define (safe? x y sln)
(if (null? sln)
#t
(let ((px (car (car sln))) (py (cadr (car sln))))
(if (or (= y py) (= (- py y) (- px x)) (= (- py y) (- x px)))
#f
(safe? x y (cdr sln))))))
(define (nqueen n)
(define (recur x)
(if (= x -1)
(list '())
(flatten (map (lambda (y) (map (lambda (sln) (cons (list x y) sln)) (filter (lambda (sln) (safe? x y sln)) (recur (- x 1))))) (range n)))))
(recur (- n 1)))
(define (pl a)
(if (null? a)
'()
(begin (display (car a)) (display "n") (pl (cdr a)))))
(pl (nqueen 4))
在这种情况下使用延续(如链接中建议的那样)是不合理的。这里有一个更简单的想法:让我们将生成器定义为一个thunk(一个无参数函数)，它将起点、最大允许值、增量和当前元素存储为其环境的一部分。每次调用该过程时，都会更新当前元素。以下代码的行为类似于Python 3。x range()函数(或Python 2。x xrange()):
(define (generator start stop step)
(let ((current (- start 1)))
(lambda ()
(cond ((>= current stop) #f)
(else
(set! current (+ current step))
current)))))
现在next过程将简单地调用生成器，直到达到最大值，此时生成器将开始为每个后续调用返回#f:
(define (next generator)
(generator))
(define g (generator 0 3 1))
(next g) ; 0
(next g) ; 1
(next g) ; 2
(next g) ; 3
(next g) ; #f
另一种选择是使用流，但我将坚持使用上面的解决方案，它足够简单，应该适用于任何Scheme解释器。还有另一种选择——如果你在用Racket编程，只需使用序列(也是一个流)，就像这样:
(for ([i (in-range 0 4 1)])
(display i))
=> 0123
我有一个make-iterator过程，使用狡猾的提示来实现spidermonkey生成器(类似于ECMAScript 6生成器，但不完全相同)。由于racket也有提示符，这应该直接翻译为racket的call-with-continuation-prompt和abort-current-continuation，以代替guile的call-with-prompt和abort-to-prompt。
代码如下:
;; this procedure takes a generator procedure, namely a procedure
;; which has a 'yield' parameter for its first or only argument,
;; followed by such other arguments (other than the one for the
;; 'yield' parameter) as the generator procedure requires, and
;; constructs an iterator from them. When the iterator is invoked, it
;; will begin executing the procedure unless and until the argument
;; comprising the yield procedure is called, which will cause the
;; iterator to suspend computation and instead return the value passed
;; to yield (yield is a procedure taking one argument). If invoked
;; again, the iterator will resume computation at the point where it
;; last left off (returning a list of the values, if any, passed to
;; the iterator on resuming). When the generator procedure has
;; executed to the end, the iterator returns 'stop-iteration. This
;; procedure is intentionally modelled on javascript/spider-monkey
;; generators. It has some resemblance to call/ec, except that (i)
;; instead of executing the passed procedure immediately, it returns
;; an iterator which will do so, (ii) it is resumable, and (iii) the
;; procedure to be executed can receive starting arguments in addition
;; to the yield/break argument, to provide an alternative to binding
;; them with a lambda closure.
(define (make-iterator proc . args)
(define tag (make-prompt-tag))
(define send-back '())
(define (thunk)
(apply proc
(lambda (val)
(abort-to-prompt tag val)
send-back)
args)
;; the generator procedure has returned - reset thunk to do
;; nothing except return 'stop-iteration and return
;; 'stop-iteration after this last call to proc
(set! thunk (lambda () 'stop-iteration))
'stop-iteration)
(lambda send-args
(set! send-back send-args)
(call-with-prompt tag
thunk
(lambda (cont ret)
(set! thunk cont)
ret))))
以下是管道衬砌程序:
;; for-iter iterates until the iterator passed to it (as constructed
;; by make-iterator) returns 'stop-iteration. It invokes the procedure
;; passed as a second argument with the value yielded by the iterator
;; on each iteration. It is mainly used for composing lazy operations
;; by pipelining, as for example with lazy-map and lazy-filter.
(define (for-iter iter proc)
(let loop()
(let ([val (iter)])
(if (not (eq? val 'stop-iteration))
(begin
(proc val)
(loop))))))
;; lazy-map is a procedure which takes an input iterator constructed
;; by make-iterator and a standard procedure, and then returns another
;; iterator (the output iterator) which yields the values obtained by
;; applying the standard procedure to the input iterator's yielded
;; values.
(define (lazy-map iter proc)
(make-iterator (lambda (yield)
(for-iter iter (lambda (val) (yield (proc val)))))))
;; lazy-filter is a procedure which takes an input iterator
;; constructed by make-iterator, and then returns another iterator
;; (the output iterator) which yields such of the values yielded by
;; the input iterator as are those for which the predicate proc
;; returns #t
(define (lazy-filter iter proc)
(make-iterator (lambda (yield)
(for-iter iter (lambda (val) (if (proc val) (yield val)))))))
下面是Rhino第6版第280页的典型反例:
(define (counter yield initial)
(let loop ([next-value initial])
(let ([increment (yield next-value)])
(if (not (null? increment))
(if (eq? (car increment) 'reset)
(loop initial)
(loop (+ next-value (car increment))))
(loop (+ 1 next-value))))))
(define counter-iter (make-iterator counter 10)) ;; create iterator at 10
(display (counter-iter))(newline) ;; prints 10
(display (counter-iter 2))(newline) ;; prints 12
(display (counter-iter 'reset))(newline) ;; prints 10
我也有一个回指版本作为宏，它将yield键名注入到代码体中，但我更喜欢上面的方法。
编辑:对于不支持提示的方案实现，以下操作与使用提示的版本相同。然而，对于guile，提示比使用完整的call/cc延续更有效(我想这并不一定适用于所有实现):
(define (make-iterator proc . args)
(define prompt-cont #f)
(define iter-cont #f)
(define done #f)
(define (yield arg)
(call/cc
(lambda (k)
(set! iter-cont k)
(prompt-cont arg))))
(lambda send-back
(if done
'stop-iteration
(call/cc
(lambda (k)
(set! prompt-cont k)
(if iter-cont
(iter-cont send-back)
(begin
(apply proc yield args)
(set! done #t)
(prompt-cont 'stop-iteration))))))))
经典序列可以在ChezScheme中用几行实现。以下是我的版本:
(library (seq)
(export seq hd tl range smap force-seq for)
(import (scheme))
(define-syntax seq
(syntax-rules ()
((_ a b) (cons a (delay b)))))
(define hd car)
(define (tl s) (force (cdr s)))
(define (range-impl a b s)
(cond ((< a b) (seq a (range-impl (+ a s) b s)))
(else '())))
(define (range a . b)
(cond ((null? b) (range-impl 0 a 1))
((null? (cdr b)) (range-impl a (car b) 1))
(else (range-impl a (car b) (cadr b)))))
(define (smap f s)
(cond ((null? s) '())
(else (seq (f (hd s)) (smap f (tl s))))))
(define (force-seq s)
(when (not (null? s))
(force-seq (tl s))))
(define-syntax for
(syntax-rules ()
((_ v r body ...) (force-seq (smap (lambda (v) body ...) r)))))
)
用法:
(import (seq))
(for x (range 5 12)
(display x)
(newline))
使用序列可以很容易地以python方式从文件中读取行:
(library (io)
(export getline lines)
(import (scheme))
(import (seq))
(define (getline ip)
(define (copy-line)
(let ((c (get-char ip)))
(unless (or (eof-object? c)
(eqv? c '#newline))
(display c)
(copy-line))))
(let ((c (peek-char ip)))
(cond ((eof-object? c) #f)
(else (with-output-to-string copy-line)))))
(define (lines ip)
(let ((l (getline ip)))
(cond (l (seq l (lines ip)))
(else '()))))
)
可以这样写:
(import (seq))
(import (io))
(for l (lines (current-input-port))
(display l)
(newline))
我发现do的执行速度明显快于遍历列表:
(do ((i 0 (add1 i)))
((= i 100000) 'result)
(some-function! i some-data))
如果你想要更多的功能，球拍文档建议in-list与for及其变体一起使用。
(for/list ((i (in-list (range 0 100000))))
(some-function i some-data))