Haskell: سلوك مفاجئ من "Gramby"

Question

أحاول معرفة سلوك وظيفة وظيفة المكتبة (من البيانات .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]]

ماذا ينقصني؟

Answer 1

Have a look at the ghc implementation of groupBy:

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

Now compare these two outputs:

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

In short, what happens is this: groupBy assumes that the given function (the first argument) tests for equality, and thus assumes that the comparison function is reflexive, transitive and symmetric (see equivalence relation). The problem here is that the less-than relation is not reflexive, nor symmetric.

---

Edit: The following implementation only assumes transitivity:

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

Answer 2

حقيقة أن "<" ليس اختبار المساواة.

قد تتوقع بعض السلوك لأنك تطبقها بشكل مختلف، ولكن هذا ليس ما يعود به.

مثال على سبب أن ما تخرجه هو إجابة معقولة هو أن تجتاحه

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

لديه الآن 3 مجموعات من العناصر المتساوية. لذلك يتحقق مما إذا كان أي منهم في الواقع هو نفسه:

نظرا لأنه يعرف أن جميع العناصر في كل مجموعة متساو، فيمكن أن ننظر فقط إلى العنصر الأول في كل منها و 1 و 2 و 1.

1> 2؟ نعم! لذلك يدمج المجموعتين الأولين.

1> 1؟ رقم! لذلك يغادر المجموعة الأخيرة.

والآن تقارن جميع العناصر للمساواة.

... فقط، أنت لم تمريرها نوع الوظيفة المتوقع.

بالمختصر، عندما يريد اختبار المساواة، اعطيه اختبار المساواة.

Answer 3

المشكلة هي أن التنفيذ المرجعي لل groupBy في تقرير Haskell يقارن عناصر ضد العنصر الأول، لذلك لا تتزايد المجموعات بشكل صارم (يتعين عليهم أن يكونوا جميعا أكبر من العنصر الأول). ما تريد بدلا من ذلك هو نسخة من groupBy أن الاختبارات على ذلك متاخم عناصر، مثل التنفيذ هنا.

Answer 4

أود فقط الإشارة إلى أن وظيفة Gramby تتطلب أيضا قائمتك سيتم فرزها قبل تطبيقها.

علي سبيل المثال:

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 يستخدم SPAN في تعريفه. للحصول على سلوك معقول لا يعتمد علينا على وجود القائمة الكامنة في أي أمر معين، يمكننا تحديد الوظيفة:

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