Улучшите мою реализацию Haskell Фильтра

Самый простой способ сделать вашу реализацию более аккуратной - использовать охранники. Вместо pattern = value можно написать pattern | boolean = value; это будет соответствовать только тогда, когда boolean истинно. Таким образом, мы можем получить

filter1 :: (a -> Bool) -> [a] -> [a]
filter1 p (x:xs) | p x       = x : filter1 p xs
                 | otherwise = filter1 p xs
filter1 _ []                 = []

(Обратите внимание, что otherwise - это просто синоним True). Теперь у нас есть filter p xs в двух местах, поэтому мы можем перенести его в предложение where; они общие для всего, что имеет общий шаблон, даже если у него другой guard:

filter2 :: (a -> Bool) -> [a] -> [a]
filter2 p (x:xs) | p x       = x : xs'
                 | otherwise = xs'
  where xs' = filter2 p xs
filter2 _ []                 = []

(Эта реализация используется в GHC Prelude.)

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

filter3 :: (a -> Bool) -> [a] -> [a]
filter3 p xs = let filter3' p (x:xs) ys | p x       = next $! x:ys
                                        | otherwise = next $! ys
                     where next = filter3' p xs
                   filter3' _ []     ys             = reverse ys
               in filter3' p xs []

Заметим, однако, что это не сработает на бесконечных списках (хотя все остальные реализации будут работать), благодаря reverse, поэтому мы сделаем ее строгой с помощью $! . (Я думаю, что сделал все правильно - возможно, я использовал не ту переменную. Но я думаю, что все же правильно.)

Все эти реализации похожи на вашу. Есть, конечно, и другие. Одна основана на foldr:

filter4 :: (a -> Bool) -> [a] -> [a]
filter4 p = let check x | p x       = (x :)
                        | otherwise = id
            in foldr check []

Здесь мы используем преимущества стиля point-free; поскольку xs будет последним аргументом и filter4, и foldr check [], мы можем его убрать, и то же самое с последним аргументом check.

Можно также воспользоваться монадой списка:

import Control.Monad
filter5 :: MonadPlus m => (a -> Bool) -> m a -> m a
filter5 p xs = do x <- xs
                  guard $ p x
                  return x

Монада списка представляет недетерминизм. Вы выбираете элемент x из xs, убеждаетесь, что он удовлетворяет p, и возвращаете его, если удовлетворяет. Затем все эти результаты собираются вместе. Но обратите внимание, что теперь это более общий метод; он работает для любой MonadPlus (монада, которая также является моноидом, то есть имеет ассоциативную бинарную операцию mplus-++ для списков и элемент тождества mzero-[] для списков), например [] или Maybe. Например, filter5 even $ Just 1 == Nothing, а filter5 even $ Just 2 == Just 2.

Мы также можем адаптировать foldr-версию, чтобы получить другую общую сигнатуру типа:

import Control.Monad
import qualified Data.Foldable as F
import qualified Data.Monoid   as M
filter6 :: (F.Foldable f, MonadPlus m, M.Monoid (m a))
        => (a -> Bool) -> f a -> m a
filter6 p = let check x | p x       = return x
                        | otherwise = mzero
            in F.foldMap check

Модуль Data.Foldable предоставляет класс типа Foldable, который представляет любую структуру, которую можно сложитькак список (помещая результат в общий моноид вместо этого. ) Наш фильтр требует MonadPlus ограничения на результат, так что мы можем написать return x. Функция foldMap требует функции, которая преобразует все в элементы моноида, а затем конкатенирует их вместе. Несоответствие между f a слева и m a справа означает, что вы можете, например, filter6 a Maybe и получить обратно список.

Я уверен, что есть (много!) других реализаций filter, но это 6, которые я смог придумать относительно быстро. Итак, какая из них мне нравится больше? Это выбор между простым filter2 и foldr-базированным filter4. А filter5 хорош своей общей сигнатурой типов. (Не думаю, что мне когда-либо требовалась подпись типа, подобная той, что есть у filter6). Тот факт, что filter2 используется в GHC, является плюсом, но GHC также использует некоторые забавные правила перезаписи, так что для меня не очевидно, что он лучше без них. Лично я вероятно выбрал бы filter4 (или filter5, если бы мне нужна была универсальность), но filter2 определенно подойдет.