3

私は R5RS 標準のスキーム実装を使用しています。

ここで、要素 '(2 3 4) がリスト '(1 2 3 4) にあるかどうかを調べる必要があると想像してください。

例として、より厳密には、次のことを望みます。

1. (is-in? '(2 3 4) '(1 2 3 4)) -> #f
2. (is-in? '(2 3 4) '(1 (2 3 4)) -> #t

質問: 例 1 のように、そのような動作を取得するにはどうすればよいですか?

説明させてください。リスト全体を検索する場合、carまたはcdrを使用してその部分を取得できます。リストを再帰的に調べると、最終的には次のようになります。

3. (cdr '(1 2 3 4)) -> '(2 3 4)
4. (cdr '(1 (2 3 4)) -> '((2 3 4))

最終的に、2 つのリストを取得しました。ここでわかるように、サブリスト '(2 3 4) は3 と 4の両方の結果に含まれています。

3 と 4 と 1 と 2の矛盾を見てください。 2 3 4) - そして等号を使用しますか? 関数、再帰呼び出しのどこかで、最終的に 1 と 2 の両方で #t を取得します。

5. (is-in? '(2 3 4) '(1 2 3 4)) -> #t
6. (is-in? '(2 3 4) '(1 (2 3 4)) -> #t

では、そのような振る舞いを 1 から取得するにはどうすればよいでしょうか。すべての異なるタイプのデータで機能する関数が必要です。5 と 6 のように機能する関数を次に示します (throught は 1 と 2 として機能するはずです)。

(define or (lambda (x y)
             (cond ((eq? x y) (eq? x #t))
                   (#t #t)
                   )
             )
  )

(define and (lambda (x y)
              (cond ((eq? x y) (eq? x #t))
                    (#t #f)
                    )
              )
  )

(define atom? (lambda (x)
                (not (pair? x))
                )
  )

(define length (lambda (x)
                       (cond ((eq? x '()) 0)
                             ((atom? x) 1)
                             (#t (+ (length (car x)) (length (cdr x))))
                             )
                       )
  )

(define equal? (lambda (x y)
                 (cond ((and (atom? x) (atom? y)) (eq? x y))
                       ((not (eq? (length x) (length y))) #f)
                       ((not (and (pair? x) (pair? y))) #f)
                       (#t (and (equal? (car x) (car y)) (equal? (cdr x) (cdr y))))
                       )
                 )
  )

(define is-in? (lambda (x y)
                 (cond ((equal? x y) #t)
                       (#t (cond ((pair? y) (or (is-in? x (car y)) (cond ((eq? (length y) 1) #f)
                                                                          (#t (is-in? x (cdr y)))
                                                                          )))
                                 (#t #f)
                                 )
                           )
                       )
                 )
  )

更新：

私が欲しいのは、あるオブジェクトが別のオブジェクト内にあるかどうかを伝えることができる一般的な関数を持つことです。私はエンティティオブジェクトに名前を付けて、この関数がどんな入力値でも動作することを強調しています。

使用例:

1. (is-in? 1 '(1 2 3)) ;-> #t
2. (is-in? '(1) '(1 2 3)) ;-> #f
3. (is-in? '(2 . 3) '(1 2 . 3)) ;-> #f
4. (is-in? '(2 . 3) '(1 (2 . 3))) ;-> #t
5. (is-in? '2 '(1 2 . 3)) ;-> #t
6. (is-in? '(2) '(1 2 . 3)) ;-> #f
7. (is-in? '(1 2 (3 4 (5 6 . (7 . 8)) 9) 10 11 (12 . 13)) '(1 (2 3 ((4 ((6 (3 . ((1 2 (3 4 (5 6 . (7 . 8)) 9) 10 11 (12 . 13)))) 3) 4)) 5) 2))) ;-> #t
8. (is-in? '(2 3 4) '((1 (2 3 4)) (1 2 3 4))) ;-> #t
9. (is-in? '(2 3 4) '(1 2 3 4)) ;-> #f
10. (is-in? '(2 3 4) '(1 (2 3 4))) ;-> #t
11. (is-in? '(1) '(1)) ;-> #t
4

2 に答える 2

2 
(define (is-in? e lst)
   (cond ((null? lst) #f) ; if list is empty, we failed
         ((eq? e (car lst)) #t) ; check 1st element of list
         ((list? (car lst)) (is-in? e (append (car lst) (cdr lst)))) ; search inside car if it is a list
         (#t (is-in? e (cdr lst))))) ; check rest of list

You can replace eq? with something more elaborate to handle other definitions of equality.

Note: this assumes that all sequences are lists; you'll have to tweak it to handle dotted-pairs that are not lists.

于 2012-10-20T16:33:05.073 に答える
2

まず第一に、なぜand, or, equal?andを再定義するのlengthですか? これらは組み込みのプリミティブです。また、あなたの定義atom?は間違っています。次のようにする必要があります。

(define (atom? x)
  (and (not (pair? x))
       (not (null? x))))

宿題の一環として、これを最初から実装する必要があると思います。それがどのように達成できるかを見てみましょう。空欄を埋めて答えを出してください。

(define (is-in? ele lst)
  (or <???>                          ; trivial case: ele == list
      (member? ele lst)))            ; call helper procedure

(define (member? ele lst)
  (cond ((null? lst)                 ; if the list is empty
         <???>)                      ; then the element is not in the list
        ((atom? lst)                 ; if the list is not well-formed
         (equal? <???> <???>))       ; then test if ele == list
        (else                        ; otherwise
         (or (equal?  ele <???>)     ; test if ele == the 1st element in the list
             (member? ele <???>)     ; advance the recursion over the `car`
             (member? ele <???>))))) ; advance the recursion over the `cdr`

の 2 番目のケースmember?が必要であることに注意してください。これは、指定された例に不正な形式のリストがあるためです (null 以外の値で終わる)。上記のソリューションは、質問で提供されているすべての例を正しく処理します。

于 2012-10-20T16:46:57.453 に答える