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.

Kronos

I'm fairly sure you can't do that with anamorphism (or apomorphism) alone. These two schemes characterize productive corecursion and filter need not be productive: filter (const False). – Predikant

I can define filter (const False) using ana (const Nil) – Kronos

Should your filter work on infinite lists? – Predikant

I don't care for now. – Kronos

btw, why do you need ana . para? you can do it with just para – Kwabena

I was pushing the limits of anamorphisms, for education sake. – Kronos

@Kronos ana- and apomorphisms are for coalgebras for some functor. Here we are dealing with list, so coalgebra must generate one element, and the seed for the rest, or a empty list. Since you need to skip zero or more elements in the seed list, your coalgebra is necessarily a paramorphism. In your case, this paramorphism implements a dropWhile (not.f) – Kwabena

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.

Binoculars

Great explanation! "You always have to break down the input list" is a great argument. – Kronos

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.

Kwabena

Besides last being a cata, we end up doing all the list building through the seed, bypassing the element emission of the unfold. xfilter, as written here, will reverse the list, but that might be fixed with a dlist trick. – Tortricid

@Tortricid A trick to turn filter into a productive corecursion, which I saw in some paper on corecursion and (what else) the Sieve of Eratosthenes, is just to have each step produce a list of at most one element, and pass the overall result through a concat (moving the recursive onus onto it). concat is of course recursive as it can't know how many [] to skip over, but it's much much less off-line than reverse . last here. so, afilter p = concat . ana phi where phi [] = Nil ; phi (x:xs) = Cons [x | p x] xs, I guess. – Halfbeak

@WillNess That's neat -- a hylo with a virtual list and concat (or catMaybes) on the fold side. – Tortricid

yes, catMaybes is much better -- and with MonadComprehensions, the code for phi even remains the same. – Halfbeak