编写此函数（通常称为 filterA）的惯用方法是什么？

Question

我正在学习 this 课程。

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

但对我来说有点"round about"的感觉，想不出更直接的方法。

注意：我已经扩展到 x, y, z 因为它使（对我而言）更容易了解正在发生的事情，虽然我意识到我可以在一行中表达所有内容，但我不认为更 'direct' 因此不是我问题的答案。

注意 2：本课程似乎是从基础部分构建通用类型类。我们从 List 的自定义实现开始，然后是 Functor，现在是 Applicative，所以我只能使用这些类中的概念。我还不能使用 Monad 中的任何内容。

Answer 1

我的第一个想法是从普通的 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 让我们分别从 f x 和 filtering f xs 本地提取 Bool 和 List a；或者更准确地说，我们已经将 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

Answer 2

这里是 foldr 的实现（使用 base 类型和函数编写）。我相当确定它等同于 .

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 是 pointfree-friendly 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)

（Data.Maybe 中的 bool Nothing (Just x) 和 catMaybes 而不是 bool [] [x] 和 concat 也可以。）

请注意，此解决方案需要额外遍历列表，因为 traverse 不够强大，无法实施过滤。这就是为什么 filter、catMaybes、filterA 和朋友需要 different classes 才能被推广。

编写此函数（通常称为 filterA）的惯用方法是什么？

What is the idiomatic way to write this function (which might normally be called filterA)?

haskell

applicative