Ryan Ingram ryani.spam at gmail.com
Wed Mar 18 17:47:48 EDT 2009

On Wed, Mar 18, 2009 at 8:10 AM, David Menendez <dave at zednenem.com> wrote:
> l_out :: Functor f => Lfix f -> f (Lfix f)
> l_out = cata (fmap l_in)
>
> g_in :: Functor f => f (Gfix f) -> Gfix f
> g_in = ana (fmap g_out)

OK, I understand these now.

But they both seem to have significant performance implications, which
I think are related to the "tail-in-terms-of-foldr" problem.

Consider this definition:

safeTail [] = []
safeTail (x:xs) = xs

The simplest way to write this directly with foldr is:

safeTail' = fst . foldr f ([], []) where
f x (t, l) = (l, x:l)

But the difference is that safeTail' here reconstructs the list from
scratch, instead of reusing the existing data as safeTail does.  This
means that (safeTail . safeTail . safeTail ...) takes O(n^2) time

redexes to every element of the object being manipulated; consider

gid = g_in . g_out

then consider
(gid . gid . gid . gid) x

The result gets filled up quickly with administrative redexes that look like
Gfix (fmap g_out) \$ g_out \$ Gfix (fmap g_out) \$ g_out \$ Gfix ...

Is there a way to solve this problem and still maintain the nice
totality guarantees that you get from System F without fix?

-- ryan