[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