On Wed, Mar 18, 2009 at 8:10 AM, David Menendez
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