2 
test :: [String] -> [String]

test = foldr step []

  where step x ys

          | elem x ys = x : ys

          | otherwise = ys

入力されるすべての個別の文字列で構成される新しいリストを作成しようとしています。私のテストデータは次のとおりです。

test ["one", "one", "two", "two", "three"]

期待される結果：

["one", "two", "three"]

私は Haskell に不慣れで、非常に基本的で明白な何かが欠けていると確信していますが、これを調査する方法が不足しています。私の考えがどこに欠けているかを教えていただけますか？

実際の応答は[]です。最初のガード条件が満たされないようです (これを に置き換えるとTrue、元のリストが複製されます)。そのため、出力リストは作成されません。

私の理解では、折り畳みはリストの各項目のステップの結果を蓄積し、それを空のリストに追加するというものでした。このステップでは、各項目が出力リストに含まれているかどうかをテストし (テストされた最初の要素がそこにない)、まだ出力リストに含まれていないものをすべて追加すると予想しました。明らかにそうではありません:-)

4

2 に答える 2

7

考えてみてください: あなたのコードは、「x が剰余にある場合、x を結果の前に追加する」、つまり重複を作成していると言っています。「xが剰余にない場合、xを結果の先頭に追加する」に変更するだけで、正しい関数が得られます。

Data.List.nubこの関数は重要な点で異なります: この関数はより厳密です。したがって：

test [1..] = _|_   -- infinite loop (try it)
nub [1..] = [1..]

nubこれは、結果の計算を開始するためにリスト全体を必要としないことを意味し、したがって、ストリーム処理ゲームの優れたプレーヤーです。

厳密である理由elemは、厳密だからです。結果を返す前に、リスト全体を検索します (一致が見つからないと仮定します)。次のように記述できます。

nub :: (Eq a) => [a] -> [a]
nub = go []
    where
    go seen [] = []
    go seen (x:xs) | x `elem` seen = go seen xs
                   | otherwise     = x : go (x:seen) xs

がこれまでの出力のように成長するのに対し、あなたのものは残りの出力のseenように成長することに注意してください。前者は常に有限 ( から始まり、一度に 1 ずつ追加) ですが、後者は無限 (例: ) です。したがって、このバリアントは要素をより遅延して生成できます。[][1..]

Data.Setのリストの代わりに aを使用した場合、これはより高速になります (O(n^2) ではなく O(n log n)) seen。Ordしかし、それは制約を追加します。

于 2010-09-08T03:11:48.580 に答える
7

あなたの推論は正しいです:の要素ではないときにを追加するように、= x : ys andを切り替えるだけでよいのです。また、これとまったく同じことを行います。= ysxysData.List.nub

于 2010-09-08T02:56:05.833 に答える