3

私は誰かが私を正しい方向に導いてくれることを望んでいました：私は2つのリストのアイテムのすべての可能な組み合わせを生成することを探しています：
例：
リスト'（symbol1 symbol2）と'（1 2）が与えられた場合、私は生成しようとしています
:( list（list'symbol1 1）（list' symbol1 2）（list'symbol2 1）（list symbol2 2））

これまでの私のコードは次のとおりです。

    (define (combiner list1 list2)
    (list
      (foldr (lambda (a b) (foldr (lambda (c d) (list a c)) empty list1)) empty list2)
      (foldr (lambda (a b) (foldr (lambda (c d) (list b d)) empty list1)) empty list2)))

これは明らかに機能しておらず、私が試した他のいくつかの方法でもありません。2つのリストで暗黙の再帰を処理するのに問題があります-何かアイデアはありますか？

4

3 に答える 3

4

ここで見ているのは、プログラムの設計方法のセクション17である2つの複雑な議論の再帰です。別のヒントが必要な場合は、これが3つのケースのどれであるかを説明します。

于 2011-11-19T01:14:30.017 に答える
2

私は問題を解決する別の可能な方法を考えました。ヒントは次のとおりです。

(define (combiner list1 list2)
  (define (combine l1 l2)
    (cond ((empty? l1) empty)
          ((empty? l2) XXX)
          (else (cons YYY
                      ZZZ))))
  (combine list1 list2))

上記のコードでは、次の3つの質問に対する答えを理解する必要があります。

  • XXX2番目のリストの反復を終了したが、最初のリストにはまだ要素があり、最初のリストの1つの要素を進めたい場合、どのように再帰を進めますか？
  • YYY最初のリストの要素と2番目のリストの要素をどのように組み合わせますか？
  • ZZZ両方のリストにまだ要素が残っている場合、どのように再帰を進めますが、この時点では、2番目のリストを進めることにのみ関心がありますか？

最後のヒント：ある時点で2番目のリストを「再起動」する必要があることに注意してください。そのためには、list2まったく変更されていない元のリストを参照できます。

これがお役に立てば幸いです。（まだ）正直な答えは出したくありません。自分で解決策を見つけてほしいのです。

于 2011-11-19T02:16:34.930 に答える
0

ここで混乱を招く可能性があるのは、の自由な使用ですlist。タイプにHaskell表記を使用して問題に取り組み始めます。::「タイプあり」を[Foo]意味し、「Fooのリスト」を意味します。

list1 :: [Symbol]
list2 :: [Number]
type Pair = (Symbol, Number)
(combiner list1 list2) :: [Pair]

foldrこれで、オーバーリスト2を使用してこの問題に取り組みたいようです。

foldr :: (a -> b -> b) -> b -> [a] -> b

foldrにはとが必要step :: a -> b -> bですstart :: b。最終結果を、にしたいので[Pair]、それはそれを意味しb = [Pair]ます。startその場合、おそらく空のリストになります。list2が[a]スロットを埋めるので、それはそれを意味しa = Numberます。したがって、私たちの問題については、step :: Number -> [Pair] -> [Pair]

combiner :: [Symbol] -> [Number] -> [Pair]
combiner list1 list2 = foldr step start list2
  where step :: Number -> [Pair] -> [Pair]
        step a b = undefined
        start = []

foldrこれまでのところ、これはあなたが書いたものと同じですが、私はstepまだ定義していません。では、階段関数とは何ですか？Numberタイプから、aとaを取り、[Pair]を生成する必要があることがわかり[Pair]ます。しかし、これらの入力はどういう意味ですか？さて、Number入力はのいくつかの要素になりlist2ます。そして、[Pair]入力は「これまでのフォールドの結果」になります。だから、私たちは私たちを取り、Numberそれのためにsを作成するために何かPairをして、それからこれまでの結果にそれらを叩きつけたいと思うでしょう。これは、私のコードがあなたのコードと異なり始めるポイントです。

step a b = append (doSomething a) b
doSomething :: Number -> [Pair]
doSomething a = undefined

あなたは、Racketを使用して、おそらくdoSomething無名関数として定義するので、それはlist1スコープ内にあることを意味します。（Haskellの関数のwhere句にあるので、スコープ内にあります）。おそらく、そのリストを使用して組み合わせを生成します。

doSomething a = ... a ... list1 ...

実装doSomethingは、Racketに戻すのと同様に、読者の演習として残されています。ここで定義しているHaskell関数の型アノテーションは、combinerに一般化できることに注意してください[a] -> [b] -> [(a,b)]。

于 2011-11-19T02:48:31.680 に答える