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

Submitted by Cale Gibbard on Mon, 10/03/2005 - 11:22pm.

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.

Submitted by Cale Gibbard on Mon, 10/03/2005 - 11:41pm.

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.

Submitted by dtlin on Tue, 10/04/2005 - 2:30pm.

a ++ listElem ++ b
  where (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.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.