CODEWITHSUNDEEP
listhaskell
KevinCameron1337
KevinCameron1337

Reputation: 517

Comparing list length

I have a list of lists, let's say:

import Data.List

xs = [[1,2], [1,2,3], [2,3]]

I want to get the inner list with the most items, in this case [1,2,3].

I'm trying to use the maximumBy function from the Data.List library:

maximumBy (compare `on` length) xs

but I get the following error: not in scope 'on'

Can anyone tell me what is wrong, or if you have a better way to get the list?

Upvotes: 9

Views: 8163

Answers (5)

phimuemue
phimuemue

Reputation: 36081

Try

maximumBy (comparing length)

or

maximumBy (on compare length)

or

maximumBy (compare `on` length)

Upvotes: 4

Landei
Landei

Reputation: 54584

Inspired by hammar's solution, but with just one pass thru the list:

import Data.List

longest = snd . foldl' cmp (0,[]) where
   cmp maxPair@(maxLen, _) list = 
      let len = length list 
      in if len > maxLen then (len, list) else maxPair

Upvotes: 1

hammar
hammar

Reputation: 139930

While using maximumBy with comparing length or compare `on` length will do the job just fine for short lists, note that this is not a very efficient solution if the lists are long, since each time the algorithm compares two lists, it will re-calculate their lengths.

For example, if we have a very long first list, followed by many short lists, using maximumBy will be very slow since the length of the first list will be re-calculated at each step.

> import Data.List
> import Data.Ord
> let xs = replicate 50000 'a' : replicate 50000 "b"
> maximumBy (comparing length) xs
<snip>
(16.09 secs, 98338680 bytes)

We can get a more efficient solution by caching the lengths of the lists:

> let longest xss = snd $ maximumBy (comparing fst) [(length xs, xs) | xs <- xss]
> longest xs
<snip>
(0.35 secs, 91547296 bytes)

Of course, this might not make a big difference if your lists are small, but it's worth taking note of.

Upvotes: 9

Random Dev
Random Dev

Reputation: 52300

or you can make it a bit more explicit:

xs = [[1,2],[1,2,3],[2,3]]
ordLen a b = compare (length a) (length b)
maximumBy ordLen xs

maybe it's easier to understand this way.

Upvotes: 5

interjay
interjay

Reputation: 110203

on is defined in Data.Function, so you need to import that.

Alternatively, you can use comparing from Data.Ord:

maximumBy (comparing length) xs

Upvotes: 10

Related Questions