does haskell optimize list surgery?
Submitted by metaperl on Mon, 10/03/2005 - 12:46pm.
does Haskell optimize the list dissection in something like this:
take n lis ++ listElem ++ drop (n+1) lis
- metaperl's blog
- Login to post comments
does Haskell optimize the list dissection in something like this:
take n lis ++ listElem ++ drop (n+1) lis
How should it be optimized? The drop (n+1) lis will produce a pointer to the middle of lis, while the rest of the stuff has to be reconstructed. The actual list elements won't be recomputed (or computed at all) though, it's all pointers to values or code which produces values.
Now that I think about it, one could slightly optimise that code by using splitAt, which will only do one traversal of lis (though by the Report Prelude, that doesn't have any effect, as it defines splitAt n xs = (take n xs, drop n xs)).
I wouldn't expect the gains to be huge though.
a ++ listElem ++ bwhere (a,_:b) = splitAt n lis
I don't think Haskell will optimize to that, but I agree that it probably wouldn't make a big difference. It's O(n) either way.