如何从方案中的两个列表中获取对的交集? [英] 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)))))

我在上面错过了这个功能:

I was missing this function above:

(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 中有错字，您将 1 切换为小写 L.如果您修复了 intersect如果您正在比较符号，我觉得 很好.例如.

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 (无论在实现中是否为 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屋！