ハスケル：「GROUPBY」の驚くべき行動

StackOverflow https://stackoverflow.com/questions/1316365

  •  19-09-2019
  •  | 
  •  

質問

私は、最初の引数として渡された「平等テスト」機能により、リストのグループ要素に主張しているライブラリ関数（Data.Listから）GROUPBYの行動を把握しようとしています。型シグネチャは、平等のテストだけでタイプを持つ必要があることを示唆している。

(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]]

私は何をしないのですか？

役に立ちましたか？

解決

<のhref = "http://www.haskell.org/ghc/docs/latest/html/libraries/base/src/Data-ListののGHC の実装を見てください.htmlを＃GROUPBY」のrel = "noreferrer"> GROUPBYするます：

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

他のヒント

"<" という事実は平等のテストではありません。

あなたは違っそれを実装したいので、あなたには、いくつかの行動を期待するかもしれないが、それはそれは約束するものではありません。

それはやって、それを介してスイープする場合は、

何それは出力することは合理的な答えである理由の例です。

[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？番号！だから、最後のグループがあること去るます。

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

...唯一、あなたはそれにそれが期待される機能の種類を渡しませんでした。

要するに、それは平等のテストを希望する場合、与えますそれ平等テストするます。

問題がHaskellレポートでgroupByのリファレンス実装は、最初の要素に対して要素を比較することで、そのグループは厳密に（彼らは最初の要素よりも、すべての大きなする必要が）増加していません。あなたが代わりに欲しいのは、の隣接するの要素、実装のような<のhref =「http://www.haskell.org/haskellwiki/List_function_suggestions#Generalize_groupBy_and_friends」のrel = "noreferrerにテストgroupByのバージョンであります「>ここを。

私はちょうど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
ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top