CODEWITHSUNDEEP
listschemeprocedure
user2409697
user2409697

Reputation: 13

Scheme, Check if anything in two lists are the same

Is it possible to check two list against each other if anything is the same in them?

(check-list '(hey cookie monkey) '(apple pizza cookie) ==> #t

I tried something like 

(define (check-list list element)
  (let ((x list))
  (cond ((null? x) #f)
        ((eq? (car x) (car element)) #t)
        (else (check-list (cdr x) element))))
  (check-list list (cdr element)))

I know this is not correctly written but don't know how to tackle this problem.

Anyone that can help me?

Upvotes: 1

Views: 4508

Answers (7)

ToothFairy101
ToothFairy101

Reputation: 1

(define remove-item
  (lambda (lst ele)
    (if (null? lst)
        '()
        (if (equal? (car lst) ele)
            (remove-item (cdr lst) ele)
            (cons (car lst)
                  (remove-item (cdr lst) ele))))))

Upvotes: 0

Sylwester
Sylwester

Reputation: 48745

If the lists are wicket long you might want to hash the first list and then just iterate through the second. This uses R5RS with srfi-69 and for small lists you'll get a little overhead but 

(require srfi/69); alist->hash-table, hash-table-ref/default 
(define (intersect? list1 list2)
  (let ((hash (alist->hash-table (map (lambda (x) (cons x x)) list2) equal? )))
    (let loop ((list list1))
      (and (not (null? list))
           (or (hash-table-ref/default hash (car list) #f)
               (loop (cdr list)))))))

Upvotes: 1

WorBlux
WorBlux

Reputation: 1413

Here's an answer using higher-order functions

in mit-schme

(define (check-list L1 L2)
 (apply boolean/or (map (lambda (x) (member? x L2)) L1)))

Upvotes: 0

Óscar López
Óscar López

Reputation: 236004

There seems to be a little confusion. The "big" problem here is how to determine if two lists share at least one element in common, let's write a procedure for that called element-in-common?. Before tackling this problem, we need to determine if a single element belongs in one list, that's what check-list should do (notice that in your code check-list receives as a second parameter an element, but you're treating it as if it were a list of elements).

You don't have to write the check-list procedure, it already exists and it's called member. With that knowledge in hand, we can solve the big problem - how to determine if at least one of the elements in one list (let's call it lst1) is in another list (called lst2)?

Simple: we iterate over each of the elements in lst1 using recursion, asking for each one if it belongs in lst2. If just one element of lst1 is a member of lst2, we return #t. If none of the elements in lst1 is in lst2, we return #f. Something like this:

(define (element-in-common? lst1 lst2)
  (cond (<???>               ; is the first list empty?
         <???>)              ; then there are no elements in common
        ((member <???> lst2) ; is the current element of `lst1` in `lst2`?
         <???>)              ; then there IS an element in common
        (else                ; otherwise
         (element-in-common? <???> lst2)))) ; advance recursion

Don't forget to test your code:

(element-in-common? '(hey cookie monkey) '(apple pizza cookie))
=> #t

(element-in-common? '(hey cookie monkey) '(apple pizza pie))
=> #f

Upvotes: 0

GoZoner
GoZoner

Reputation: 70155

Similar to a prior answer but exploiting logic primitives:

(define (intersect? list1 list2)
  (and (not (null? list1))
       (or (member     (car list1) list2)
           (intersect? (cdr list1) list2))))

Upvotes: 1

user1019830
user1019830

Reputation:

Sometimes it helps to formulate the process of the solution to a problem in your natural language. Let's simplify the problem a bit.

How do you check if one element is contained in a list? One way to do that would be to compare that one element with each element in the list until you found it - somewhere along the lines you have already done - but not quite. A quick draft would be:

(define (member? e lst)
  (cond ((null? lst) #f)       ; empty list doesn't contain e
        (or (eq? e <??>)       ; either the first element is e or
            (member? e <??>))) ; the rest of the list contains e

We can use that previous knowledge to solve the real problem at hand. We know how to search for one element in a list, and now we need to search for each element in a list in another list. 

(define (check-list lst1 lst2)
  (if (or (null? lst1) (null? lst2)) #f  ; empty list(s) share no elements
      (or (member? <??> <??>)            ; first element of lst1 in lst2?
          (member? <??> <??>))))         ; rest of lst1 in lst2?

The <??> should be substituded with the appropriate expressions for selecting the parts of the lists.

Upvotes: 1

piokuc
piokuc

Reputation: 26184

You can use memq to check if first element on the first list is on the second list, and if not then check recursively if something in the rest of the first list is in the second list:

(define (check-list list1 list2)
  (cond ((null? list1) #f)
        ((memq (car list1) list2) #t)
        (else (check-list (cdr list1) list2))))

Upvotes: 0

Related Questions