CODEWITHSUNDEEP
haskell
sidoshi
sidoshi

Reputation: 2160

Evaluation of `groupBy` in haskell

Why does 

groupBy (>) [-5,-4,5,4,-2,-3,2,3]

evaluate to 

[[-5],[-4],[5,4,-2,-3,2,3]]

As -3 is not greater than 2 shouldn't it group them differently? I expected the result to be 

[[-5],[-4],[5,4,-2,-3],[2,3]]

What am I missing?

Upvotes: 4

Views: 170

Answers (1)

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476659

groupBy :: (a -> a -> Bool) -> [a] -> [[a]] uses the first member of the group as reference. So if you write:

groupBy eq (x:x2:x3)

it will - if eq x x2 is satisfied, call eq x x3 to check if x3 also belongs to the same group. So the calls are:

arg1 | arg2 | (>) `on` (*1)
  -5 |   -4 | False
  -4 |    5 | False
   5 |    4 | True
   5 |   -2 | True
   5 |   -3 | True
   5 |    2 | True
   5 |    3 | True

We can see this in the source code 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

As you can see, the span takes eq x as predicate, and x is the first member of the group.

The function probably expects a -> a -> Bool to be an equivalence relation: an equivalence relation is (1) reflexive; (2) symmetric; and (3) transitive. Your function is not an equivalence relation since it is not reflexive nor symmetric. So you can not (safely) use groupBy with an order relation.

Note: (>) `on` (*1) is equivalent to just (>) because (*1) will return the same number, you only make the function more specific here to only work on Nums, but that is not necessary.

Upvotes: 4

Related Questions