List Struture Equality

Discussion of Scheme and Racket

List Struture Equality

Postby dsjoka » Wed Mar 02, 2011 4:50 pm

Hi,

Ok I need some help with thinking through this conceputally. I need to check if a list and another list is structurally equal.

For example:

(a (bc) de)) is the same as (f (gh) ij)), because they have the same structure.

Now cleary the base case will be if both list are empty they are structurally equal.

The recursive case on the other hand I'm not sure where to start.

Some ideas:

Well we are not going to care if the elements are == to each other because that doesn't matter. We just care in the structure. I do know we will car down the list and recursively call the function with the cdr of the list.

The part that confuses me is how do you determine wheter an atom or sublist has the same structure?

Any help will be appreciated.
dsjoka
 
Posts: 14
Joined: Thu Feb 10, 2011 1:30 pm

Re: List Struture Equality

Postby gugamilare » Wed Mar 02, 2011 6:34 pm

Well, If I got the idea, any two atoms have the same structure. Therefore, the base case of your function should test also if both arguments are atoms and, if the test succeeds, return T.

To see if sublists match each other, you just need to call the function recursively on them. In other words, if the function finds cons cells, the function must be called recursively on their CARs and CDRs.

Let me know if this is not clear enough for you.
gugamilare
 
Posts: 406
Joined: Sat Mar 07, 2009 6:17 pm
Location: Brazil

Re: List Struture Equality

Postby dsjoka » Wed Mar 02, 2011 6:39 pm

Sorry I couldn't understand the last part

You mean Cons((function(car list)) (function(cdr list))

or something like that?
dsjoka
 
Posts: 14
Joined: Thu Feb 10, 2011 1:30 pm

Re: List Struture Equality

Postby gugamilare » Thu Mar 03, 2011 8:56 am

What I meant is this:

Code: Select all
(defun structurally-equal-p (a b)
  ;; <- place base cases here
  (if (and (consp a) (consp b))
    (and (structurally-equal-p (car a) (car b))
            (structurally-equal-p (cdr a) (cdr b)))))


In other words, if the arguments a and b are both cons cells, the function structurally-equal-p tests if (car a) and (car b) have the same structure using recursion. Then, it tests if (cdr a) and (cdr b) also have the same structure. If that is true, then a and b have the same structure and the function returns T.
gugamilare
 
Posts: 406
Joined: Sat Mar 07, 2009 6:17 pm
Location: Brazil

Re: List Struture Equality

Postby dsjoka » Thu Mar 03, 2011 12:21 pm

Whats is the difference between cons and consp?
dsjoka
 
Posts: 14
Joined: Thu Feb 10, 2011 1:30 pm

Re: List Struture Equality

Postby dsjoka » Thu Mar 03, 2011 1:11 pm

Forget it, I found what it was.

Does consp work with Dr Racket? I'm not home, so I can't try.
dsjoka
 
Posts: 14
Joined: Thu Feb 10, 2011 1:30 pm

Re: List Struture Equality

Postby gugamilare » Thu Mar 03, 2011 7:20 pm

Oos, sorry, now I've realized you are talking about Scheme :oops:

Anyway, Scheme should also have the function consp, so I guess that is a yes, but, instead of
Code: Select all
(defun structurally-equal-p (a b)
  ...)

you should use
Code: Select all
(define (structurally-equal-p a b)
  ...)
gugamilare
 
Posts: 406
Joined: Sat Mar 07, 2009 6:17 pm
Location: Brazil

Re: List Struture Equality

Postby Kompottkin » Fri Mar 04, 2011 6:22 am

gugamilare wrote:Anyway, Scheme should also have the function consp, so I guess that is a yes


Scheme calls it pair?. Other than that, it should work the same way.
User avatar
Kompottkin
 
Posts: 94
Joined: Mon Jul 21, 2008 7:26 am
Location: München, Germany

Re: List Struture Equality

Postby pepsi7up » Mon Mar 19, 2012 6:28 pm

Code: Select all
(defun list-structure-eq (l1 l2)
  (cond ((and (null l1) (null l2)) t)
   ((or (null l1) (null l2)) nil)
   ((and (listp (car l1)) (listp (car l2)))
    (and (list-structure-eq (car l1) (car l2)) (list-structure-eq (cdr l1) (cdr l2))))
   ((and (atom (car l1)) (atom (car l2)))
    (and (and (atom (car l1)) (atom (car l2))) (list-structure-eq (cdr l1) (cdr l2))))
   (t nil)))

(list-structure-eq '(a (b c) d) '(1 (2 3) 4))
t
(list-structure-eq '(a (b) d) '(1 (2 3) 4))
nil


common-lisp might already have a list atom equals..:arrow:
Code: Select all
(defun list-eq (l1 l2)
  (cond ((and (null l1) (null l2)) t)
   ((or (null l1) (null l2)) nil)
   ((and (listp (car l1)) (listp (car l2)))
    (and (list-eq (car l1) (car l2)) (list-eq (cdr l1) (cdr l2))))
   ((and (atom (car l1)) (atom (car l2)))
    (and (eq (car l1) (car l2)) (list-eq (cdr l1) (cdr l2))))
   (t nil)))



(list-eq '(a b c) '())
nil

nil

t
 
pepsi7up
 
Posts: 2
Joined: Mon Mar 19, 2012 6:16 pm

Re: List Struture Equality

Postby pepsi7up » Thu Mar 22, 2012 4:55 am

ok whoops this is the Scheme channel. This might work if you replace the t form with an else one :o
pepsi7up wrote:
Code: Select all
(defun list-structure-eq (l1 l2)
  (cond ((and (null l1) (null l2)) t)
   ((or (null l1) (null l2)) nil)
   ((and (listp (car l1)) (listp (car l2)))
    (and (list-structure-eq (car l1) (car l2)) (list-structure-eq (cdr l1) (cdr l2))))
   ((and (atom (car l1)) (atom (car l2)))
    (and (and (atom (car l1)) (atom (car l2))) (list-structure-eq (cdr l1) (cdr l2))))
   (t nil)))

(list-structure-eq '(a (b c) d) '(1 (2 3) 4))
t
(list-structure-eq '(a (b) d) '(1 (2 3) 4))
nil


common-lisp might already have a list atom equals..:arrow:
Code: Select all
(defun list-eq (l1 l2)
  (cond ((and (null l1) (null l2)) t)
   ((or (null l1) (null l2)) nil)
   ((and (listp (car l1)) (listp (car l2)))
    (and (list-eq (car l1) (car l2)) (list-eq (cdr l1) (cdr l2))))
   ((and (atom (car l1)) (atom (car l2)))
    (and (eq (car l1) (car l2)) (list-eq (cdr l1) (cdr l2))))
   (t nil)))



(list-eq '(a b c) '())
nil

nil

t
 
pepsi7up
 
Posts: 2
Joined: Mon Mar 19, 2012 6:16 pm

Next

Return to Scheme

Who is online

Users browsing this forum: No registered users and 3 guests