Filter list of tuples by maximum element

Question

userDatabase is a list that consists of a tuples such as (id, username, password). How can I filter the list by using the maximum id? What I have at the moment is doing nothing but I thought I include it for some context.

newUser :: UserDatabase -> UserDatabase
newUser usrdb = filter (\(usrid,_,_) -> usrid == (maximum [x | (x, _, _) <- userdb])) userdb

Thanks in advance!

Answer 1

I have a list of type [(X, (R, R))] (a list of tuples, where 2^nd element is a tuple too), where X and R are some arbitrary types, and R is a member of typeclass Ord. Example of such list: [(0, (0,1)), (1, (1,1)), (2, (0,0)), (3, (1,0))]. Imagine I want to find all elements of this list, where the first element of the second element (that is, the left element of an inner tuple) is maximal. But I don't want just one such element, I want all elements, where a left element of an inner pair is maximal. So my function, called on the above list, should return [(1, (1,1)), (3, (1,0))]. maximumBy wouldn't work, because it would return only one element. So I wrote a variation of maximumBy, which returns multiple maximum values:

maximumByM :: (a -> a -> Ordering) -> [a] -> [a]
maximumByM c (x:xs) = maximumByM' c xs [x]
  where maximumByM' _ [] acc = acc
        maximumByM' c (x:xs) acc@(a:_) = case x `c` a of
          LT -> maximumByM' c xs acc
          EQ -> maximumByM' c xs (x:acc)
          GT -> maximumByM' c xs [x]

Suffix -M means “multiple”. This multiple-valued function returns a list of all values that are maximal (according to a custom comparison):

maximumByM compare [1,2,3] -- [3]
maximumByM compare [1,2,3,1,2,3] -- [3,3]
maximumByM (comparing fst) [(5,1), (5,2), (6,1), (6,2)] -- [(6,2),(6,1)]
maximumByM (comparing snd) [(5,1), (5,2), (6,1), (6,2)] -- [(6,2),(5,2)]

To implement minimumByM all you need to do is to flip the comparator, because compare 1 2 == (flip compare) 2 1:

maximumByM (flip $ comparing fst) [(5,1), (5,2), (6,1), (6,2)] -- [(5,2),(5,1)]
-- the below 2 are equivalent due to Haskell's currying
minimumByM = maximumByM . flip
minimumByM c xs = maximumByM (flip c) xs

Unfortunately maximumByM returns the list in reversed order. I could add reverse in code, but this double work? And explicit recursion? Why not implement the same function using right fold:

maximumByM :: (a -> a -> Ordering) -> [a] -> [a]
maximumByM _ [] = []
maximumByM c (x:xs) = foldr f [x] xs
  where f = (\e acc@(a:_) -> case c e a of
              LT -> acc
              EQ -> e:acc
              GT -> [e])

Now it returns the list in the same order as elements are found in the original list:

maximumByM (comparing fst) [(5,1), (5,2), (6,1), (6,2)] -- [(6,1),(6,2)]

Of course, you could use Boyd Stephen Smith Jr's approach, combining groupBy and sortBy (sortBy requires flip because it sorts from small to big):

maximumByM :: (a -> a -> Ordering) -> [a] -> [a]
maximumByM _ [] = []
maximumByM c xs = head $ groupBy ((==EQ) .: c) $ sortBy (flip c) xs
  where (.:) = (.).(.) -- x .: y = \a b -> x(y a b)

You don't need to reverse the list, because sortBy will preserve the order of elements it deems equal:

maximumByM (comparing fst) [(5,1), (5,2), (6,1), (6,2)] -- [(6,1),(6,2)]

Answer 2

Are all the usrid values distinct? In that case, there is only one maximum so you can do something like:

type User = (Int, String, String)
type UserDatabase = [User]

fst3 (x, _y, _z) = x

userHigh :: UserDatabase -> User
userHigh = maximumBy (comparing fst3)

If the ids are not distinct, you might have some ties, so you'll want to return a list

usersHigh :: UserDatabase -> [User]
usersHigh = concat . take 1
          . groupBy (on (==) fst3)
          . sortBy (flip $ comparing fst3)

Answer 3

Untested, but should get you going:

maximumBy :: Ord b => (a -> b) -> [a] -> Maybe a
maximumBy extract [] = Nothing
maximumBy extract (x:xs) = go x xs
    where go candidate [] = Just candidate
          go candidate (x:xs)
              | extract x > extract candidate = go x xs
              | otherwise = go candidate xs

EDIT: Oh, bhelkir points out this function already exists in the libraries. Anyway, a few points:

1. If you're trying to get just one item from the list, it's not a filter operation, it's more like a find or minimum/maximum operation.
2. The way you'd use this is something like this: maximumBy (\(usrid,_,_) -> usrid) users. The first argument to maximumBy is a function that extracts the comparison field from the elements of the list.