<p dir="ltr">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.</p>

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