Implementing filter using HoF in Haskell

Question

I'm trying to write a function that takes a predicate f and a list and returns a list consisting of all items that satisfy f with preserved order. The trick is to do this using only higher order functions (HoF), no recursion, no comprehensions, and of course no filter.

Answer 1

I'd suggest you look at foldr.

Answer 2

I think you can use map this way:

filter' :: (a -> Bool) -> [a] -> [a]
filter' p xs = concat (map (\x -> if (p x) then [x] else []) xs)

You see? Convert the list in a list of lists, where if the element you want doesn't pass p, it turns to an empty list

filter' (> 1) [1 , 2, 3 ] would be: concat [ [], [2], [3]] = [2,3]

In prelude there is concatMap that makes the code simplier :P

the code should look like:

filter' :: (a -> Bool) -> [a] -> [a]
filter' p xs = concatMap (\x -> if (p x) then [x] else []) xs

using foldr, as suggested by sclv, can be done with something like this:

filter'' :: (a -> Bool) -> [a] -> [a]
filter'' p xs = foldr (\x y -> if p x then (x:y) else y) [] xs

Answer 3

Well, are ifs and empty list allowed?

filter = (\f -> (>>= (\x -> if (f x) then return x else [])))

Answer 4

You can express filter in terms of foldr:

filter p = foldr (\x xs-> if p x then x:xs else xs) []