3

我目前正在阅读 John Hughes 的论文Programming with Arrows，我已经被第 20 页第 2.5 节的第一个练习难住了。

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

举了一个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：listcaselikemap和应用 predicate 的结果p。它开始于map，检查列表并使用返回一个 Either 值listcase。在应用空列表的情况下g，否则右侧的所有内容|||都应用于 type 的值，分别(a,[a])包含head和tail。该h函数首先应用，它应用谓词同时保留head，返回一个类型的值((Bool, head),tail)。这被传递给，它根据值(uncurry helper)决定是否保留。它将结果作为headBoolEither值，以便我们可以将选择方法(|||)应用于它。这个值被传递给下一个选择：(j ||| (filterA p))这样，如果谓词被持有Truethenj将应用于包含headand的对tail。被head过滤，id而filter p被应用于tail。两个结果都成对返回。arr (uncurry (:))然后使用like协调这对map。否则，将单独tail传递给。filterA p

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

4

2 回答 2

3

抱歉，我没有完全遵循您的逻辑，但让我们看看非箭头代码的作用。它

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

listcase[实现前 2 个任务的] 函数看起来不错，但请记住您正在返回一个列表，所以不妨返回它而不是重新unit映射 through const []。

你有隐藏在最后两个案例中的第三个子弹的递归代码，而我直接公开它，但这没关系。

对于最后的合并，您使用 a 编写它|||，但由于您不需要在目标类别中组合任何其他箭头，您不妨只提升一个函数来完成所有工作。在我下面的代码中，就是rejoin.

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

***当然，用, &&&, |||,first等来清楚地表达你的想法需要时间。

一点批评。

  • 确保您正在实现他们要求的功能！如果您只是采用原始函数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声明中时，您需要告诉它arrforfilterRest与 for filterA（类型变量范围）相同，因此请使用forall arr a.上述。

于 2011-07-19T02:09:26.460 回答
2

这里稍微简化一下：

test :: Arrow a => (b -> Bool) -> a b ([b] -> [b])
test p = arr $ \b -> if p b then (b:) else id
         
filterA :: Arrow a => (b -> Bool) -> a [b] [b]
filterA p = f >>> (g ||| h)
  where f = arr listcase
        g = arr id
        h = (test p *** filterA p) >>> (arr (uncurry ($)))

filterA' :: Arrow a => a b Bool -> a [b] [b]
filterA' p = f >>> (g ||| h)
  where f = arr listcase
        g = arr id
        h = (i *** filterA p) >>> (arr (uncurry ($)))
        i = proc x -> do 
              b <- p -< x
              returnA -< if b then (x:) else id
于 2011-07-19T02:20:24.237 回答