Implementing filter using HoF in Haskell

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 pre开发者_运维技巧served order. The trick is to do this using only higher order functions (HoF), no recursion, no comprehensions, and of course no filter.

---

You can express filter in terms of foldr:

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

---

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

---

You're obviously doing this to learn, so let me show you something cool. First up, to refresh our minds, the type of filter is:

filter :: (a -> Bool) -> [a] -> [a]

The interesting part of this is the last bit [a] -> [a]. It breaks down one list and it builds up a new list.

Recursive patterns are so common in Haskell (and other functional languages) that people have come up with names for some of these patterns. The simplest are the catamorphism and it's dual the anamorphism. I'll show you how this relates to your immediate problem at the end.

Fixed points

Prerequisite knowledge FTW!

What is the type of Nothing? Firing up GHCI, it says Nothing :: Maybe a and I wouldn't disagree. What about Just Nothing? Using GHCI again, it says Just Nothing :: Maybe (Maybe a) which is also perfectly valid, but what about the value that this a Nothing embedded within an arbitrary number, or even an infinite number, of Justs. ie, what is the type of this value:

foo = Just foo

Haskell doesn't actually allow such a definition, but with a slight tweak we can make such a type:

data Fix a = In { out :: a (Fix a) }

just :: Fix Maybe -> Fix Maybe
just = In . Just

nothing :: Fix Maybe
nothing = In Nothing

foo :: Fix Maybe
foo = just foo

Wooh, close enough! Using the same type, we can create arbitrarily nested nothings:

bar :: Fix Maybe
bar = just (just (just (just nothing)))

Aside: Peano arithmetic anyone?

fromInt :: Int -> Fix Maybe
fromInt 0 = nothing
fromInt n = just $ fromInt (n - 1)

toInt :: Fix Maybe -> Int
toInt (In Nothing) = 0
toInt (In (Just x)) = 1 + toInt x

This Fix Maybe type is a bit boring. Here's a type whose fixed-point is a list:

data L a r = Nil | Cons a r
type List a = Fix (L a)

This data type is going to be instrumental in demonstrating some recursion patterns.

Useful Fact: The r in Cons a r is called a recursion site

Catamorphism

A catamorphism is an operation that breaks a structure down. The catamorphism for lists is better known as a fold. Now the type of a catamorphism can be expressed like so:

cata :: (T a -> a) -> Fix T -> a

Which can be written equivalently as:

cata :: (T a -> a) -> (Fix T -> a)

Or in English as:

You give me a function that reduces a data type to a value and I'll give you a function that reduces it's fixed point to a value.

Actually, I lied, the type is really:

cata :: Functor T => (T a -> a) -> Fix T -> a

But the principle is the same. Notice, T is only parameterized over the type of the recursion sites, so the Functor part is really saying "Give me a way of manipulating all the recursion sites".

Then cata can be defined as:

cata f = f . fmap (cata f) . out

This is quite dense, let me elaborate. It's a three step process:

• First, We're given a Fix t, which is a difficult type to play with, we can make it easier by applying out (from the definition of Fix) giving us a t (Fix t).
• Next we want to convert the t (Fix t) into a t a, which we can do, via wishful thinking, using fmap (cata f); we're assuming we'll be able to construct cata.
• Lastly, we have a t a and we want an a, so we just use f.

Earlier I said that the catamorphism for a list is called fold, but cata doesn't look much like a fold at the moment. Let's define a fold function in terms of cata.

Recapping, the list type is:

data L a r = Nil | Cons a r
type List a = Fix (L a)

This needs to be a functor to be useful, which is straight forward:

instance Functor (L a) where
  fmap _ Nil = Nil
  fmap f (Cons a r) = Cons a (f r)

So specializing cata we get:

cata :: (L x a -> a) -> List x -> a

We're practically there:

construct :: (a -> b -> b) -> b -> L a b -> b
construct _ x (In Nil) = x
construct f _ (In (Cons e n)) = f e n

fold :: (a -> b -> b) -> b -> List a -> b
fold f m = cata (construct f m)

OK, catamorphisms break data structures down one layer at a time.

Anamorphisms

Anamorphisms over lists are unfolds. Unfolds are less commonly known than there fold duals, they have a type like:

unfoldr :: (b -> Maybe (a, b)) -> b -> [a]

As you can see anamorphisms build up data structures. Here's the more general type:

ana :: Functor a => (a -> t a) -> a -> Fix t

This should immediately look quite familiar. The definition is also reminiscent of the catamorphism.

ana f = In . fmap (ana f) . f

It's just the same thing reversed. Constructing unfold from ana is even simpler than constructing fold from cata. Notice the structural similarity between Maybe (a, b) and L a b.

convert :: Maybe (a, b) -> L a b
convert Nothing = Nil
convert (Just (a, b)) = Cons a b

unfold :: (b -> Maybe (a, b)) -> b -> List a
unfold f = ana (convert . f)

Putting theory into practice

filter is an interesting function in that it can be constructed from a catamorphism or from an anamorphism. The other answers to this question (to date) have also used catamorphisms, but I'll define it both ways:

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

filter p =
  unfoldr (f p)
 where
  f _ [] =
    Nothing
  f p (x:xs) =
    if p x then
      Just (x, xs)
    else
      f p xs

Yes, yes, I know I used a recursive definition in the unfold version, but forgive me, I taught you lots of theory and anyway filter isn't recursive.

---

I'd suggest you look at foldr.

---

Well, are ifs and empty list allowed?

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

---

For a list of Integers

filter2::(Int->Bool)->[Int]->[Int]
filter2 f []=[]
filter2 f (hd:tl) = if f hd then hd:filter2 f tl
                else filter2 f tl

---

I couldn't resist answering this question in another way, this time with no recursion at all.

-- This is a type hack to allow the y combinator to be represented
newtype Mu a = Roll { unroll :: Mu a -> a }
-- This is the y combinator
fix f = (\x -> f ((unroll x) x))(Roll (\x -> f ((unroll x) x)))

filter :: (a -> Bool) -> [a] -> [a]
filter =
  fix filter'
 where
  -- This is essentially a recursive definition of filter
  -- except instead of calling itself, it calls f, a function that's passed in
  filter' _ _ [] = []
  filter' f p (x:xs) =
    if p x then
      (x:f p xs)
    else
      f p xs