[Haskell-cafe] Re: compilation related questions
Achim Schneider
barsoap at web.de
Fri Apr 10 08:40:00 EDT 2009
minh thu <noteed at gmail.com> wrote:
> But for some functions, it can be seen clearly that such information
> could have been constructed at the same time that the data structure.
>
> So it is related to fusion techniques, but with the additional
> possibility of adding fields to the original data structure.
>
Well, the point fusion is about is _not_ to construct lists.
consider
naiveDropEnd xs = take (length xs - 1) xs
, which, due to length being a catamorphism, traverses xs twice.
It can be, in fact, reduced to the more sensible
dropEnd (x:[]) = []
dropEnd (x:xs) = x:dropEnd xs
, but that requires getting rid of the fold by replacing Integers
with Peanos:
length' = map (\_ -> ())
pred = tail
succ = (():)
zarroo = []
Now we can write
notSoNaiveDropEnd xs = take' (pred $ length' xs) xs
, which can be fused into a single y-combinator.
Morale of the story: Folds are the bane of laziness. Having some magic
in place than can choose a lazily constructed (and fused) Peano
instance for Num in the right places would be awesomely cool.
--
(c) this sig last receiving data processing entity. Inspect headers
for copyright history. All rights reserved. Copying, hiring, renting,
performance and/or quoting of this signature prohibited.
More information about the Haskell-Cafe
mailing list