Thank you that helps a lot. I will start looking at how to implement a priority queue and get back to you with those results if I have any questions. Thanks again.

I am going to back track a little bit and try and figure out the A* graph search 1st but in order to do that I know that I need to construct a double ended priority queue that is capable of using a hash table to keep track of the search within the tree. Anyhow my question right now is why I am getting an error for this code:

<code>

;; The data structure we choose for the queue is a list
;; the first element of the list the front of thee queue
;; to dequeue an element, we essentially take the cdr of the list
;; to enqueue an element, we must put it at the end of the list,
;; so we can make a list of the element and append that onto the end of the queue

(define queue-maker
(lambda ()
(let ((q '()))
(lambda (msg)
(case msg
((type) "queue")
((empty?) (null? q))
((enqueue!) (lambda (element)
(let ((list-of-item (cons (element) '())))
(if (null? q)
(set! q list-of-item)
(append! q list-of-item)))))
((front) (if (null? q)
(error "front: The queue is empty.")
(car q)))
((dequeue!)
(if (null? q)
(error "dequeue! The queue is empty.")
(set! q (cdr q))))
((size) (length q))
((print) (display "FRONT: ")
(for-each
(lambda (x) (display x) (display " "))
q)
(newline))
(else (delegate base-object msg)))))))

(define q(queue-maker))
(q 'empty?)
(q 'enqueue! 'x)

<code>

The error message I recieve is this:

#<procedure>: expects 1 argument, given 2: enqueue! x

Also after I am done constructing the queue and hash table I might need some help with implementing it to get the A* search to work but that is all in time because right now I cant get my queue to work, yikes!

I found my mistake, the cons statement should be cons element '() not cons (element) '() and I have to call it like so((q 'enqueue!) 1) but I will be posting the priority queue and the heap soon so I will have questions on how that relates to the A* graph search algorithm.

So here is my double ended queue and an attempt at doing a hash table, I am reading from a book and trying to this as I read so I am confused as to what the book is doing because they do not specify very well as to what each argument and procedure is doing exactly so here is my queue:

<code>

(define queue-maker
(lambda ()
(let ((q '()) (rear '()))
(lambda (msg)
(case msg
((type) "queue")
((empty?) (null? q))
((enqueue!) (lambda (element)
(let ((list-of-item (cons element '())))
(if (null? q)
(begin
(set! rear list-of-item)
(set! q list-of-item))
(begin
(set-cdr! rear list-of-item)
(set! rear list-of-item))))))
((front) (if (null? q)
(error "front: The queue is empty.")
(car q)))
((dequeue!) (if (null? q)
(error "dequeue! The queue is empty.")
(begin
(set! q (cdr q))
(if (null? q)
(set! rear 'anything)))))
((size) (length q))
((print) (display "FRONT: ")
(for-each
(lambda (x)
(display x) (display " ")) q)
(newline))
(else (delegate base-object msg)))))))

</code>

And here is what the book describes as being the buckets for the hash table

<code>

(define bucket-maker
(lambda ()
(let ((table '()))
(lambda (msg)
(case msg
((type) "bucket")
((lookup)
(let ((key (2msg)) (succ (3msg)) (fail (4msg)))
(lookup key table
(lambda (pr)
(succ (cdr pr)))
fail)))
((update!)
(let ((key (2msg)) (updater (3msg)) (initializer(4msg)))
(lookup key table
(lambda (pr)
(set-cdr! pr (updater (cdr pr))))
(lambda ()
(let ((pr (cons key (initializer key))))
(set! table (cons pr table)))))))
(else (delegate base-object msg)))))))

</code>

I am really unsure how these buckets are being constructed so if anyone can show me an example using this particular bucket program that would be great because the book I am reading doesnt show any examples

And finally the making of the hash table

<code>

(define hash-table-maker
(lambda (size hash-fn)
(let ((v ((vector (lambda (i)
(bucket-maker)))
size)))
(lambda (msg)
(case msg
((type) "hash table")
(else
(delegate (vector-ref v (hash-fn (2msg)))
msg)))))))

</code>

The queue I understand completely the bucket and hash table not so much at least how it is being used in scheme I have programed bucket/hash tables in C++ so I understand the nuts and bolts behind it just not what scheme is doing with the code that has been given to me. So if anyone can clear me up on what exactly scheme is doing here that would be great. Also I apologize if this gets shoved over to the side because I understand how annoying that is but I don't know how to make it not do that.

Quote:

;; The data structure we choose for the queue is a list
;; the first element of the list the front of thee queue
;; to dequeue an element, we essentially take the cdr of the list
;; to enqueue an element, we must put it at the end of the list,
;; so we can make a list of the element and append that onto the end of the queue

That's a pretty heavyweight way to implement a queue, not only stylistically but algorithmically.

The enqueue operation takes linear time, which makes it pretty much unusable for most things that you'd use a queue for. It can be implemented more simply, and taking constant time. Check this out:

http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-22.html#%_sec_3.3.2

Quote: Also I apologize if this gets shoved over to the side because I understand how annoying that is but I don't know how to make it not do that.

Use square brackets instead of lt and gt for your code tags.

Quote: So if anyone can clear me up on what exactly scheme is doing here that would be great.

Use a better book, like SICP. In my opinion, the writer of the text you're using is enamored with using closures to simulate OO to the detriment of clarity and of providing decent implementations, as in the first queue example you gave with linear enqueue costs, and in the hash table example. I can't bring myself to read that code, and I like scheme.

It is very reasonable to expect that a hashtable be dynamically resized, if you're going to actually use it in the manner that they're generally used. It's also reasonable to expect clarity instead of cleverness in a book that teaches scheme. Because I'm in the mood, I'll try to make up for both; here's a straightforward and most unclever version (I'm tired).

First, the bucket representation. We'll use a list, and we'll do it in a purely functional way. This is both simpler than using mutable state (easier to debug) and has the same linear algorithmic characteristics as a more traditional imperative linked list in a bucket-chained hash implememntation; only constant factors differ. This means they're a potential candidate for optimization later, but won't make a catastrophic difference. So we'll need a way to add elements to a bucket, remove them, and search for an element with a given key (in linear time). The elements in the list are (key . value) pairs:

(define (remove-if p? l)  (define (helper res l)    (cond ((null? l)           l)        ((p? (car l))         (helper res (cdr l)))        (#t         (helper (cons (car l) res) (cdr l)))))  (helper (list) l))(define (make-bucket)  (list))(define (bucket-remove b key)  (remove-if (lambda (x) (= key (car x))) b))(define (bucket-add b key val)  (cons (cons key val) (bucket-remove b key)))(define (bucket-search b key)  (cond ((null? b)         #f)        ((= key (car (car b)))         (car b))        (#t         (bucket-search (cdr b) key))))

That's convenient. Next, we'll need a representation for the array that indexes into the chains. This data structure holds the array that points to each bucket and the number of elements currently held by all buckets (the fill factor); we'll call the structure 'chains'. We'll need the fill factor to decide when to resize the hashtable; we'll do it via exponential reallocation, and we'll consider a hashtable full when it has less than twice the number of buckets as it has elements (that makes us less dependent on hash function niceness).

A function to search this structure given a hash function is of utmost importance.

So the chains structure is a pair of (elements-in-structure . bucket-vector), and it is provided a hash function f to decide which bucket to put an element into:

(define (make-chains n)  (let ((v (make-vector n)))    (define (fill-vector idx)      (cond ((= idx (vector-length v))             (cons 0 v))            (#t             (vector-set! v idx (make-bucket))             (fill-vector (+ 1 idx)))))    (fill-vector 0)))(define (insert-chains! c f key val)  (let* ((num-elts (car c))         (v (cdr c))         (size (vector-length v))         (idx (hash-idx f key size))         (bucket (vector-ref v idx)))    (vector-set! v idx (bucket-add bucket key val))    (set-car! c (+ num-elts 1))))(define (store-k-v chains f k-v)  (insert-chains! chains f (car k-v) (cdr k-v)))(define (hash-idx f key size)  (remainder (f key) size))(define (lookup-chains c f key)  (let* ((v (cdr c))        (size (vector-length v))        (idx (hash-idx f key size)))    (bucket-search (vector-ref v idx) key)))

We'll also write a chains-for-each function, that applies a provided function to every key-value pair in the chains structure. That'll come in useful, both for implementing the resize operation and for general usage (most hashtables provide this functionality), and functions to abstract the fill number and the number of buckets in the table:

(define (chains-for-each c f)  (let* ((v (cdr c))         (size (vector-length v)))    (define (v-for-each idx)      (cond ((= idx size)             'end)            (#t             (for-each f (vector-ref v idx))             (v-for-each (+ idx 1)))))    (v-for-each 0)))(define (chains-fill c)  (car c))(define (chains-size c)  (vector-length (cdr c)))

In terms of these structures, the hashtable structure is very easy to write: it's just a pair of (hash function . chains structure). In fact, the only real responsibility it has is deciding when to resize the hash table (in this case, when the fill factor is larger than half the number of buckets):

(define (make-hash f)  (cons f (make-chains 4)))(define (hash-store! h key val)    (let* ((f (car h))         (chains (cdr h))         (num-elts (chains-fill chains))         (size (chains-size chains)))    (cond ((< size (* num-elts 2))           (let ((new-chains (make-chains (* 2 size))))             (chains-for-each chains                               (lambda (x) (store-k-v new-chains f x)))             (set-cdr! h new-chains)             (hash-store! h key val)))          (#t           (insert-chains! chains f key val)))))(define (hash-lookup h key)  (lookup-chains (cdr h) (car h) key))

And we're done (maybe there's a bug lurking, I'm tired). This hashtable implementation is very straightforward and automatically resizes, which means somebody might actually find it useful; it's rather more verbose and redundant than necessary, but it's easy to understand.

Of course, I leave hash-delete as an exercise for the reader.

Here's a few tests with the second worst hash function I could come up with:

(define h (make-hash (lambda (x) (+ x 1))))(hash-store! h 1 1)(display h)(newline)(hash-store! h 2 1)(display h)(newline)(hash-store! h 3 1)(display h)(newline)(hash-store! h 4 1)(display h)(newline)(hash-store! h 1 3)(display h)

So now my question comes back around to the Graph-Search Algorithm which is as follows:

function GRAPH-SEARCH(problem, fring) returns a solution, or failureclosed <-- an empty setfringe <-- Insert(make-node (initial-state[problem], fringe)loop do  if EMPTY? (fringe) then return failure  node <-- REMOVE_FIRST (fringe)  if GOAL-TEST[problem](STATE[node]) then return solution (node)  if STATE[node] is not closed then      add STATE[node] to closed      fringe <-- Insert-all(EXPAND(node, problem, fringe)

The set closed is implemented with the hash table to allow for efficient checking for repeated states.

The algorithm assumes that the first path to a state s is the cheapest.

So I am reading threw your code that was posted and I can't thank you enough for helping me understand the hash table and how it is to be used in scheme, anyhow my question becomes how the heck does this relate to the algorithm above. I understand the closed list stores every expanded node and the fringe/open list is the unexpanded nodes. The algorithm basically checks the current node and if it matches a node on the closed list it discards it instead of being expanded. So with that said I have no clue how to correlate that understanding to scheme code. I know the hash table will be used to store the closed list and the open list will be a priority queue (like a heap or something) but other than that I am very lost in how this will be implemented, I am hoping with all the code that has been given to me that you might be able to link it together so that I can see what is going on. Thank you so much for your time I really appreciate it.