Would it be a good or bad idea to make dropWhile try to fuse?

[David Feuer]

Thanks for the info. I think I'm going to leave that one alone for now and
focus on the ones that are more obviously good ideas: scanr, takeWhile, and
(now that we have appropriate optimizations) scanl and (hopefully, if no
one objects) scanl', as well as the semi-related inits. I'd also like to
revisit length, which is currently a horrible mess of rules, and see if the
new foldl' allows it to be written efficiently without so much trouble.
On Jul 25, 2014 5:00 PM, "wren romano" <winterkoninkje at gmail.com> wrote:

> On Fri, Jul 25, 2014 at 12:35 AM, David Feuer <david.feuer at gmail.com>
> wrote:
> > This is generally awful, because it could copy a large portion of the
> > list with no benefit.
>
> This is a general example of why paramorphisms are more powerful than
> catamorphisms. That is, we have the following two notions of
> "folding", where I will uncurry things to make the pattern clearer:
>
>     cata :: (b, a -> b -> b) -> [a] -> b
>     cata (nil,cons) = go
>         where
>         go [] = nil
>         go (x:xs) = cons x (go xs)
>
>     para :: (b, a -> ([a],b) -> b) -> [a] -> b
>     para (nil,cons) = go
>         where
>         go [] = nil
>         go (x:xs) = cons x (xs, go xs)
>
> That is, we pass the algebra both the recursive structure and the
> result of the recursive call, instead of only passing the latter. In
> terms of the definability of (mathematical) functions, cata and para
> have the same power; however, in terms of algorithms, paramorphisms
> are strictly more powerful. For example, for Peano-style natural
> numbers with paramorphisms we can implement an O(1)-time predecessor
> function; but with only catamorphisms the best we can do is O(n)-time.
> Analogously for lists, paramorphisms give us an O(1)-time tail
> function (with structure sharing), whereas catamorphisms only admit
> O(n)-time (without structure sharing). The dropWhile function is a
> generalization of tail, so it'll run into exactly the same problem.
>
> The trick, of course, is getting fusion to work for build/para (or
> dually: apo/destroy). The problem is para doesn't make linear use of
> the recursive substructure, so it isn't as amenable to eliminating
> intermediate structures. In fact, there's a lot of interesting room
> for research here.
>
> > Does anyone
> > have any thoughts about whether this one is worth pursuing?
>
> The fact that it can result in massive copying is disturbing. Before
> adopting it in the core libraries you'd want to make sure you can
> guide the rewrite rules so that this definition of dropWhile is only
> ever used when it will be fused away. But, before taking the time to
> figure out how to do that, you'll probably want to find a bunch of
> examples in the wild so that you can quantify the benefits and compare
> that to the expected development cost. For example, if you have a
> program that makes extensive use of dropWhile, you could manually
> inline the fusing version and see how it compares.
>
> --
> Live well,
> ~wren
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/libraries/attachments/20140725/3bfbf3b5/attachment.html>