15

最初の引数として渡された「等式テスト」関数によってリストの要素をグループ化することを目的としたライブラリ関数groupBy（Data.Listから）の動作を理解しようとしています。型シグネチャは、同等性テストに型が必要であることを示しています

(a -> a -> Bool)

ただし、GHCi 6.6で「同等性テスト」として（<）を使用すると、結果は期待したものとは異なります。

ghci> groupBy (<) [1, 2, 3, 2, 4, 1, 5, 9]
[[1,2,3,2,4],[1,5,9]]

代わりに、次のように、厳密に増加する数の実行を期待します。

[[1,2,3],[2,4],[1,5,9]]

私は何が欠けていますか？

4

4 に答える 4

34

groupByのghc実装を見てください：

groupBy                 :: (a -> a -> Bool) -> [a] -> [[a]]
groupBy _  []           =  []
groupBy eq (x:xs)       =  (x:ys) : groupBy eq zs
                           where (ys,zs) = span (eq x) xs

次に、これら2つの出力を比較します。

Prelude List> groupBy (<) [1, 2, 3, 2, 4, 1, 5, 9]
[[1,2,3,2,4],[1,5,9]]
Prelude List> groupBy (<) [8, 2, 3, 2, 4, 1, 5, 9]
[[8],[2,3],[2,4],[1,5,9]]

要するに、これは次groupByのようになります。与えられた関数（最初の引数）が等式をテストすると仮定し、したがって、比較関数が反射的、推移的、対称的であると仮定します（同値関係を参照）。ここでの問題は、小なりの関係が反射的でも対称的でもないということです。

編集：次の実装は推移性のみを想定しています。

groupBy' :: (a -> a -> Bool) -> [a] -> [[a]]
groupBy' _   []                        = []
groupBy' _   [x]                       = [[x]]
groupBy' cmp (x:xs@(x':_)) | cmp x x'  = (x:y):ys
                           | otherwise = [x]:r
  where r@(y:ys) = groupBy' cmp xs
于 2009-08-22T16:34:37.880 に答える
9

「<」が同等性テストではないという事実。

実装方法が異なるため、何らかの動作が予想される場合がありますが、それは約束されたものではありません。

それが出力するものが合理的な答えである理由の例は、それがそれを一掃するかどうかです。

[1, 2, 3, 2, 4, 1, 5, 9] ->
[[1,2,3], [2,4], [1,5,9]]

これで、等しい要素の3つのグループができました。したがって、それらのいずれかが実際に同じであるかどうかをチェックします。

各グループのすべての要素が等しいことを知っているので、それぞれの最初の要素、1、2、および1を見ることができます。

1> 2？はい！したがって、最初の2つのグループをマージします。

1> 1？いいえ！したがって、最後のグループを残します。

そして今、それは平等のためにすべての要素を比較しました。

...ただ、期待したような関数を渡さなかっただけです。

つまり、同等性テストが必要な場合は、同等性テストを実行します。

于 2009-08-22T16:36:04.757 に答える
9

問題は、Haskell レポートの の参照実装がgroupBy要素を最初の要素と比較するため、グループが厳密に増加していないことです (最初の要素よりもすべて大きくなければなりません)。代わりに必要なのは、実装hereのように、隣接するgroupBy要素をテストするバージョンです。

于 2009-08-22T18:50:28.650 に答える
0

groupBy 関数では、リストを適用する前に並べ替える必要があることも指摘しておきます。

例えば：

equalityOp :: (a, b1) -> (a, b2) -> Bool
equalityOp x y = fst x == fst y

testData = [(1, 2), (1, 4), (2, 3)]

correctAnswer = groupBy equalityOp testData == [[(1, 2), (1, 4)], [(2, 3)]]

otherTestData = [(1, 2), (2, 3), (1, 4)]

incorrectAnswer = groupBy equalityOp otherTestData == [[(1, 2)], [(2, 3)], [(1, 4)]]

この動作は、groupBy がその定義でスパンを使用しているため発生します。基礎となるリストを特定の順序で持っていることに依存しない合理的な動作を取得するには、関数を定義できます。

groupBy' :: (a -> a -> Bool) -> [a] -> [[a]]
groupBy' eq []     = []
groupBy' eq (x:xs) = (x:similarResults) : (groupBy' eq differentResults)
    where similarResults   = filter (eq x) xs
          differentResults = filter (not . eq x) xs
于 2018-09-07T20:07:40.497 に答える