Функция filter

Функция 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