Haskell Control.Arrow: 尝试编写 filterA 函数

Question

我正在尝试编写一个 filterA :: (ArrowChoice arr) => arr a Bool -> arr [a] [a] 函数，用于从 f :: arr a Bool returns 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

正如我在评论中提到的：

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
            ))

Answer 2

你的问题是你试图在你用 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 3

只是为了补充其他答案：使用 Arrow syntax (see also the GHC manual, Chapter Arrow notation) 您可以编写更具可读性的函数：

{-# 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'

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

Haskell Control.Arrow: 尝试编写 filterA 函数

Haskell Control.Arrow: trying to write a filterA function

haskell

arrows