Сравнение длины списка

#list #haskell

#Список #haskell

Вопрос:

Скажем, у меня есть список списков:

 import Data.List

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

В данном случае я хочу получить внутренний список с наибольшим количеством элементов [1,2,3] .

Я пытаюсь использовать maximumBy функцию из Data.List библиотеки:

 maximumBy (compare `on` length) xs

но я получаю следующую ошибку: not in scope 'on'

Кто-нибудь может сказать мне, что не так, или если у вас есть лучший способ получить список?

Ответ №1:

on определяется в данных.Функция, поэтому вам нужно ее импортировать.

В качестве альтернативы вы можете использовать comparing from Data.Ord:

 maximumBy (comparing length) xs

1. Спасибо, это сработало … не знал, что мне нужна другая библиотека. Haskell новичок здесь.

2. я буду… нужно подождать 5 минут!

3. @Special—k Hoogle отлично подходит для определения, из какого модуля необходимо импортировать функцию.

Ответ №2:

Хотя использование maximumBy с comparing length или compare `on` length отлично справится с задачей для коротких списков, обратите внимание, что это не очень эффективное решение, если списки длинные, поскольку каждый раз, когда алгоритм сравнивает два списка, он пересчитывает их длины.

Например, если у нас очень длинный первый список, за которым следует много коротких списков, использование maximumBy будет очень медленным, поскольку длина первого списка будет пересчитываться на каждом шаге.

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

Мы можем получить более эффективное решение, кэшируя длины списков:

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

Конечно, это может не иметь большого значения, если ваши списки маленькие, но это стоит принять к сведению.

1. Нет ли какой-либо другой версии без пересчета maximumBy ? Кстати, как вы добираетесь ghci до времени выполнения печати?

2. @Tarrasch: Я думаю, ни в одной из стандартных библиотек. Используется :set s для включения синхронизации каждой оценки.

3. @Tarrasch: По-видимому, было предложение добавить такие функции , но, похоже, от него отказались.

Ответ №3:

или вы можете сделать это немного более явным:

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

может быть, так легче понять.

Ответ №4:

Попробуйте

 maximumBy (comparing length)

или

 maximumBy (on compare length)

или

 maximumBy (compare `on` length)

Ответ №5:

Вдохновленный решением Хаммара, но всего за один проход по списку:

 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