Я прохожу курс это.
Существует раздел для Applicative
, и меня просят реализовать функцию со следующим поведением и типом
-- | Filter a list with a predicate that produces an effect.
--
-- >>> filtering (ExactlyOne . even) (4 :. 5 :. 6 :. Nil)
-- ExactlyOne [4,6]
--
-- >>> filtering (\a -> if a > 13 then Empty else Full (a <= 7)) (4 :. 5 :. 6 :. Nil)
-- Full [4,5,6]
--
-- >>> filtering (\a -> if a > 13 then Empty else Full (a <= 7)) (4 :. 5 :. 6 :. 7 :. 8 :. 9 :. Nil)
-- Full [4,5,6,7]
--
-- >>> filtering (\a -> if a > 13 then Empty else Full (a <= 7)) (4 :. 5 :. 6 :. 13 :. 14 :. Nil)
-- Empty
--
-- >>> filtering (>) (4 :. 5 :. 6 :. 7 :. 8 :. 9 :. 10 :. 11 :. 12 :. Nil) 8
-- [9,10,11,12]
--
-- >>> filtering (const $ True :. True :. Nil) (1 :. 2 :. 3 :. Nil)
-- [[1,2,3],[1,2,3],[1,2,3],[1,2,3],[1,2,3],[1,2,3],[1,2,3],[1,2,3]]
filtering :: Applicative f => (a -> f Bool) -> List a -> f (List a)
Я придумал следующую реализацию, которая удовлетворяет всем требованиям
filtering f as =
let x = sequence (f `map` as)
y = zip as <$> x
z = filter snd <$> y
in map fst <$> z
но мне это кажется немного "круглым", и я не могу придумать более прямой способ сделать это.
Примечание: я расширился до x, y, z
, потому что так (мне) легче следить за тем, что происходит, и хотя я понимаю, что мог бы выразить все это в одной строке, я не считаю это более «прямым» и, следовательно, не ответ на мой вопрос.
Примечание 2: Этот курс, похоже, строит классы общих типов из фундаментальных частей. Мы начали с пользовательской реализации List
, затем Functor
и теперь Applicative
, поэтому я могу использовать концепции только из этих классов. Я пока не могу ничего использовать из Monad
.
Моей первой идеей было бы начать с простого filter
:
filter :: (a -> Bool) -> List a -> List a
filter _ Nil = Nil
filter f (x :. xs) =
let b = f x
ys = filter f xs
in
if b then x :. ys else ys
... и попробуйте расширить его до Applicative
:
filtering :: (Applicative f) => (a -> f Bool) -> List a -> f (List a)
filtering _ Nil = pure Nil
filtering f (x :. xs) =
let b = f x
ys = filtering f xs
in
if b then x :. ys else ys
В этой попытке есть две проблемы: f x
— это f Bool
, а не Bool
, поэтому if b then ...
— это ошибка типа, и filtering f xs
— это f (List a)
, а не List a
, поэтому x :. ys
— это ошибка типа.
Мы можем исправить эти проблемы, используя lift2 :: (Applicative f) => (a -> b -> c) -> f a -> f b -> f c
:
filtering f (x :. xs) =
lift2 (\b ys -> if b then x :. ys else ys) (f x) (filtering f xs)
lift2
позволяет локально извлекать Bool
и List a
из f x
и filtering f xs
соответственно; или, точнее, мы обернули наши if ... then ... else
вычисления в функцию, которая lift2
затем вставляется в f
.
В качестве альтернативы мы могли бы использовать <$>
и <*>
напрямую:
filtering f (x :. xs) =
(\b ys -> if b then x :. ys else ys) <$> f x <*> filtering f xs
Или напишите нашу вспомогательную функцию немного иначе:
filtering f (x :. xs) =
(\b -> if b then (x :.) else id) <$> f x <*> filtering f xs
Отличный ответ! Для всех тех, кто читает это, но не знаком с этим курсом, оператор (:.) в пользовательском типе списка эквивалентен оператору (:) в стандартном типе списка.
@ChechyLevas А lift2
это liftA2
из Control.Applicative
.
Вот реализация с точки зрения foldr
(и написанная с использованием типов и функций основание). Я почти уверен, что это эквивалентно раствор мельпомены.
import Control.Applicative (liftA2)
import Data.Bool (bool)
filterA :: Applicative f => (a -> f Bool) -> [a] -> f [a]
filterA f = foldr (\x xs -> liftA2 (++) (bool [] [x] <$> f x) xs) (pure [])
Стоит отметить несколько деталей:
bool y x b
— это сленговое обозначение if b then x else y
, удобное для использования без точек.
Использование (++)
вместо (:)
для добавления элементов — это нормально, поскольку мы делаем это в начале списка.
xs
не является буквально списком — он имеет тип f [a]
.
Демонстрация:
GHCi> filterA (\x -> print x *> pure (x > 5)) [1..10]
1
2
3
4
5
6
7
8
9
10
[6,7,8,9,10]
Вот другой вариант, вдохновленный вашим исходным решением (обратите внимание, что sequence (map f xs)
совпадает с traverse f xs
):
filterA :: Applicative f => (a -> f Bool) -> [a] -> f [a]
filterA f = fmap concat . traverse (\x -> bool [] [x] <$> f x)
(bool Nothing (Just x)
и catMaybes
из Data.Maybe
вместо bool [] [x]
и concat
также будут работать.)
Обратите внимание, что для этого решения требуется дополнительный проход по спискам, потому что traverse
недостаточно силен для реализации фильтрации. Вот почему filter
, catMaybes
, filterA
и друзья требуют разные классы, если они должны быть обобщены.
Примечание: библиотека увядший действительно называет ее (обобщенная версия)
filterA
.