Filtering Applicatives

Question

I am doing NICTA Haskell course and stuck on the last part of Applicative, here is my progress.

Basically, we are to filter a List with a predicate that produce a List in an Applicative context.

filtering :: Applicative f => (a -> f Bool) -> List a -> f (List a)
filtering _ Nil = pure Nil
filtering f (x :. rest) = 
        let whole = lift2 (:.) (pure x) (filtering f rest) in
        lift2 filter (const <$> f x) whole

So whole here is the full unfiltered list, so I lift a filter, and the added const in (const <$> f x) is to satisfy the (a -> Bool) requirement in filter.

All is well and it is compiled successfully, but it fails one of the test case so something must be wrong here.

For instance, filtering (Id . even) [4,5,6] only return Id [4] as opposed to Id [4,6] (Id is just a container and is an Applicative.)

Do I make any mistake somewhere?

Answer 1

The problem here is (const <$> f x). That function is going to be used to examine the whole list, but it's only going to provide the result of f on the current x. That means when it's working on the [5,6] sublist, it's going to essentially be filter (const False) [5,6], which results in an empty list.

You can't call on filter to do this for you, because it's just not the right shape. Something like this will always happen. Instead, just focus on including the current element or not, and let recursion handle the rest of the list properly. (I'm trying not to say more because the goal of doing the course is to figure it out for yourself, of course.)

Answer 2

I'm confused by what you think "the full unfiltered list" is needed for, and I think so are you. The full unfiltered list it x :. rest, you already have that!

Apparently, you mean "the whole result as it would be if the predicate always yielded True... but that doesn't make any sense, because you'd basically predict that it would always yield True.

What you need to consider, instead of this whole thing, is two applicative-wrapped values: the result of the predicate at the head – that's just f x :: f Bool. And, as the recursion, the filtered rest of the list, filtering f rest :: f (List a).

Now, as you've apparently noticed liftA2 is often the easiest way to combine two Applicative-wrapped values (though <*> actually tends to make for neater code). Recall

liftA2 :: (a->b->c) -> f a -> f b -> f c

In this case,

liftA2 :: (Bool->List a->List a) -> f Bool -> f (List a) -> f (List a)

So you need a function Bool->List a->List a, which prepends x if the boolean is true and otherwise leaves the lists as it is. Well, it shouldn't be a problem to define that in a local where block.