extending howManyEqual

Submitted by metaperl on Mon, 05/08/2006 - 5:50pm.

given
howManyEqual a b c = fromEnum(a == b) + fromEnum(b == c) + fromEnum(a == c)

how would I write howManyEqualFour a b c d

Submitted by Cale Gibbard on Mon, 05/08/2006 - 11:54pm.

I'd probably start first by defining the operation I wanted on lists. It's unclear exactly how you want howManyEqual to generalise in this case, but I can offer some examples.

One place to start is to construct a list of the sizes of sets of elements in the list which are equal to each other.

import Data.List

equalSizes :: Eq a => [a] -> [Int]
equalSizes [] = []
equalSizes (x:xs) = length us : equalSizes vs
    where (us,vs) = partition (== x) (x:xs)

An important thing to note is that if we can assume that the values in the list are of an ordered type, and we don't care about the ordering of the output list, then we can get a much more efficient implementation, and also one which is easier to define:

equalSizes' :: Ord a => [a] -> [Int]
equalSizes' = map length . group . sort

Either way, this is a decent starting point, from here, we can construct other generalisations of howManyEqual. Probably the most obvious one is the maximum value of equalSizes (or 0 if it is empty).

howManyEqual :: Eq a => [a] -> Int
howManyEqual = foldl' max 0 . equalSizes

We might also be looking for the sum of the sizes which are greater than 1, that is, the number of elements in the list which are equal to something else in the list.

howManyEqual' :: Eq a => [a] -> Int
howManyEqual' = sum . filter (/= 1) . equalSizes

Another generalisation might be the number of pairs of distinct list elements which are equal (which is sort of what the implementation you gave hints at). Since we can already get the sizes of the classes of elements which are equal to each other, we might as well use it. It's easy to work out how many pairs each of those will generate, a class of size k will give (k;2) = k (k-1)/2 equal pairs, where (k;2) is the binomial coefficient. This makes sense in elementary terms, as there are k ways to pick one element, then k-1 to pick a different one after that, but for any given pair, we could have chosen either element first, so we're double counting, and divide by two to account for that.

howManyEqual'' :: Eq a => [a] -> Int
howManyEqual'' = sum . map (\k -> k * (k-1) `div` 2) . equalSizes

All of these generalisations are the same as your original function on lists of size 3, but they're all different from each other on larger lists.

Really, equalSizes is probably the best generalisation, as it's quite likely that any other generalisation you'll want, you can construct easily from it.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.