Control.Arrow：尝试编写一个filterA函数

Question

我正在尝试编写一个

filterA :: (ArrowChoice arr) => arr a Bool -> arr [a] [a]

函数，从列表中删除

f :: arr a Bool

返回

False

的每个元素。这就是我目前所拥有的

listcase [] = Left ()
listcase (x:xs) = Right (x, xs)

filterA f = arr listcase >>>
            arr (const []) ||| (first (f &&& arr id) >>>
            arr (\((b,x),xs) -> if b then
                x : (filterA f xs)
                else filterA f xs
            ))

现在，当使用

(->) a

箭头进行测试时，这是有效的，如下所示：

λ> filterA (== 8) [8,9]
[8]

但是，对于 Kleisli Arrows 这样的

，它不起作用

λ> runKleisli (Kleisli $ filterA (== 8)) (return [8,9] :: [IO Int])

<interactive>:160:47:
    Couldn't match expected type `IO Int' with actual type `[t0]'
    In the first argument of `return', namely `[8, 9]'
    In the second argument of `runKleisli', namely
      `(return [8, 9] :: [IO Int])'
    In the expression:
      runKleisli (Kleisli $ filterA (== 8)) (return [8, 9] :: [IO Int])

当添加类型签名

filterA :: (Arrow arr) => arr a Bool -> arr [a] [a]

或

filterA :: (ArrowChoice arr) => arr a Bool -> arr [a] [a]

时，它会抛出此错误：

arrows.hs:11:22:
    Could not deduce (arr ~ (->))
    from the context (Arrow arr)
      bound by the type signature for
                 filterA :: Arrow arr => arr a Bool -> arr [a] [a]
      at arrows.hs:7:12-51
      `arr' is a rigid type variable bound by
            the type signature for
              filterA :: Arrow arr => arr a Bool -> arr [a] [a]
            at arrows.hs:7:12
    Expected type: [a] -> [a]
      Actual type: arr [a] [a]
    The function `filterA' is applied to two arguments,
    but its type `arr a Bool -> arr [a] [a]' has only one
    In the second argument of `(:)', namely `(filterA f xs)'
    In the expression: x : (filterA f xs)

我不明白为什么。我错过了什么吗？

编辑： @jaket 的评论有效（我猜这有点愚蠢），但类型签名仍然不匹配。 我还更新了代码以使其更加紧凑（尽管仍然出现相同的错误）

filterA f = arr listcase >>>
            arr (const []) ||| (arr toEither >>>
            (filterA f) ||| (second (filterA f) >>> arr uncurry (:)))
  where toEither (x, xs) = if f x then Right (x, xs) else Left xs

顺便说一句，GHC 将类型推断为

filterA :: (a -> Bool) -> [a] -> [a]

。

Answer 1

你的问题是你试图在用

arr

包装的函数定义内进行递归，并且你调用

filterA f

就好像它是这一行中的函数一样：

                x : (filterA f xs)

仅当箭头类型为

(->)

时才有效，这是类型错误之一告诉您的内容。

相反，您需要在箭头级别进行递归，如下所示：

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

filterA :: (ArrowChoice arr) => arr a Bool -> arr [a] [a]
filterA f = listcase ^>>
            arr (const []) ||| ((f &&& arr id) *** filterA f >>^
                                (\((b, x), xs) -> if b then x:xs else xs))

（确实可以编译）

你的

runKleisli

的例子有点混乱，你的意思是：

runKleisli (filterA $ Kleisli $ return . (== 8)) [8,9]

或

runKleisli (filterA $ arr (== 8)) [8,9] :: IO [Int]

这是直接从类型来看的。

Answer 2

只是为了补充其他答案：使用箭头语法（另请参阅 GHC 手册，章节箭头表示法），您可以编写更具可读性的函数：

{-# LANGUAGE Arrows #-}

import Control.Arrow

filterA :: (ArrowChoice arr) => arr a Bool -> arr [a] [a]
filterA f = farr
  where
    farr = proc xs ->
            case xs of
                []       -> returnA -< []
                (x:xs')  -> do
                    b   <- f    -< x
                    ys' <- farr -< xs'
                    returnA -< if b then x : ys' else ys'

内部转换为箭头符号的结果可能会不太简洁，但希望编译器能够为您进行优化。

Answer 3

正如我的评论中提到的：

runKleisli (Kleisli $ filterA (== 8)) [8, 9]

接下来您需要将

f :: a -> b

提升为箭头

arr a b

(first (arr f &&& arr id)
        ^^^

在你的函数中：

filterA :: ArrowChoice arr => (a -> Bool) -> arr [a] [a]
filterA f = arr listcase >>>
            arr (const []) ||| (first (f &&& arr id) >>>
            arr (\((b,x),xs) -> if b then
                x : (filterA f xs)
                else filterA f xs
            ))