haskell - 如何定义箭头的过滤函数？

Question

我正在阅读这篇论文 Programming with Arrows作者:约翰·休斯我已经被第 20 页第 2.5 节中的第一个练习难住了。

我们可以使用 Arrow 和 ArrowChoice 类型类，以及函数、流函数的实例[a] -> [b] 和通过 Kleisli 类型的一元函数 a -> m b。

给出了 mapA 示例:

mapA f = arr listcase >>>
         arr (const []) ||| (f *** mapA >>> arr (uncurry (:)))

这是一个尝试:

listcase :: [a] -> (Either () (a,[a]))
listcase [] = Left ()
listcase (x:xs) = Right (x,xs)

helper :: (Bool,a) -> [a] -> Either (a,[a]) [a]
helper (True,x)  y = Left (x,y)
helper (False,x) y = Right y

test :: Arrow a => (b -> Bool) -> a (b,c) ((Bool,b), c)
test p = first (arr p &&& arr id)

filterA :: Arrow a => (b -> Bool) -> a [b] [c]
filterA p = f >>> (g ||| (h >>> (j ||| (filterA p))))
   where f = arr listcase
         g = arr (const [])
         h = test p >>> (uncurry helper)
         j = (arr id *** (filterA p)) >>> (arr (uncurry (:)))

这种徒劳的尝试背后的(暴力)理由如下:filterA 有两种选择:listcase(如 map)，以及应用谓词 p 的结果>。它像 map 一样开始，检查列表并使用 listcase 返回 Either 值。如果是空列表，则应用 g，否则 ||| 右侧的所有内容都将应用于 (a,[a] 类型的值)，分别包含head和tail。首先应用 h 函数，该函数在保留 head 的同时应用谓词，返回 ((Bool, head),tail) 类型的值>。它被传递给(uncurry helper)，它根据Bool值决定是否保留head。它以 Either 值的形式返回结果，以便我们可以对其应用选择方法 (|||)。该值将传递给下一个选择:(j ||| (filterA p))，这样如果谓词保持 True，则 j 为应用于包含 head 和 tail 的对。 head 通过使用 id 进行过滤，而 filter p 则应用于 tail。两个结果均作为一对返回。然后像 map 一样使用 arr (uncurry (:)) 来协调这一对。否则tail将单独传递给filterA p。

我怀疑这是否像我想象的那么困难，我想我错过了一些非常明显的东西。

Answer 1

抱歉，我不太明白您的逻辑，但让我们看看非箭头代码的作用。它

• 检查列表是否为空，如果是则返回
• 否则，将列表的头部拉出，调用元素x
• 递归列表的其余部分，调用结果ys
• 如果谓词 p 在头部为真，那么我们将 x 附加到 ys。
• 否则，我们返回ys

listcase 函数[用于实现前 2 个任务]看起来不错，但请记住您正在返回一个列表，因此最好返回该列表而不是 unit 和通过 const [] 重新映射。

您将第三个项目符号的递归代码隐藏在最后两个案例中，而我直接公开它，但这没关系。

对于最后一次合并，您可以使用 ||| 编写它，但由于您不需要在目标类别中编写任何其他箭头，因此您不妨将一个函数提升为做所有的工作。在我下面的代码中，这是重新加入。

filterA :: forall arr a. ArrowChoice arr => arr a Bool -> arr [a] [a]
filterA p = arr lstcase >>> (filterRest ||| id) where
    -- left if has a head, right otherwise
    lstcase :: [a] -> (Either (a, [a]) [a])
    lstcase (x:xs) = Left (x, xs)
    lstcase [] = Right []

    -- if we got a head, then
    --     for the head ("first" in code), map this to itself and p's result on it
    --     recurse on the rest of the list ("second" part)
    --     append the element to the recursion result if p's result is true
    filterRest :: arr (a, [a]) [a]
    filterRest = (first (id &&& p) >>> second (filterA p) >>> arr rejoin)

    rejoin :: ((a, Bool), [a]) -> [a]
    rejoin ((x, True), rest) = x:rest
    rejoin ((x, False), rest) = rest

当然，用***、&&&、|||、等方式清楚地表达你的想法需要时间首先，等等

一点批评。

• 确保您正在实现他们要求的功能!如果您只采用原始函数p，那么您不妨声明filterA = arr filter。你确实想要一个抬起的箭头p。也就是说，更改只需键入 p 而不是 arr p，这样您的代码就有了正确的想法。
• (uncurry helper) 不是箭头空间中的东西，它只是一个原始函数。

在开发这些东西时，我通常会编写一个框架，并声明类型。这可以帮助我弄清楚发生了什么事。例如，我开始于

filterA :: ArrowChoice arr => arr a Bool -> arr [a] [a]
filterA p = arr lstcase >>> (filterRest ||| id) where
    -- left if has a head, right otherwise
    lstcase :: [a] -> (Either (a, [a]) [a])
    lstcase = undefined

    filterRest :: arr (a, [a]) [a]
    filterRest = undefined

但是，当您将 fa 添加到 filterRest 声明中时，您需要告诉它 arr 对于 filterRest与 filterA 相同(类型变量范围)，因此请使用上面的 forall arr a.。