CODEWITHSUNDEEP
haskellarrow-abstraction
tolUene
tolUene

Reputation: 584

Control.Arrow: trying to write a filterA function

I am trying to write a filterA :: (ArrowChoice arr) => arr a Bool -> arr [a] [a] function that removes every element from a list for which f :: arr a Bool returns False. This is what I have so far

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

Now this works when testing it with (->) a Arrows, like this:

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

It doesn't work however, for Kleisli Arrows like

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

And when adding a type signature filterA :: (Arrow arr) => arr a Bool -> arr [a] [a] or filterA :: (ArrowChoice arr) => arr a Bool -> arr [a] [a], it throws this error: 

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)

I do not understand why. Did I miss something?

Edit: @jaket's comment worked (I guess that was kinda stupid) but the type signature still doesn't match. I also updated the code to be more compact (still getting the same error though) 

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 infers the type as filterA :: (a -> Bool) -> [a] -> [a], by the way.

Upvotes: 1

Views: 164

Answers (3)

Petr
Petr

Reputation: 63399

Just to complement the other answers: Using the Arrow syntax (see also the GHC manual, Chapter Arrow notation) you can write function somewhat more readable:

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

The result translated internally to the arrow notation will be probably somewhat less concise, but hopefully the compiler will optimize for you.

Upvotes: 1

Daniel Martin
Daniel Martin

Reputation: 23558

Your problem is that you're trying to do the recursion inside the function definition that you wrap with arr, and you call filterA f as though it were a function in this line:

                x : (filterA f xs)

That only works if the arrow type is (->), which is what one of the type errors is telling you.

Instead, you need to do the recursion at the arrow level, as in:

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

(which does compile)

Your runKleisli example is a bit confused, you meant to say:

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

or

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

That's straight from looking at the types.

Upvotes: 1

jaket
jaket

Reputation: 9341

As mentioned in my comment:

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

Next you need to lift f :: a -> b into an arrow arr a b 

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

in your function:

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

Upvotes: 0

Related Questions