today I solve the N-queen problem using Scheme but it is extremely slow compared to the same version of Python. when N = 8, Scheme takes 90+ seconds! I know one reason is that I can't use a generator in Scheme, my code has to form large lists first, which is a nightmare for memory and calculation.
There is few topics about generator in Scheme, this one is the only one I found maybe useful but sadly it doesn't work in both racket or chez scheme.
Actually, I just want a simple version of python generator, that is, do not form the whole list, just send me one value at one time. i.e:
(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.
If this is hard, any related links or similar implementation topics are also appreciated. I'm really tired of searching. Thanks!
This is my N-queen Scheme code, if needed:
(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))
Using continuations for this case (as suggested in the link) is unjustified. Here's a simpler idea: let's define our generator as a thunk (a no-args function) that stores as part of its environment the starting point, the maximum allowed value, the increment and the current element. Every time we call the procedure, the current element will be updated. The following code behaves similar to Python 3.x range() function (or Python 2.x xrange()):
(define (generator start stop step)
(let ((current (- start 1)))
(lambda ()
(cond ((>= current stop) #f)
(else
(set! current (+ current step))
current)))))
Now the next procedure will simply call the generator until the maximum value is reached, at this point the generator will start returning #f for each subsequent call:
(define (next generator)
(generator))
For example:
(define g (generator 0 3 1))
(next g) ; 0
(next g) ; 1
(next g) ; 2
(next g) ; 3
(next g) ; #f
Another alternative would be to use streams, but I'll stick with the above solution, it's simple enough and should work on any Scheme interpreter. And yet another alternative - if you're coding in Racket, just use a sequence (which is also a stream), like this:
(for ([i (in-range 0 4 1)])
(display i))
=> 0123