[GHC] #876: stack overflow on 'length . filter odd $ [0 .. 999999999]'

[Bulat Ziganshin]

Hello Malcolm,

Thursday, August 31, 2006, 2:29:46 PM, you wrote:

>> in general, for any function we can either implement
>> 1) good consumer based on using foldr
>> 2) tail-recursion
>> 
>> are you agree?

> I'd like to point out that, if you are prepared to abandon foldr/build
> fusion in favour of hylo fusion, you can code good consumers using
> either foldr or foldl.

looks promising. but even if GHC HQ will accept your plan, something
will still remain to fix: there are some functions, such as 'filter', that
can be implemented via foldr but not via foldl. such functions has two
possible implementations:

1) using foldr, which make them goo producers
2) using reverse+foldl which makes them tail-recursive

which makes situation more interesting is that even without fusion
foldr=based solution will be faster for most lists - as long as whole
processed data fits in L2 processor cache (at least, this says results
of my tests of replicateM implementations)


.... browsing GHC.List, i've found the following:

#ifdef USE_REPORT_PRELUDE
and                     =  foldr (&&) True
or                      =  foldr (||) False
#else
and []          =  True
and (x:xs)      =  x && and xs
or []           =  False
or (x:xs)       =  x || or xs

{-# RULES
"and/build"     forall (g::forall b.(Bool->b->b)->b->b) . 
                and (build g) = g (&&) True
"or/build"      forall (g::forall b.(Bool->b->b)->b->b) . 
                or (build g) = g (||) False
 #-}
#endif


why we can't use foldl in definition and at the same time have rules
for using with build ???

i understand that it's impossible for and/or, but for 'length' this
should work, i think?




-- 
Best regards,
 Bulat                            mailto:Bulat.Ziganshin at gmail.com