|
|||||||||
|
|||||||||
| |||||||||
|
|||||||||
|
|||||||||
| |||||||||
|
|
|
| |||||||||
 |
|
|
«
Previous Thread
|
Next Thread
»
|
Thread Tools | Search this Thread | Rate Thread | Display Modes |
Dev Shed Forums Sponsor:
|
|
Get inside! Sample the range of functionality easily built with JMSL Library for Time Series Data Analysis, Heat Maps, Portfolio Optimization, Monte Carlo Simulation, Stock Price Charting and more. Download Now! |
|
#16
April 5th, 2006, 04:57 PM
|
|||
|
|||
|
I see. Hmm, im getting the idea. However, with the last code... when i run it i get something that says "#<procedure:dispatch>"
Is that suppose to happen? Also, is it possible to start off with a queue that already has elements in it and then add/remove?
|
|
#17
April 5th, 2006, 06:35 PM
|
||||
|
||||
|
Quote:
Yep. This is the actual value of the variable q in that last example: the closure for the function (dispatch), which had been returned by (make-queue) earlier. I included it to show a) what the closure actually is, and b) why you couldn't just print the value of q from the top-level interpreter the way you could in the other versions. Quote:
Yes; we can change the constructor functions so that they can take multiple arguments, either by using a list for the argument or by using variable arity. In fact, this would actually make the constructor easier in this case, as the current version has to create a list out of the initial argument; taking multiple arguments, they would already be a list, so we can just assign the value to queue directly: Code:
(define (make-queue . top) (define queue top) ;; ... and so on The period, when used in the formal parameter list of a function, indicates that the function should take several separate variables, then put them all into the variable following the period as a list. So, given this, you would then be able to write: Code:
(define q (make-queue 1 2 3 4)) (q 'value) ... and the interpreter would return (1 2 3 4) as the value of the queue.
__________________
Rev First Speaker Schol-R-LEA;2 JAM LCF ELF KoR KCO BiWM TGIF #define KINSEY (rand() % 7) λ Scheme is the Red Pill Scheme in Short • Understanding the C/C++ Preprocessor Taming Python • A Highly Opinionated Review of Programming Languages for the Novice, v1.1 FOR SALE: One ShapeSystem 2300 CMD, extensively modified for human use. Includes s/w for anthro, transgender, sex-appeal enhance, & Gillian Anderson and Jason D. Poit clone forms. Some wear. $4500 obo. tverres@et.ins.gov
|
|
#18
April 5th, 2006, 06:56 PM
|
||||
|
||||
|
Nice work Schol-R, I'm not sure that you represented functional programming to it's upmost though. That said its personal preference and Scheme doesn't dictate what style you use either way
 .A queue is really nothing more than a list and some simple actions for interacting with it. Now if a queue is just a list and lists are so frequently used in a functional manor you have to wonder why it's necessary to produce an object with all the state changes that implies. Why not just use the queue in your program like you would any other list? To answer your question Mochi yes you can start of with more than one value however you'll have to make a simple change to the code: Code:
(define (make-queue top) (define queue (list top)) ... Code:
(define (make-queue . queue)
; removed the queue definition
...
Now whatever you pass to the function will automatically be a list, and you can pass in as many arguments as you like. This saves you a little bit of work too .Heres a small example of this using a very small function so you have a better idea of whats going on. Code:
> (define (a . b)
b)
> (a 1 2 3 4)
(1 2 3 4)
> (a 1)
(1)
>
The reason that you're getting a procedure displayed is because q is holding the procedure returned when the queue was made .The 'value method should return the queue in a printable manor (it's just a list). Remove the 'q at the very end and it should act more like you expected. EDIT: Awesome. Schol-R seems to have beat me to it .Take care, Mark. Last edited by netytan : April 5th, 2006 at 06:58 PM.
|
|
#19
April 5th, 2006, 07:40 PM
|
|||
|
|||
|
Oh i see. Wow, that minor change makes a world of a differenct. So now the new code for a Queue to take multiple arguments is
Code:
(define (make-queue . top)
(define queue top)
(define (add! new-item)
(set! queue (append queue (list new-item))))
(define (value)
queue)
(define (next!)
(if (null? queue)
'()
(let ((next (car queue)))
(set! queue (cdr queue))
next)))
(define (dispatch method . parameters)
(case method
('add! (if (null? parameters)
queue
(add! (car parameters))))
('value (value))
('next! (next!))
(else 'invalid-method)))
dispatch)
The test code that i used is dereived from Schol-R-Lea's original code as follows. By the way, i notice that although "(q 'value)" occurs 3 times in the test code they all return different results. Hmm... Code:
(define q (make-queue 1 2 3 4 5 6 7 8)) (q 'value) (q 'add! 2) (q 'value) (q 'next!) (q 'value) q The results were so Code:
(1 2 3 4 5 6 7 8) (1 2 3 4 5 6 7 8 2) 1 (2 3 4 5 6 7 8 2) #<procedure:dispatch> My question now is this... suppose i wanted the code to return a queue but this time i want to get rid of the numbers less that say "5" out of the queue For example --> (5 6 7 8) would be the desired new queue. Would there have to be some kind of comparison operation to do that? Also something i notice, i added a "2" but it still stays at the end... I thought it might have gone next to the already existing "2"
|
|
#20
April 5th, 2006, 08:04 PM
|
||||
|
||||
|
Quote:
For that I'd use filter, it's not standard in most Scheme systems but heres my implementation: Code:
(define filter
(lambda (fn values)
"This function is a tail-recursive implementation of the filter
function found in other Lisp dialect."
(let loop ((list values)
(rest '()))
(if (pair? list)
(let ((item (car list))
(next (cdr list)))
(if (fn item)
(loop next (cons item rest))
(loop next rest)))
(reverse rest)))))
This is purely functional, if you want it to be destructive (change the value given) then you'll have to make a few changes. If not then you can simply use the value or save it for later  .Code:
> (list 5 2 6 7 1 2 3 2 4 6 7 8 0 9) (5 2 6 7 1 2 3 2 4 6 7 8 0 9) > (define a-list (list 5 2 6 7 1 2 3 2 4 6 7 8 0 9)) > a-list (5 2 6 7 1 2 3 2 4 6 7 8 0 9) > (filter (lambda (e) (> e 4)) a-list) (5 6 7 6 7 8 9) > 2 doesn't get pushed in by the other 2 because that's not a queue, in a queue the last item added goes onto the end of the queue and the first to be removed is always at the front. Think real life .Take care, Mark. Last edited by netytan : April 5th, 2006 at 08:46 PM. Reason: Fix broken code tag
|
|
#21
April 5th, 2006, 08:51 PM
|
||||
|
||||
|
Quote:
I have to admit that I was rather brief with the FP example, partly because I wanted to get on with demonstrating the other possible approaches, and partly because I felt that, since this problem appeared to be focused primarily on a persistent mutable data structure, a procedural or OO solution seemed more appropriate. I tend to mix paradigms to a degree which many others find discomforting , and while I generally lean towards FP approaches, I will switch to a different approach if I feel that the FP one isn't the most effective for the matter at hand. Also, the example is somewhat skewed because I was using it at the top level and redefining the same variable time and again. In actual FP code, the queue as a conceptual data structure - as opposed to as a specific variable or list - would be passed from function to function, used to assign separate variables in (let) statements, and so forth without it necessarily being bound to any global symbol at all. So part of the problem is with how I was demonstrating the code rather than with the code itself. In any case, it can be noted that the functional version is the simplest of the examples I wrote, and probably the easiest to understand, but it does require extra effort on the part of the programmer using the functions. It is probably the case that a less cumbersome version that is nonetheless FP could be written, but I was concentrating on explanations, not on paradigms. Last edited by Schol-R-LEA : April 5th, 2006 at 09:48 PM.
|
|
#22
April 5th, 2006, 10:08 PM
|
||||
|
||||
|
Quote:
I can see your point, short of writing the program it's hard to show how the queue will exist .My approach is a little different: I try and use FP as much as possible and only introduce side effects when I can't get around them — which isn't very common  — and then I encapsulate them as much as possible.Take care Schol-R, Mark.
|
|
#23
April 5th, 2006, 11:07 PM
|
|||
|
|||
|
Quote:
Oh i see, so a queue does not necessarily have to be ordered. Alright, i get that. I suppose the postion of the elements does not matter.  I saw these codes about Priority Queues.  Code:
(define (create-priority-q less?) (make-binary-heap (lambda (el1 el2) (less? (car el1) (car el2))))) (define (priority-q:get-min-element pq) (binary-heap:get-root pq)) (define (priority-q:get-min pq) (cdr (priority-q:get-min-element pq))) (define (priority-q:get-min-key pq) (car (priority-q:get-min-element pq))) (define (priority-q:insert! pq key datum) (binary-heap:insert! pq (cons key datum))) (define (priority-q:delete-min! pq) (binary-heap:delete-root! pq)) (define (priority-q:empty? pq) (binary-heap:empty? pq)) (define (priority-q:length pq) (binary-heap:size pq)) By reading them i sorta see what's going on... ish. The first one seems to be comparing two things to see which one is less. A good question would be, where does the smaller item go afterwards? As for the rest, it appears as if there must already be some existing queue to extract a minimum element from and put in new elements, right? How do i test these things to see if they make sense? And what does Binary Heap have to do with any of this? 
|
|
#24
April 6th, 2006, 02:03 AM
|
||||
|
||||
|
Heaps are tree structure that can be used to implement priority queues efficiently; in a properly implemented heap, the highest (or lowest, depending) value is always at the root of the tree. A binary heap is one in which the tree is also a balanced binary tree. Apparently, the code in question uses an existing binary heap data type to build the priority queue type; without knowing more about how the type is meant to be used, anything said about it is speculation. If you are going to try and use this code, you would need the source for the binary heap type first. (EDIT: it is also possible to write your own binary heap type, then modify the priority queue code to match your type. You could even try to write to match the function signatures of the binary heap type used here, but it would be difficult since we don't know the exact behavior of that type and may introduce some differences unintentionally.)
That having been said, this constructor function: Code:
(define (create-priority-q less?) (make-binary-heap (lambda (el1 el2) (less? (car el1) (car el2))))) ... appears to be taking a predicate, (less?), and then creating a new unnamed predicate which compares the first elements of a pair of lists; it is passing the resulting function to the binary tree contructor. The final result is an empty priority queue. The insertion operator is a little clearer: Code:
(define (priority-q:insert! pq key datum) (binary-heap:insert! pq (cons key datum))) This function (or more likely, macro, since the exclaimation point implies that it performs a destructive update) takes the priority queue, a key, and the data which the prirority queue is ordering. It creates a new data structure comprised of a list whose elements are the key and the datum, which it then gives to the binary heap insertion function along with the queue itself. Presumably, the (binary-heap:insert!) uses the unnamed predicate that was passed to (make-binary-heap) to compare the keys, and insert the key-data pairs into the heap in least-first order. Thus, to create a priority queue that compares numeric keys using the standard less-than operator, and then insert a series of values, the resulting priority queue might develop something like this (the resulting queue tree structure is in italic bold; it would not actually appear in practice): Code:
(define my-pq (create-priority-q <)) (priority-q:insert! my-pq 3 'a) '((3 'a)) (priority-q:insert! my-pq 6 'b) '((3 'a) ((6 'b))) (priority-q:insert! my-pq 1 'c) '((1 'c) ((3 'a)) ((6 'b))) (priority-q:insert! my-pq 4 'd) '((1 'c) ((3 'a) ((4 'd))) ((6 'b))) (priority-q:insert! my-pq 2 'e) '((1 'c) ((2 'e) ((3 'a)) ((4 'd))) ((6 'b))) HTH. C&CW. Last edited by Schol-R-LEA : April 6th, 2006 at 04:36 PM.
|
|
#25
April 6th, 2006, 04:34 PM
|
|||
|
|||
|
Okay, i am kinda lost. I am not sure what i am doing wrong to get this error but check it out.
I entered this into the editor window Code:
(define (create-priority-q less?) (make-binary-heap (lambda (el1 el2) (less? (car el1) (car el2))))) (define (priority-q:get-min-element pq) (binary-heap:get-root pq)) (define (priority-q:get-min pq) (cdr (priority-q:get-min-element pq))) (define (priority-q:get-min-key pq) (car (priority-q:get-min-element pq))) (define (priority-q:insert! pq key datum) (binary-heap:insert! pq (cons key datum))) (define (priority-q:delete-min! pq) (binary-heap:delete-root! pq)) (define (priority-q:empty? pq) (binary-heap:empty? pq)) (define (priority-q:length pq) (binary-heap:size pq)) Then in the listener window i entered the code you provided Schol-R-Lea (without the bold italic stuff) and i getting this error. Code:
> (define my-pq (create-priority-q <)) (priority-q:insert! my-pq 3 'a) . reference to undefined identifier: make-binary-heap > I tried editing the code in the editor window to say this instead Code:
(define (create-priority-q <)
(make-binary-heap (lambda (el1 el2)
(less? (car el1) (car el2)))))
{ ... bla bla bla ... other stuff was in here aswell...
too lazy to copy and paste it here again ... }
But i still get the same error Code:
> (define my-pq (create-priority-q <)) (priority-q:insert! my-pq 3 'a) . reference to undefined identifier: make-binary-heap > Okay, maybe i am not asking the question right. On other words... if i were to create a priority queue that will enable insertion and deletion of elements... what would be the editor code and the listerner code? I want to test it using numbers.
|
Del.icio.us
Digg
Google
Spurl
Blink
Furl
Simpy
Y! MyWeb
