List filter using an anamorphism

Question

I implemented a broken filter function using an anamorphism from recursion-schemes Hackage library:

import Data.Functor.Foldable

xfilter :: (a -> Bool) -> [a] -> [a]
xfilter f = ana $ project . phi f

phi :: (a -> Bool) -> [a] -> [a]
phi f (h : t) | not (f h) = t
phi f l = l

The function is not a faithful implementation of filter: xfilter odd [1..5] works, but xfilter odd [0,0] doesn't. I tried to implement "retries" by using explicit recursion in phi and then reimplemented that with a paramorphism, so I ended with ana . para:

xfilter :: (a -> Bool) -> [a] -> [a]
xfilter f = ana . para $ phi where
    phi Nil = Nil
    phi (Cons h (t, tt)) | f h = Cons h t
    phi (Cons h (t, tt)) = tt

This is satisfactory, but I then tried to express retries explicitly in phi and perform them outside:

xfilter :: (a -> Bool) -> [a] -> [a]
xfilter f = ana $ project . retry (phi f)

phi :: (a -> Bool) -> [a] -> Either [a] [a]
phi f (h : t) | not (f h) = Left t
phi f l = Right l

retry f x = case f x of
    Right x -> x
    Left x -> retry f x

Right means 'produce a new element' and Left means 'retry with a new seed'.

The signature of phi started to look pretty similar to the first argument of apomorphism specialized for lists:

xxapo :: ([a] -> Prim [a] (Either [a] [a])) -> [a] -> [a]
xxapo = apo

([a] -> Either [a] [a] vs [a] -> Prim [a] [a] (Either [a] [a])

So I wonder is it possible to implement filtering using apomorphisms or other generalized unfolds, or ana . para is the best I can hope for?

I know I can use folds, but the question is specifically about unfolds.

Answer 1

In short: This can't be done. You always have to break down the input list somehow, which you can't accomplish by unfolding alone. You can see that in your code already. You have retry (phi f), which is equivalent to dropWhile (not . f), which recursively consumes an input list. In your case, the recursion is inside retry.

We can implement filter using ana, but the function passed to ana will have to be recursive, as in

filter1 :: (a -> Bool) -> [a] -> [a]
filter1 p = ana f
  where
    f [] = Nil
    f (x : xs') | p x       = Cons x xs'
                | otherwise = f xs'

However, we can implement filtering using para without any further recursion:

filter2 :: (a -> Bool) -> [a] -> [a]
filter2 p = cata f
  where
    f Nil = []
    f (Cons x r) | p x          = x : r
                 | otherwise    = r

(although this is not what you've been interested in).

So why it works with cata but not with ana?

• Catamorphisms represent inductive recursion where each recursive step consumes at least one constructor. Since each steps takes only finite time, together this ensures that when consuming a (finite) data structure, the whole recursion always terminates.
• Anamorphisms represent co-inductive recursion where each recursive step is guarded by a constructor. This means that although the result can be infinite, each part (a constructor) of the constructed data structure is produced in finite time.

Now how filter works: At each step it consumes one element of a list and sometimes it produces an output element (if it satisfies a given predicate).

So we see that we can implement filter as a catamorphism - we consume each element of a list in a finite time.

But we can't implement filter just as an anamorphism. We can never know when filter produces a new result. We can't describe the production of a next output element using just a finite number of operations. For example, let's take filter odd (replicate n 0 ++ [1]) - it takes O(n) steps to produce the first element 1. So there must be some kind of recursion that searches an input list until it finds a satisfying element.

Answer 2

    xfilter :: (a -> Bool) -> [a] -> [a]
    xfilter f xs = last $ apo phi ([xs], []) where
        phi ([[]], ys) = Cons [] $ Left [ys]
        phi ([h:t], ys) | f h = Cons [] $ Right ([t], h:ys)
        phi ([h:t], ys) = Cons [] $ Right ([t], ys)

But last is a cata.