>Except that the list split step in Haskell is O(n) in time, while it is constant when using arrays. Oh, no. You shouldn't split list by calculating length. T

>Except that the list split step in Haskell is O(n) in time, while it is constant when using arrays. Oh, no. You shouldn't split list by calculating length. Try this instead: even (x:_:xs) = x : even xs even xs = xs odd = even . drop 1 splitList xs = (even xs, odd xs) Voila! Completely lazy, O(1). So for merge. See here: http://lambda-the-ultimate.org/node/608?from=0&comments_per_page=200 http://lambda-the-ultimate.org/node/608?from=0&comments_... The solution contains proper merge algorithm. And yes, I never read Okasaki in full. But, I use Haskell semi-professionally from 1999 and professionally from 2006.