1

スキームで高階関数を使用する方法を学んでいます。高階関数を使おうと思ったのですが、うまく使いこなせません。この学習演習では、フィルター、折り畳み、および/またはマップの組み合わせのみを使用することをお勧めします。

たとえば、A と B を呼び出す 2 つのリスト間の集合の差を構築したいと考えています。x が A の要素であるが x が B の要素ではないような集合の差を x として定義しています。関数のみを使用したいマップ、フィルター、フォールド。例えば：

A = (1 8 6 2) とする

B = (5 7 9 1 6) とする

A と B のセット差は (8 2) になります。

アイデアは、A の要素を繰り返し処理し、A の要素が B の要素と等しいかどうかを確認することによって新しいリストを構築することです。等しい場合は、新しいリストに a を追加しないでください。それ以外の場合は、新しいリストに a を追加します。

私のアルゴリズムのアイデアは次のようになります。

neq を「等しくない」とする

  1. A の a と B の b ごとに、次の式を評価します。(neq? a b)

    a = 1 の場合:

    (および (neq? 1 5) (neq? 1 7) (neq? 1 9) (neq? 1 1) (neq ? 1 6))

  2. この式が true の場合、a は新しいリストに入ります。それ以外の場合は、新しいリストに a を追加しないでください。この例(neq? 1 1)では false と評価されるため、新しいリストに 1 を追加しません。

私の手順全体のほとんどは 1 に依存しており、ここで問題が発生します。

  1. ステップ 1 を行うにはどうすればよいですか?
  2. ステップ 1 でmapとfold関数の組み合わせが必要であることがわかりましたが、どうすればand a neq b分散型を取得できますか?

編集これは私が持っている最も近いサンプルです:

(fold-right (trace-lambda buggy (a b c) (and (neq? a b))) #t A B)
|(buggy 3 5 #t)
|#t
|(buggy 2 4 #t)
|#t
|(buggy 1 1 #t)
|#f
#f

上記は、(and (neq? ab)) チェーンを実行しようとしている匿名関数のトレースを示しています。ただし、これは A と B の同じ位置/インデックスの要素に対してのみ実行されます。

すべてのヘルプは大歓迎です!

4

4 に答える 4

3

Haskell では、fold遅延評価のため、短絡評価が可能です。

しかし、Scheme ではそれは不可能です。そのため、Racketormapには、そのために提供される特別な関数 があり、短絡評価が可能です。IOW は、foldScheme が怠惰ではないため、Scheme で明示的に個別に定義する必要がある特別な種類です。したがって、あなたの条件によれば、特別な種類のfold.

それを使用すると、

(define (diff xs ys) 
  (filter 
    (lambda (y) 
      (not (ormap (lambda (x) (equal? x y))     ; Racket's "ormap"
                  xs))) 
    ys))

要素を順序付けできる場合は、セットを順序付き (昇順) リストとして維持することをお勧めします。次にdiff、両方のリストのヘッド要素を比較し、それに応じて進めて、線形時間で作業することで、より効率的に実装できます。

于 2013-02-04T18:31:02.380 に答える
3

の単純化されたバージョンは、もちろん、 をmember使用して簡単に実装できます。fold

(define (member x lst)
  (fold (lambda (e r)
          (or r (equal? e x)))
        #f lst))

これで、残りは簡単です。

(define (difference a b)
  (filter (lambda (x)
            (not (member x b)))
          a))

neq?これらすべてを ( を使用して) 1 つの関数に統合したい場合は、次のようにします。

(define (difference a b)
  (filter (lambda (x)
            (fold (lambda (e r)
                    (and r (neq? e x)))
                  #t b))
          a))
于 2013-02-03T15:35:51.443 に答える
1

ラケットの使用:

(define A '(1 8 6 2))

(define B '(5 7 9 1 6))

(filter-not (lambda (x) (member x B)) A)

 ==> '(8 2)
于 2013-02-03T03:09:54.193 に答える