Понимание фильтра Haskell
Я понимаю, что фильтр Haskell является высокого уровня функцией (значение функции, которая берет другую функцию в качестве параметра), который проходит список, проверяющий, какой элемент выполняет определенное булево условие.
Я не вполне понимаю его определение:
filter:: (a->Bool)->[a]->[a]
filter p [] = []
filter p (x:y) | p x = x:filter p y
| otherwise = filter p y
Я понимаю, что, если бы я передаю пустой список функции, это просто возвратило бы пустой список, но как я читаю последние две строки?
2 ответа
Он использует предохранители , которые, если вы переходите с языка с синтаксисом стиля C, немного похожи на структуру переключателя .
Последний шаблон гласит: Если функция p оценивается как истина с аргументом x , то возвращает заголовок списка и отфильтрованный конец списка. В противном случае просто верните отфильтрованный хвост списка.
Вы также можете переписать его так:
filter p (x:y) = if ( p x ) then
x:filter p y
else
filter p y
Рассмотрим описание фильтра в документах :
фильтр, примененный к предикату и списку, возвращает список тех элементов, которые удовлетворяют предикату ; т.е. ,фильтр p xs = [x | x <- xs, px]
Чтобы объяснить это тому, кто не понимает понимания списков, вы можете сказать, что фильтр имеет три случая:
- (простой случай) когда список, который нужно отфильтровать, пуст, результат также будет пуст
- , когда заголовок списка, который нужно отфильтровать, удовлетворяет предикату, он является частью результата
- в противном случае пропустите заголовок и отфильтруйте остальную часть списка
Эти случаи однозначно соответствуют последним трем строкам определения в вашем вопросе.
Небольшие штрихи могут сделать определение более идиоматическим и, следовательно, более легким для чтения:
filter _ [] = []
filter p (x:xs)
| p x = x : filter p xs
| otherwise = filter p xs
Для пустого списка предикатом может быть что угодно, а подчеркивание явно показывает, что в этом случае это неважно.
Вместо сопоставления с (x: y) , использование (x: xs) - подумайте: «ex and exes» - подчеркивает, что вы разделяете список на голова (типа a ) и хвост (типа [a] , т.е. , список a ).
Наконец, выстраивание рекурсивных вызовов filter легко позволяет читателю увидеть, что последний случай пропускает x .