[Haskell-cafe] encoding for least fixpoint

[Ryan Ingram]

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
instead of O(n).

Similarily, l_out and g_in both seem to add many administrative
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