Понимание фильтра Хаскелла

Question

Я понимаю, что фильтр Хаскелла - это функция высокого порядка (имеется в виду функция, которая принимает в качестве параметра другую функцию), которая проверяет список, какой элемент удовлетворяет определенному логическому условию.

Я не совсем понимаю его определение:

filter:: (a->Bool)->[a]->[a]
filter p [] = []
filter p (x:y) | p x = x:filter p y
               | otherwise = filter p y

Я понимаю, что если я передам пустой список функции, она просто вернет пустой список, но как мне прочитать последние две строки?

Answer 1

Используются охранники , которые, если вы пришли из языка с синтаксисом стиля C, немного похожи на структуру switch.

Последний шаблон гласит: Если функция p оценивается как true с аргументом x, тогда возвращает заголовок списка и отфильтрованный хвост списка. В противном случае просто верните отфильтрованный хвост списка.

Вы также можете переписать это так:

filter p (x:y) = if (  p x ) then
                     x:filter p y
                 else
                     filter p y

Answer 2

Рассмотрим описание filter в документах :

filter, примененный к предикату и списку, возвращает список тех элементов, которые удовлетворяют предикату; т.е. ,

filter p xs = [x | x <- xs, p x]

Чтобы объяснить это кому-то, кто не понимает понимания списка, можно сказать, что filter имеет три случая:

1. (простой случай), когда фильтруемый список пуст, результат также пуст
2. когда заголовок фильтруемого списка удовлетворяет предикату, это часть результата
3. в противном случае пропустите заголовок и отфильтруйте оставшуюся часть списка

Эти случаи соответствуют один к одному с тремя последними строками вашего вопроса.

Маленькие штрихи могут сделать определение более идиоматичным и, следовательно, более легким для чтения:

filter _ []      = []
filter p (x:xs)
  | p x          = x : filter p xs
  | otherwise    =     filter p xs

Для пустого списка предикатом может быть что угодно, и подчеркивание явно показывает, что в этом случае это неважно.

Вместо сопоставления с (x:y), используя (x:xs) - think: "ex and exes" - подчеркивает, что вы разделяете список на его голову (типа a) и tail (типа [a] , т.е. , список a).

Наконец, выстраивание рекурсивных вызовов в filter позволяет читателю увидеть, что в последнем случае пропущен x.