Рекурсия или понимание списка?

Работая над Learn You a Haskell For Great Good, в главе о функциях высшего порядка автор рассматривает реализацию нескольких различных библиотечных функций. Когда я пришел к определению filter' (повторная реализация стандартной библиотечной функции filter), я подумал, что очевидным было следующее:

filter' f xs = [x | x <- xs, f x]

Но автор дает следующее более длинное рекурсивное определение:

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

Оба определения делают одно и то же. Есть ли для этого причина? Является ли рекурсивное определение более эффективным? Это более идиоматично для Haskell? Что-то другое?


recursion list-comprehension haskell
person JSBձոգչ    schedule 09.07.2011    source источник
comment
filter' также можно записать в терминах функции высшего порядка foldr, как в filter' p = foldr (\x ys -> if p x then x : ys else ys) [], хотя это был бы лучший пример использования функции высшего порядка, чем создание ее с нуля.   -  person hammar    schedule 09.07.2011
comment
См. Haskell 2010 › Expressions › List Comprehension, если вам интересно в том, как они обессахаривают.   -  person Dan Burton    schedule 10.07.2011

Ответы (2)


arrow_upward
16
arrow_downward

Вероятно, это потому, что понимание списка - это просто синтаксический сахар, который в принципе переводится в рекурсивную форму.

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

Короче говоря, он показывает, как реализовать из довольно минимального набора основных строительных блоков.

Однако это предположение - я сам не читал этот учебник.

person Steve314    schedule 09.07.2011

arrow_upward
8
arrow_downward

Понимание списка — это довольно много сахара для карты и фильтра в одной операции; Хотя он может использовать concatMap в бэкэнде. Как правило, использование чего-то с более высокой абстракцией для реализации чего-то с более низкой абстракцией является мошенничеством.

person alternative    schedule 09.07.2011
comment
Вы не можете реализовать понимание списка с точки зрения только карты и фильтра, вам действительно нужен concatMap. - person augustss; 09.07.2011
comment
@augustss Как вы думаете, почему я специально упомянул, что он использует concatMap? Я имел в виду, что фильтр является частью concatMap. - person alternative; 09.07.2011
comment
может использовать не звучало как должен использовать. :) - person augustss; 09.07.2011
comment
@augustss Конечно, это не обязательно использовать, вы можете все это реализовать заново. - person alternative; 09.07.2011
comment
Я думаю, что точка зрения augustss здесь заключается в том, что concatMap полностью включает в себя map и filter, а также делает то, чего они не могут, и что любая повторная реализация для создания списковых включений обязательно будет эквивалентна concatMap. - person C. A. McCann; 09.07.2011
comment
Включение списков можно рассматривать как работу внутри монады списка с присваиванием, соответствующим связыванию, и условиями, указывающими защиту. Как уже отмечалось, реализация привязки требует concatMap, а map и filter по отдельности не годятся. Насколько мне известно, вы не можете реализовать concatMap с точки зрения map и filter. - person Sujay Jayakar; 12.07.2011
comment
@Sujay concatMap = concat . карта... Да, реализовано с точки зрения карты, а затем фильтр может быть реализован с помощью concat Map - person alternative; 12.07.2011