如何从方案中的两个列表中取对交叉? [英] How to take intersection of pairs from two lists in scheme?

问题描述

我正在使用The little schemer中的脚本，以获取两组的交集.但是我在成员"处收到未绑定的标识符错误，有人可以告诉我这是怎么回事:

I am using this script from The little schemer, to get intersection of two sets. But I am getting unbound identifier error at 'member?', can anyone please tell what's wrong with it:

(define intersect
  (lambda (set1 set2)
    (cond ((null? set1) (quote ()))
          ((member? (car set1) set2)
           (cons (car setl)
                 (intersect (cdr set1) set2)))
          (else (intersect (cdr setl) set2)))))

我在上面缺少此功能:

(define member?
  (lambda (a lat)
    (cond ((null? lat) #f)
          (else (or (eq? (car lat) a)
                    (member? a (cdr lat)))))))

此外，我想与两个列表相交:'(((1 2)(2 7))'((1 3)(4 5))='((1 5))，有关如何操作的任何建议关于它?我正在寻找这篇文章的答案:

Also, I want to intersect two lists like: '((1 2)(2 7)) '((1 3)(4 5)) = '((1 5)), any suggestions on how to go about it? I am looking up the answers from this post: How to write a scheme function that takes two lists and returns four lists

推荐答案

您在intersect中有一个错字，其中您将小写L切换为1.正在比较符号.例如

You have a typo in intersect where you have switched 1 with as lower case L. If you fix that your intersect seems fine by me if you are comparing symbols. Eg.

(define intersect
  (lambda (set1 set2)
    (cond
      ((null? set1)(quote ()))
      ((member? (car set1) set2)
       (cons (car set1)
             (intersect (cdr set1) set2)))
      (else (intersect (cdr set1) set2)))))

(intersect '(a b c d) '(c d e f)) ; ==> (c d) 

要比较符号以外的其他内容，您需要更改member?，以便它使用equal?而不是eq?.会是这样的:

To make it compare other things than symbols, you need to change your member? so that it uses equal? instead of eq?. It will be like this:

(define member?
  (lambda (a lat)
    (cond
      ((null? lat) #f)
      (else (or (equal? (car lat) a) ; changed eq? to equal? 
                (member? a (cdr lat)))))))

(intersect '((1 2)(3 4)(5 6)) '((9 10) (7 8) (5 6))) ; ==> ((5 6))

甚至在此之后.上面的符号版本仍然有效. 在任何LISP中(至少是Common Lisp和Scheme)，您都有member.它使用equal并在未找到时计算为false(在实现中为假)，如果找到，则从找到元素的位置开始计算到参数列表的其余部分(认为正确):

Even after this. The symbol version above still works. In any LISP (Common Lisp and Scheme at least) you have member. It uses equal and evaluate to false (whatever is false in the implementation) when it's not found and if it's found it evaluates to the rest of the argument list starting from where the element was found (which is considered true):

(member 'a '(x y a c)) ; ==> (a c)

使用标准成员而不是您自己的谓词:

Using standard member instead of your own predicate:

(define intersect
  (lambda (set1 set2)
    (cond
      ((null? set1)(quote ()))
      ((member (car set1) set2)
       (cons (car set1)
             (intersect (cdr set1) set2)))
      (else (intersect (cdr set1) set2)))))

(intersect '((1 2)(3 4)(5 6)) '((9 10) (7 8) (5 6))) ; ==> ((5 6))
(intersect '(a b c d) '(c d e f)) ; ==> (c d) 

编辑1

似乎您不是要搜索intersection，而是要进行特殊的alist合并:

It seems you are not searching for intersection but a special alist merge:

#!r6rs
(import (rnrs base)
        (rnrs lists))

;; if you dont have r6rs remove the above and
;; uncomment this rnrs/lists-6 memp
#;(define (memp predicate? lst)
  (cond ((null? lst) #f)
        ((predicate? lst) lst)
        (else (memp predicate? (cdr lst)))))


(define (alist-merge merge-proc alist-1 alist-2)
  (if (null? alist-1) 
      '()
      (let* ((name (caar alist-1))
             (found (memp (lambda (x) (equal? (car x) name)) alist-2)))
        (if found
            (cons (merge-proc (car alist-1) (car found))
                  (alist-merge merge-proc
                               (cdr alist-1)
                               alist-2))
            (alist-merge merge-proc
                         (cdr alist-1)
                         alist-2)))))

(define (alist-merge-add alist-1 alist-2)
  (alist-merge (lambda (x y)
                 (list (car x)
                       (+ (cadr x) (cadr y))))
               alist-1
               alist-2))

(alist-merge-add '((1 2)(2 7)) '((1 3)(4 5))) ; ==> ((1 5))

这篇关于如何从方案中的两个列表中取对交叉?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！