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

Question

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

Answer 1

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

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

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

Answer 2

Нет, нет предопределенной функции, которая делает это, но я бы сказал, что 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 - разумное имя переменной).

Answer 3

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

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

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

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

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

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

2. Даже если это невозможноОптимизированный, лень часто делает такой код достаточно эффективным в любом случае.

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

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

Answer 4

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

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