[Haskell-cafe] Re: compilation related questions
minh thu not...@gmail.com wrote: On a related note, I have another question. Say we have some data structure, for instance a list, some functions on this data structure (probably defined with some well known functions, such as map or fold), and a program using them. Is there any research trying to rewrite the program, and the data structure, to optimize them ? Yes. The most advanced approach that I know of is Dons' stream-fusion[1]. I guess the technique of transforming a program so that Y-combinators are at their outermost possible position (and fused, in the process) could be generalised. A contrived example is the length of a list : instead of traversing a list to know its length, the list can have an additional field which is incremented at each cons. Well, that's not a list anymore, at least not with some additional ingenuity to deal with infinite ones. Statically-lengthed lists can be done with some type trickery, see e.g. [2], if that helps. [1] http://www.cse.unsw.edu.au/~dons/papers/CLS07.html [2] http://article.gmane.org/gmane.comp.lang.haskell.general/13561 -- (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. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: compilation related questions
minh thu not...@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. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
