;; bfs search for a number
;;
;; This procedure makes it easy to generate
;; output...
(define show 
  (lambda x
	(map display x)))


;; successor states of a state numbered x are x-1 and x+1

(define (successor x)
  (list (- x 1) (+ x 1)))

;; Breadth first seach example. Uses a BFS to search for a number (goal)
;; in search tree rooted at startnum. The successor function is used to
;; generate a list of child states.
;;
;; This procedure generates a trace of what it is doing, displaying
;; a line each time it visits a state
;;
;;  bfs keeps a queue (list) of states it needs to explore
;;  Each time it looks at a state, it generates the list of
;;  successor states checks for the goal state, and if not found
;;   adds the successor states to the queue.
;;
;;  bfs uses a named let to introduce the queue which initially
;;   holds only the start state.
;;   The recursion is all on the named let instead of the
;;   top level bfs procedure
;;
;; NOTE: This version makes no attempt to avoid re-visiting states
;;  (it will visit the same state many times)

(define (bfs startnum goal)
  ;; named let. initialize states with list of
  ;; all successor states. We will recurse over this
  ;; list using the named let.
  (let bfs-helper ((states (list startnum)))
	(if (null? states)
		(begin
		  (show "FAILURE: ran out of states!\n")
		  #f)
		(let ((nextstate (car states)))
		  (show "state: " nextstate "\n")
		  (if (equal? goal nextstate)
			  (begin
				(show "GOAL FOUND: " nextstate "\n")
				#t)
			  (begin
				(bfs-helper (append (cdr states) (successor nextstate)))))))))

;; here is a sample call:
;;   start at 0, find the number 3.
(bfs 0 3)