[Haskell-cafe] encoding for least fixpoint
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
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
More information about the Haskell-Cafe
mailing list