Scheme 테스트 목록에있는 항목 또는 목록 비교 (중첩 가능)

Question

내 목표는 목록 또는 항목이 중첩 목록 안에 있으면 함수 part?을 true로 설정하는 것입니다.

그러나 지금까지는 신호 항목을 첫 번째 순서 목록에서만 사용할 수있었습니다.

(define part? 
    (lambda (item l) 
    (and (not (null? l)) 
     (or (= item (car l)) 
      (part? item (cdr l)))))) 

내 목표는

부분을하는 것입니다 (아직 목록을 중첩되지 않음)? (A (B)), ((B) A (B)) C)가 #f이고

부분? (A B), (C (A B) (C))는 #t

어디에서 개선해야합니까? 중첩 목록과 비교할 목록을 만들려면 어떻게해야합니까?

Answer 1

면책 조항 : 저는 20 년 후에 정기적으로 계획서를 작성하지 않았습니다.

나는 당신이이 문제에 대해 당신의 조건을 수립하는 전체/회피 방식에 관해 생각하고 싶다고 생각한다.

입력 항목이 주어지면 목록에 해당 항목이 있는지 찾아야합니다.

1. 목록에 null이 없으면 목록에 항목이 포함될 수 있습니다. 목록의 차가 항목을 일치하거나 목록의 차가 항목을

2. 이 포함 된 경우 목록의 CDR이 항목이 포함 된 경우 목록 항목을 포함하는 경우

3. 목록이 항목이 포함되어 있습니다.

4. 마지막으로 고려해야 할 질문은 (part? '(a b)'(a b))의 결과는 무엇입니까?

나는 그것이 이런 종류의 문제와 잘 맞는 때문에이 COND 구조를 사용이

(define part? (lambda (item l) 
    (cond ((null? l) f) 
      ((or (same? item (car l)) (part? item (car l)))) 
      (t (part? item (cdr l))) 
    ) 
)) 

(define same? (lambda (a b) (eq? a b))) 

같은 코드를 작성합니다는 - 그것은 단지 문제를 탈옥 오른쪽 느낌 - 널 체크를 알 . 내가 쓴거야? 당신이 직접 작성하고 싶을 경우 도우미 함수로서.당신은 할 수 그냥 쉽게이 방법 : 기본적으로 그들은 모두 원자는 그들이 EQ 또는 그들이 모두 나열하고 자동차가 동일하고, CDR은이 경우 두 항목이 동일한 것을 말한다

(define same? (lambda (a b) 
    (cond ((and (atom? a) (atom? b)) (eq? a b)) 
      ((and (list? a) (list? b)) (and (same? (car a) (car b)) (same? (cdr a) (cdr b)))) 
      (f f) 
    ) 
)) 

동일하거나 그렇지 않으면 거짓.

마찬가지로 쉽게 다시 작성할 수 있습니까? 다음과 같이하십시오 :

(define same? (lambda (a b) (equal? a b))) 

코드의 병목 현상은 두 항목이 동일한 지 확인하는 방법입니다. 병목 지점을 자체 기능으로 분해하면 다른 메커니즘으로 대체 할 수 있습니다. 당신이 아직 여기 있지 않다는 것을 알지만, 당신은 한순간에있을 것입니다 : 당신은 또한 술어가 전달되도록 코드를 다시 작성할 수 있습니다. 이것과 같은 것 (그리고 더 최신 스키마 프로그래머는 자유롭게) 저를 해결하려면 다음이 이제 일부 구조 규칙과 당신에 의해 공급되는 동등 술어를 적용하는 기능으로 부분의 개념을 추상화 한

(define part-pred? (lambda (same-pred item l) 
    (cond ((null? l) f) 
      ((or (same-pred item (car l)) (part? item (car l)))) 
      (t (part? item (cdr l))) 
    ) 
)) 

(define part-eq? (lambda (item l) (part-pred? 'eq? item l))) 
(define part-same? (lambda (item l) (part-pred? 'same? item l))) 
(define part-equal? (lambda (item l) (part-equal? 'equal? item l))) 

. 따라서 규칙을 쉽게 변경할 수 있습니다. 이것은 당신이 mapcar를 칠 때 더 합리적이 될 것입니다.

Answer 2

여기에 사용 된 = 함수의 문제점은 숫자에만 정의 된 것입니다. 임의의 데이터를 동등하게 테스트하려면 술어 eq?, eqv? 및 equal?이 있습니다. 여기서는 가장 차별화 된 것 (eq?, 기본적으로 포인터 비교와 같은 것)부터 가장 구별하지 않는 것 (equal?은 유형 및 구조를 고려합니다)에 나열되어 있습니다. eqv? 술어는 그 중간에 있습니다 (숫자에 대해서는 유형 인식, 그렇지 않은 경우에는 eq?).

목록을 비교하려면 일반적으로 equal?을 사용합니다.

이 술어에 대한 세부 사항은 R6RS에서 찾을 수 있습니다.

Answer 3

중첩 된 목록을 처리하고 있으므로 각 목록의 각 항목이 목록 자체인지 확인해야하므로 솔루션에서 아이디어가 누락됩니다. 주어진 목록이 다른 목록 또는 부분의 일부인지 확인하는 경우 목록의 나머지 부분 중 첫 번째 항목이 동등하고 나머지 목록이 다른 항목의 일부인지 확인해야합니다.

(define part? item l 
    (cond (and (list? (car item)) (not (list? (car l))) ...) 
     (and (not (list? (car item))) (list? (car l)) ...) 
     (and (not (list? (car item))) (not (list? (car l))) ...) 
     (and (list? (car item)) (list? (car l))) ...)