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

Question

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

myfilter :: (a -> Bool) -> [a] -> [a]
myfilter f (x:xs) = if f x
    then x : myfilter f xs
    else myfilter f xs
myfilter _ [] = []

Спасибо

Answer 1

Самый простой способ убрать вашу реализацию - это использовать guard . Вместо pattern = value вы можете написать write 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; они разделяются всем, у кого есть общий шаблон, даже если у него другая защита:

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

(Эта реализация используется GHCs 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 []

Мы используем стиль без очков здесь; поскольку 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, который представляет любую структуру, которую можно fold редактировать как список (вместо этого помещая результат в общий Monoid.) Наш filter также требует ограничения MonadPlus на результат, чтобы мы могли написать return x. Для функции foldMap требуется функция, которая преобразует все в элементы Monoid, а затем объединяет их все вместе. Несоответствие между f a слева и m a справа означает, что вы можете, например, filter6 a Maybe и получить список.

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

Answer 2

Как насчет понимания списка?

myfilter f xs = [x | x <- xs, f x]

Answer 3

Вы можете хотя бы немного высушить его, вытянув этот общий myfilter f xs код:

myfilter :: (a -> Bool) -> [a] -> [a]
myfilter f (x:xs) = if f x
    then x : rest
    else rest
        where rest = myfilter f xs
myfilter _ [] = []

Answer 4

Для сравнения, вот реализация Википедии:

myfilter :: (a -> Bool) -> [a] -> [a]
myfilter _ []                 = []
myfilter f (x:xs) | f x       = x : myfilter f xs
                  | otherwise = myfilter f xs

Answer 5

В Haskell большую часть времени вы можете (и должны) использовать охранников вместо if-then-else:

myfilter :: (a -> Bool) -> [a] -> [a]
myfilter f (x:xs)
   | f x       = x : myfilter f xs
   | otherwise = myfilter f xs
myfilter _ [] = []

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