Изучай Haskell во имя добра!

Функция filter принимает предикат и список, а затем возвращает список элементов, удовлетворяющих предикату. Предикат – это функция, которая говорит, является ли что-то истиной или ложью, – то есть функция, возвращающая булевское значение. Сигнатура функции и её реализация:

filter :: (a –> Bool) –> [a] –> [a]

filter _ [] = []

filter p (x:xs)

  | p x       = x : filter p xs

  | otherwise = filter p xs

Довольно просто. Если выражение p x истинно, то элемент добавляется к результирующему списку. Если нет – элемент пропускается.

Несколько примеров:

ghci> filter (>3) [1,5,3,2,1,6,4,3,2,1]

[5,6,4]

ghci> filter (==3) [1,2,3,4,5]

[3]

ghci> filter even [1..10]

[2,4,6,8,10]

ghci> let notNull x = not (null x) in filter notNull [[1],[],[3,4],[]]

[[1],[3,4]]

ghci> filter (`elem` ['а'..'я']) "тЫ СМЕЕШЬСя, ВЕДЬ я ДрУГой"

"тяярой"

ghci> filter (`elem` ['А'..'Я']) "я Смеюсь, Ведь ты такОЙ же"

"СВОЙ"

Того же самого результата можно достичь, используя генераторы списков и предикаты. Нет какого-либо правила, диктующего вам, когда использовать функции map и filter, а когда – генераторы списков. Вы должны решить, что будет более читаемым, основываясь на коде и контексте. В генераторах списков можно применять несколько предикатов; при использовании функции filter придётся проводить фильтрацию несколько раз или объединять предикаты с помощью логической функции &&. Вот пример:

ghci> filter (<15) (filter even [1..20])

[2,4,6,8,10,12,14]

Здесь мы берём список [1..20] и фильтруем его так, чтобы остались только чётные числа. Затем список передаётся функции filter (<15), которая избавляет нас от чисел 15 и больше. Вот версия с генератором списка:

ghci> [ x | x <- [1..20], x < 15, even x]

[2,4,6,8,10,12,14]

Мы используем генератор для извлечения элементов из списка [1..20], а затем указываем условия, которым должны удовлетворять элементы результирующего списка.

Помните нашу функцию быстрой сортировки (см. предыдущую главу, раздел «Сортируем, быстро!»)? Мы использовали генераторы списков для фильтрации элементов меньших (или равных) и больших, чем опорный элемент. Той же функциональности можно добиться и более понятным способом, используя функцию filter:

quicksort :: (Ord a) => [a] –> [a]

quicksort [] = []

quicksort (x:xs) =

  let smallerSorted = quicksort (filter (<= x) xs)

      biggerSorted = quicksort (filter (> x) xs)

  in  smallerSorted ++ [x] ++ biggerSorted

Ещё немного примеров использования map и filter

Давайте найдём наибольшее число меньше 100 000, которое делится на число 3829 без остатка. Для этого отфильтруем множество возможных вариантов, в которых, как мы знаем, есть решение.

largestDivisible :: Integer

largestDivisible = head (filter p [100000,99999..])

  where p x = x `mod` 3829 == 0

Для начала мы создали список всех чисел меньших 100 000 в порядке убывания. Затем отфильтровали список с помощью предиката. Поскольку числа отсортированы в убывающем порядке, наибольшее из них, удовлетворяющее предикату, будет первым элементом отфильтрованного списка. Нам даже не нужно использовать конечный список для нашего базового множества. Снова «лень в действии»! Поскольку мы используем только «голову» списка, нам неважно, конечен полученный список или бесконечен. Вычисления прекращаются, как только находится первое подходящее решение.

Теперь мы собираемся найти сумму всех нечётных квадратов меньших 10 000. Но для начала познакомимся с функцией takeWhile: она пригодится в нашем решении. Она принимает предикат и список, а затем начинает обход списка с его «головы», возвращая те его элементы, которые удовлетворяют предикату. Как только найден элемент, не удовлетворяющий предикату, обход останавливается. Если бы мы хотели получить первое слово строки "слоны умеют веселиться", мы могли бы сделать такой вызов: takeWhile (/=' ') "слоны умеют веселиться", и функция вернула бы "слоны".