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

25 Jul 2014


      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"  wrote:
...
On Fri, Jul 25, 2014 at 12:35 AM, David Feuer 
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