Функция filter

Рассмотрим еще несколько функций. Опять-таки, сначала разберитесь, что конкретно делает каждая из этих функций:

foo [] = []

foo (x:xs) | x > 0 = x : foo xs

| otherwise = foo xs

moo [] = []

moo (x:xs) | x `mod` 2 == 0 = x : moo xs

| otherwise = moo xs

boo [] = []

boo (x:xs) | x `elem` ['0'..'9'] = boo xs

| otherwise = x : boo xs

goo [] = []

goo (s:ss) | length s == 0 = goo ss

| otherwise = s : goo ss

Что делают все эти функции? Первая функция берет числовой список и возвращает список только положительных элементов из него. Вторая функция оставляет в числовом списке только четные числа. Третья функция выкидывает из строки (списка символов) цифры. Четвертая функция берет список строк, и выбрасывает из него пустые строки.

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

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

filter f [] = []

filter f (x:xs) | f x = x : filter f xs

| otherwise = filter f xs

И здесь опять параметризуется (то есть становится параметром более общей функции) то, что отличает эти четыре функции: условие, по которому принимается решение – выбросить элемент или поместить в результирующий список. Давайте теперь перепишем все функции с помощью функции filter:

foo = filter (>0)

moo = filter (\x -> x `mod` 2 == 0)

boo = filter (\x -> not (x `elem` ['0'..'9']))

goo = filter (\s -> not (null s))

А как насчет функции, которая бы выкидывала отрицательные числа из списка, а положительные увеличивала бы на единицу? Думаю, вы уже догадались – это не filter, потому что filter не может изменить элементы списка, а только выкинуть или не выкинуть.

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

Если вспомнить функцию map, то функцию filter тоже можно представить в виде робота, который идет вдоль конвейера с предметами, применяет к каждому предмету свое условие, и если условие не выполняется – выкидывает предмет с контейнера. Как и робот для функции map, новый робот тоже видит в каждый момент времени только один элемент, и ничего не может запоминать, переходя от одного элемента к другому.

И функция filter также отлично фильтрует бесконечные списки! Правда, вычисление выражения filter (==2) [1..] не завершится никогда: функции filter неоткуда взять информацию о том, что в списке натуральных чисел число 2 встречается только один раз!