Finding max list within a list

Question

I was trying to get the list with the greatest sum within a list and then return that list. But when I call the function with

max_list [[1,2],[3,6],[10,34,5]]

it gives me the error:

Exception: a4.hs:65:1-64: Non-exhaustive patterns in function max_list

This is the code:

max_num :: [Int] -> Int
max_num [x] = x
max_num (x:xs) | (max_num xs) > x = maxVal xs
               | otherwise        = x

max_list :: [[Int]] -> [Int]
max_list [[a]] = head(filter (\x -> (sum_int x) == (max_num [[a]]) [[a]])

My logic is as follows: I will

Sum the elements in the sublist
Compare that element to see if it equals the max-value of the list
Filter out the values that do not equal the max-value

Example call:

head (filter (\x -> (sum x) == 11) [[1,3],[4,7],[2,5]])
> [4,7]

So in that case I calculated the value 11 before hand and its sum of each element is [4, 11, 7] and it will give me the value whose sum is equal to the max value

`[[a]]` is a pattern that matches a singleton list that contains a singleton list. You probably meant to just use `a` (without any brackets). Similarly, `[x]` is a pattern that matches a list with only one element (and that element is named `x`). `max_num` is missing a pattern that matches the empty list. — 4castle, Mar 13 '18 at 05:14
On the issue @4castle mentions, see also [*Why doesn't this function work if I use "\[xs\]" instead of "xs"?*](https://stackoverflow.com/q/48884276/2751851) — duplode, Mar 13 '18 at 05:31
oh thanks for that. I wasn't aware when reading through the documentation and patterns. Thanks! — xnv23, Mar 13 '18 at 05:50

Adam Smith · Accepted Answer · 2018-03-13T20:17:30.460

7

There is a function in Data.List called maximumBy with the signature

maximumBy :: (a -> a -> Ordering) -> [a] -> a

and Data.Function has on with the signature

on :: (b -> b -> c) -> (a -> b) -> a -> a -> c

Applied with the compare function (compare :: Ord a => a -> a -> Ordering), we can see how this is exactly what you're looking for.

import Data.List     (maximumBy)
import Data.Function (on)

{- for clarity:
   compare          :: Ord a          => b -> b -> Ordering
   (compare `on`)   :: Ord b          => (a -> b) -> a  ->  a  -> Ordering
   compare `on` sum :: (Num a, Ord a) =>            [a] -> [a] -> Ordering
   -- well actually [a] is t a for a foldable t, but same diff -}
result = maximumBy (compare `on` sum) [[1,2],[3,6],[10,34,5]]

to implement this yourself, you could write a fold that compares each value according to its sum, recursing until the sum of x is greater than anything that comes before after it.

myMaximumBySum []     = [] -- degenerate case
myMaximumBySum [x]    = x  -- tautological case
myMaximumBySum (x:xs)
  | sum x > sum (myMaximumBySum xs) = x
  | otherwise                       = myMaximumBySum xs

-- or more naturally:
myMaximumBySum = foldr f []
  where f x acc = if sum x > sum acc then x else acc

edited Mar 13 '18 at 20:17

answered Mar 13 '18 at 05:11

Adam Smith

52,157
12
73
112

is there any way to write a general maximum by function using fold/recursion? – xnv23 Mar 13 '18 at 05:53
@xnv23 `maximumBy fun (l:ls) = foldl (\x y-> if fun x < fun y then y else x ) l ls` – rjpj1998 Mar 13 '18 at 06:18
I think you got the imported function a bit wrong. The type is `maximumBy :: (a -> b) -> [a] -> a`, so perhaps the answer should be updated w.r.t. this signature? – Willem Van Onsem Mar 13 '18 at 08:55
@WillemVanOnsem That looks fine to me. if `:t [[1,2],[3,6],[10,34,5]] :: [a]` then `:t [10,34,5] :: a` – rjpj1998 Mar 13 '18 at 12:21
3

@rjpj1998: sorry, I meant that the type is *not* that one, but `maximumBy :: Foldable t => (a -> a -> Ordering) -> t a -> a`, and that `sum` does not match with `a -> a -> Ordering`. – Willem Van Onsem Mar 13 '18 at 12:39
@WillemVanOnsem fixed. – Adam Smith Mar 13 '18 at 20:17

Finding max list within a list

1 Answers1