List filter using an anamorphism

corecursion, haskell, list, recursion, recursion-schemes

Solution

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.

Problem

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.

Original source