From: "Alastair Reid" <[EMAIL PROTECTED]> > > Gertjan Kamsteeg <[EMAIL PROTECTED]> writes: > >> You don't have to define cpsfold explicitly recursively since it > >> can be expressed in terms of foldr: > > Hal Daume III <[EMAIL PROTECTED]> writes: > > Is this generally considered good design? [...] > > Three different attempts at an answer: > > As with all code-factoring it's in the eye of the beholder. > > If what you want to do is trace execution in detail, the less factored > code is easier to understand. > > If what you want to do is understand the difference between 5 > different recursive traversals of a list, then isolating those > differences (by suppressing the invariant fact of recursion) is > better. >
I agree. However, although *functionally* every list traversing function should be expressible in terms of foldr (because foldr represents the type theoretical elimination rule for lists in most type systems with inductive types (and without element depending types)), it's not just a matter of taste. Execution clearly *does* depend on how things are defined. When I said 'can be expressed', I meant extensionally equivalent, including behavior w.r.t. reductions. For example, if, in the Prelude, foldr had been defined in terms of foldl: foldr f a xs = foldl (\h x y -> h (f x y)) id xs a my definition of cpsfold in terms of foldr wouldn't go through. That is, some stack would again overflow. What I wanted to say is that the fact that Amanda's answer1 (maximum in terms of foldr) didn't work wasn't caused by the definition of foldr in the Prelude. Besides, (re)factoring is fun. So, here's another one (foldl in terms of foldr): foldl f a xs = foldr (\x h y -> h (f y x)) id xs a BTW, there may be another reason for expressing list traversing functions in terms of foldr: if one uses only functions representing 'standard' elimination rules, it is guaranteed that all reduction sequences eventually terminate. Gertjan _______________________________________________ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
