Самый простой способ обметать ваша реализация заключается в использовании guards. Вместо 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
; они разделяют все, что разделяет общую картину, даже если она имеет другой охранник: (. Эта реализация является один used by GHCs Prelude)
filter2 :: (a -> Bool) -> [a] -> [a]
filter2 p (x:xs) | p x = x : xs'
| otherwise = xs'
where xs' = filter2 p xs
filter2 _ [] = []
Теперь ни один из них хвостовой рекурсией. Это может быть невыгодно, но это делает функцию ленивой. Если мы хотим хвостовую рекурсию версию, мы могли бы написать
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 module обеспечивает класс Foldable
типа, который представляет собой любую структуру, которая может быть fold
редактора как список (размещение результат в общем Monoid
вместо.) Наш filter
требует также MonadPlus
ограничений на результат, чтобы мы могли написать return x
. Функция foldMap
требует функции, которая преобразует все элементы в элементы Monoid
, а затем объединяет их все вместе. Несоответствие между f a
слева и m a
справа означает, что вы могли бы, например,a Maybe
и получить список.
Я уверен, что существует (много!) Других реализаций filter
, но это 6, о которых я мог думать относительно быстро. Теперь, какой из них мне больше всего нравится? Это провал между простым filter2
и foldr
- filter4
. И filter5
хорош для своей общей сигнатуры типа. (Я не думаю, что мне когда-либо нужна подпись типа, например, filter6
.) Тот факт, что filter2
используется GHC, является плюсом, но GHC также использует некоторые фанковые правила перезаписи, поэтому для меня не очевидно, что он превосходит без них. Лично я бы , вероятно, перешел с filter4
(или filter5
, если мне нужна была общая), но filter2
определенно отлично.
Я не считаю это уродливым. –