Home > Archive > Scheme > April 2006 > having trouble with list comparing
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
having trouble with list comparing
|
|
| isaac2004 2006-04-16, 7:06 pm |
| hi im tryingto write a function that takes as arguments two lists and
then puts a boolean statement on them to check if they are the same
list.
(define bag-equal
(lambda (S1 S2)
(cond
((= (S1) (S2)) #t)
(else #f ) ) ) )
it throws an error wnat am i doing wrong here
| |
| Ray Dillinger 2006-04-16, 7:06 pm |
| isaac2004 wrote:
> hi im tryingto write a function that takes as arguments two lists and
> then puts a boolean statement on them to check if they are the same
> list.
>
>
> (define bag-equal
> (lambda (S1 S2)
> (cond
> ((= (S1) (S2)) #t)
> (else #f ) ) ) )
> it throws an error wnat am i doing wrong here
You're using a numeric equivalence predicate = to
check the equivalence of cons cells. If you want
to check whether the list heads are literally the
SAME cons cell, use eq? instead. If you want to
see whether the two list heads' cars and cdrs
point at the SAME two objects, use eqv?
Unfortunately, there is no native equivalence predicate
which tests for the kind of equivalence you're likely
to want in list comparisons; whether the lists have
the same elements in the same order.
Also unfortunately, your predicate name 'bag-equal'
implies that you intended a different comparison
entirely. If you're implementing bag operations
using list representation you want a comparison
function in which the sequence of elements in a
list doesn't matter.
Bear
| |
| isaac2004 2006-04-16, 7:06 pm |
| The purpose of the function was to take as arguments two lists
representing bags and
should return #t if they represent the same bag and false otherwise.
isnt this what the function states, if not would i use just a simple if
statement using the eqv? object ti test the case
| |
| Pascal Bourguignon 2006-04-16, 7:06 pm |
| "isaac2004" <isaac_2004@yahoo.com> writes:
> The purpose of the function was to take as arguments two lists
> representing bags and
> should return #t if they represent the same bag and false otherwise.
> isnt this what the function states, if not would i use just a simple if
> statement using the eqv? object ti test the case
No. What this:
(define bag-equal
(lambda (S1 S2)
(cond
((= (S1) (S2)) #t)
(else #f))))
states is:
define bag-equal as a function taking two arguments, S1 and S2, which
must be procedures of zero argument returning numbers. If the numbers
returned by these two procedures are equal, then return #t, else
return #f. It could be written as:
(define bag-equal (lambda (S1 S2) (= (S1) (S2))))
because = already returns either #t or #f.
It should be called for example as:
(bag-equal (lambda () 1) (lambda () 2))
or as:
(bag-equal (lambda () (+ 1 1)) (lambda () 2))
Not quite what you seem to want.
--
__Pascal Bourguignon__ http://www.informatimago.com/
"You cannot really appreciate Dilbert unless you read it in the
original Klingon"
| |
| isaac2004 2006-04-16, 7:06 pm |
| >It should be called for example as:
(bag-equal (lambda () 1) (lambda () 2))
or as:
(bag-equal (lambda () (+ 1 1)) (lambda () 2))
Not quite what you seem to want.
then how should i declare my variables then if i want them to be
referenced as bags
| |
| Ray Dillinger 2006-04-16, 10:04 pm |
| isaac2004 wrote:
>
> (bag-equal (lambda () 1) (lambda () 2))
> or as:
> (bag-equal (lambda () (+ 1 1)) (lambda () 2))
>
>
> Not quite what you seem to want.
>
> then how should i declare my variables then if i want them to be
> referenced as bags
>
First you have to decide how you want bags to be represented
in scheme. You have a bunch of choices. If all the values in
the bag are numbers, a sorted list is a good choice. If the
bags are general though, you can't do it, because as far as
I know there's no way to sort, eg, closures or procedures
relative to each other.
You don't "declare" variables, as such, in a vanilla scheme
anyway; The system decides what type something is by what
you're trying to do with it. Your code called these two
variables with no arguments (hence the values had to be
functions of no arguments) and called a numeric-equality
predicate on the results (hence the functions had to return
numbers).
| |
| Pascal Bourguignon 2006-04-16, 10:04 pm |
| "isaac2004" <isaac_2004@yahoo.com> writes:
> (bag-equal (lambda () 1) (lambda () 2))
> or as:
> (bag-equal (lambda () (+ 1 1)) (lambda () 2))
>
>
> Not quite what you seem to want.
>
> then how should i declare my variables then if i want them to be
> referenced as bags
The problem is not in declaring variables. It's in the syntax you use:
> No. What this:
>
> (define bag-equal
> (lambda (S1 S2)
> (cond
> ((= (S1) (S2)) #t)
> (else #f))))
>
> states is:
>
> define bag-equal as a function taking two arguments, S1 and S2, which
> must be procedures of zero argument returning numbers. If the numbers
> returned by these two procedures are equal, then return #t, else
> return #f. It could be written as:
(S1) means call the procedure which is the value of S1, with 0 argument.
S1 means the value of the variable S1.
--
__Pascal Bourguignon__ http://www.informatimago.com/
"You question the worthiness of my code? I should kill you where you
stand!"
| |
|
|
isaac2004 wrote:
> The purpose of the function was to take as arguments two lists
> representing bags and
> should return #t if they represent the same bag and false otherwise.
> isnt this what the function states, if not would i use just a simple if
> statement using the eqv? object ti test the case
Well, it sounds like order doesn't matter. If I'm understanding right,
the desired outcome is that '(black red blue) and '(blue red black)
should both return true
There are several ways to do that. One way would be to sort both lists
(aka "bags"), and then compare them using equal? You could also write a
more direct recursive procedure utilizing the built-in member? and a
self-written remove-an-instance-of procedure.
I can't really do your homework for you, but if there is a specific
question you have about why the code you wrote doesn't do what you
expect, feel free to ask more.
| |
| azubijan 2006-04-17, 7:05 pm |
| ;; short version, if your bags are represented by lists
(define (list-equal s1 s2)
(equal? s1 s2))
| |
| Pascal Bourguignon 2006-04-17, 7:05 pm |
| "H." <hbe123@gmail.com> writes:
> isaac2004 wrote:
>
> Well, it sounds like order doesn't matter. If I'm understanding right,
> the desired outcome is that '(black red blue) and '(blue red black)
> should both return true
Why are you assuming the bag is represented like this?
It could be: ((black red blue))
or: ((1 black red blue))
or: ((black 1) (red 1) (blue 1))
or about anything.
What does it mean that two lists represent the same bag?
How does a list represent a bag?
A bag is a mathematical object http://en.wikipedia.org/wiki/Multiset
while list is a concrete type in scheme:
- () is a list.
- (cons object list) is a list.
- nothing else is a list.
Note how the definition of a bag implies some equality operator. If I
want to put these two objects: (cons 1 2) and (cons 1 2) into the same
bag, are they the same? Do I have twice (cons 1 2), or do I have two
different pairs that happen to have the same elements? Depends on
whether you use eqv? or equal? on them.
So you need to specify exactly what you understand by a "bag".
Then, you need to specify how you represent such a bag with lists.
For example, the bag {1, 1, 2, 3, 3, 4, 4, 4, 4} can be represented as:
((1 2) (2 1) (3 2) (4 4)) ; (item multiplicity)
or as: (1 1 2 3 3 4 4 4 4) ; multiples are close
or as: (1 4 2 4 3 4 1 4 3) ; order doesn't matter
or as: ((1 2) (2 1 3) (4 4)) ; (multiplicity . items)
or as: ((2) (1 3) () (4)) ; (nth i b) = list of items of multiplicity (+ i 1)
etc...
> There are several ways to do that. One way would be to sort both lists
> (aka "bags"), and then compare them using equal? You could also write a
> more direct recursive procedure utilizing the built-in member? and a
> self-written remove-an-instance-of procedure.
>
> I can't really do your homework for you, but if there is a specific
> question you have about why the code you wrote doesn't do what you
> expect, feel free to ask more.
Of course we cannot do a lot at this stage, because the specifications
are incomplete. However, we can still implement bag-equal? using
abstractions:
(make-empty-bag equal?) ; returns an empty bag using equal? as equality
; predicate for its elements.
(bag-equality-predicate bag) ; returns the equality predicate for the elements
; of the bag
(bag? object) ; returns #t <=> object is bag
(bag-empty? object) ; returns #t <=> object is an empty bag.
(bag-add-element element bag) ; returns a new bag that contains
; all the elements of bag, plus one element.
(bag-remove-element element bag) ; returns a new bag that contains
; all the elements of bag, minus one element.
(bag-multiplicity element bag) ; returns the number of times element is
; contained in bag (0 if element is not i bag).
(bag-enumerator bag) ; returns a procedure that returns successively lists
; (element multiplicity) for all elements in the bag,
; then ().
Then you can write:
;; Note, all code below untested.
(define (bag-subset? b1 b2)
(let ((next (bag-enumerator b1)))
(let loop ((current (next)))
(if (null? current)
#t
(if (<= (cadr current) (bag-multiplicity (car current) b2))
(loop (next))
#f)))))
(define (bag-equal? b1 b2)
(and (eqv? (bag-equality-predicate b1) (bag-equality-predicate b2))
(bag-subset? b1 b2)
(bag-subset? b2 b1)))
If bag-multiplicity is O(n), then this bag-equal? will be O(nē), which is bad.
If you have a hash-table, you could implement a bag-equal? which is O(n):
(make-hash-table equal?) ; returns a hash table which use equal? as equality
; predicate.
(hash-set! hash key value) ; add or change the value at key in the hash table.
(hash-get hash key) ; returns either a list containing as single element
; the value at key in the hash table, or () if there's
; no element at key in the hash table.
(hash-remove! hash key) ; remove the entry at key in the hash table.
(hash-count hash) ; remove the number of keys in the hash table.
then you can write:
(define (bag-equal? b1 b2)
(and (eqv? (bag-equality-predicate b1) (bag-equality-predicate b2))
(let ((h (make-hash-table (bag-equality-predicate b1)))
(n1 (bag-enumerator b1))
(n2 (bag-enumerator b2)))
(let loop ((current (n1)))
(if (not (null? current))
(begin (hash-set! h (car current) (cdr current))
(loop (n1)))))
(let loop ((current (n2)))
(if (null? current)
(= 0 (hash-count h))
(let ((old (hash-get h (car current))))
(if (and (not (null? old))
(= (cdr old) (cdr current)))
(begin (hash-remove! h (car current))
(loop (n2)))
#f)))))))
which builds a hash table mapping the elements in the bag b1 to their
multiplicity [O(e1)], then check that all the element in bag b2 have
the same multiplicity [O(e2)], removing the entries in the table, and
finally returning #t when none remain. Total: O(n) with n=e1+e2, the
sum of the number of distinct elements in b1 and b2.
--
__Pascal Bourguignon__ http://www.informatimago.com/
"Logiciels libres : nourris au code source sans farine animale."
| |
| isaac2004 2006-04-17, 7:05 pm |
| wouldnt just adding a function like shown earlier just lengthen the
process and further more not reach the conclusion, you cannot use
equal? because it is a bag that sahows no order so how would i complete
this task, is a helper function like sort or something like it, im just
 on the algorithm of it
| |
| earthnut@web.de 2006-04-17, 7:05 pm |
| Perhaps you mean something like:
(define (remove-from-bag bag element)
(cond ((null? bag)
'this-is-a-dummy-element-added-at-the-end-of-bag-for-penalty-that-the-element-is-not-in)
((equal? element (car bag)) (cdr bag))
(else (cons (car bag) (remove-from-bag (cdr bag) element)))))
(define (bag-equal? S1 S2)
(cond ((and (null? S1) (null? S2)) #t)
((null? S2) #f)
(else (bag-equal? (remove-from-bag S1 (car S2)) (cdr S2)))))
| |
|
|
isaac2004 wrote:
> wouldnt just adding a function like shown earlier just lengthen the
> process and further more not reach the conclusion, you cannot use
> equal? because it is a bag that sahows no order so how would i complete
> this task, is a helper function like sort or something like it, im just
> on the algorithm of it
What I got from Pascal's message is that you had not specified the way
that bags are being represented, which is the logical first step in
writing code to manipulate them.
I was answering the question under the assumption that a bag is
represented by a list, with each each item in the bag being represented
by an atom, but I was pre-supposing. In order to get the most useful
help, you should try to be as detailed as possible about how you are
choosing to represent a bag.
|
|
|
|
|