Подсчет количества элементов в списке, которые удовлетворяют заданному предикату

Имеет ли стандартная библиотека Haskell функцию, предоставляющую список и предикат, возвращает количество элементов, удовлетворяющих этому предикату? Что-то вроде типа (a -> Bool) -> [a] -> Int. Мой поиск hoogle не возвращал ничего интересного. В настоящее время я использую length . filter pred, который я не считаю особенно элегантным решением. Мой вариант использования, кажется, достаточно распространен, чтобы иметь лучшее решение библиотеки. Является ли это тем или неправильным предчувствием?

Ответ 1

Реализация length . filter p не так плоха, как вы предлагаете. В частности, он имеет только постоянные накладные расходы в памяти и скорости, поэтому да.

Для вещей, которые используют слияние потоков, например пакет vector, length . filter p будет фактически оптимизирован, чтобы избежать создания промежуточного вектора. Однако в списках используется то, что называется foldr/build fusion на данный момент, что недостаточно для оптимизации length . filter p без создания линейно больших трюков, которые переполняют стек стека.

Подробнее о поточном слиянии см. в этом документе. Насколько я понимаю, причина, по которой потоковое слияние в настоящее время не используется в основных библиотеках Haskell, заключается в том, что (как описано в статье) около 5% программ значительно ухудшаются при реализации поверх потоковых библиотек, а foldr/build Оптимизация никогда не сможет (AFAIK) значительно повысить производительность.

Ответ 2

Haskell - это язык высокого уровня. Вместо того, чтобы предоставлять одну функцию для любой возможной комбинации обстоятельств, с которыми вы когда-либо сталкивались, она предоставляет вам небольшой набор функций, которые охватывают все основы, и затем вы склеиваете их вместе, чтобы решить любую проблему в настоящее время.

В терминах простоты и лаконичности это так же изящно, как и получается. Так что да, length . filter pred является абсолютно стандартным решением. В качестве другого примера рассмотрим elem, который (как вы знаете) указывает, присутствует ли данный элемент в списке. Стандартная эталонная реализация для этого на самом деле

elem :: Eq x => x -> [x] -> Bool
elem x = foldr (||) False . map (x ==)

В словах сравните каждый элемент в списке с целевым элементом, создав новый список Bools. Затем сверните функцию логического-ИЛИ над этим новым списком.

Если это кажется неэффективным, постарайтесь не беспокоиться об этом. В частности,

Компилятор часто может оптимизировать временные структуры данных, созданные таким кодом. (Помните, что это стандартный способ написания кода в Haskell, поэтому компилятор настроен на его устранение.)
Даже если его невозможно оптимизировать, ленивость часто делает такой код достаточно эффективным.

(В этом конкретном примере функция OR прекратит цикл, как только будет видно совпадение - точно так же, как если бы вы вручную закодировали его.)

Как правило, пишите код, склеивая ранее существовавшие функции. Измените это, только если производительность недостаточно.

Ответ 3

Нет, нет предопределенной функции, которая делает это, но я бы сказал, что length . filter pred - это, по сути, элегантная реализация; это как можно ближе к выражению того, что вы имеете в виду, просто не ссылаясь на концепцию напрямую, чего вы не можете сделать, если вы ее определяете.

Единственными альтернативами были бы рекурсивная функция или сгиб, которые ИМО были бы менее изящными, но если вы действительно хотите:

foo :: (a -> Bool) -> [a] -> Int
foo p = foldl' (\n x -> if p x then n+1 else n) 0

Это в основном просто вложение length в определение. Что касается именования, я бы предложил count (или, возможно, countBy, так как count - разумное имя переменной).

Ответ 4

Это мое любительское решение аналогичной проблемы. Подсчитайте количество отрицательных целых чисел в списке l

nOfNeg l = length(filter (<0) l)
main = print(nOfNeg [0,-1,-2,1,2,3,4] ) --2