Implement 'filtering'

The NICTA Haskell Course presents the following function to implement on List:

data List t =
  Nil
  | t :. List t
  deriving (Eq, Ord)

And the function:

filtering :: Applicative f => (a -> f Bool) -> List a -> f (List a)
filtering _ Nil       = pure Nil
filtering f (x :. xs) = (++)  ((\y -> case y of True -> x :. Nil
                                                   False -> Nil)  f x)    
                                                         filtering f xs

Please review this implementation.

Taking a look at the course materials, I think you've missed the point. Applicative.hs has you define sequence :: Applicative f => List (f a) -> f (List a) before filtering, and looking briefly through the suggested progression it appears as though things are ordered such that there is always a “clever” answer to be built out of the things you've previously implemented.

That said, this question then gets both easier and harder. Easier because there is purpose built machinery to manipulate e.g. that weird non-Prelude List type. Harder because this isn't really standard Haskell anymore since all of our usual functions and typeclasses have been replaced by their evil twins.

I think the intended answer is that you map the predicate function over the list you're given, then use the sequence function you defined earlier to switch List (f Bool) to f (List Bool), then... I dunno. This is mirror world.

Here's how you'd write this function given the types from regular old base.

import Control.Applicative
import Data.Traversable

filtering :: (Applicative f) => (a -> f Bool) -> [a] -> f [a]
filtering f xs = (xs `filterBy`)  (sequenceA . map f $ xs)
    where
        filterBy :: [a] -> [Bool] -> [a]
        filterBy xs ps = map fst . filter snd $ zip xs ps

I assume the version you're looking for will be identical, but using sequence instead of sequenceA.

I think there is probably an even more clever solution—and I suspect it uses the reader instance (((->) a)) and a lifted filter—but I sure can't tease it out. Comments and edits welcome.

StackExchange Code Review Q#85262, answer score: 2