hub.darcs.net :: ross -> fingertree -> issue

treeowl

splitTree is much too lazy. Instead of building two trees, it builds two chains of thunks which, when forced, will build trees. There is very little to be gained from this, and the cost is high. Basically, it only makes sense when <> is expensive, in which case a monoidal finger tree probably isn't the right data structure anyway. I suggest something like this:

splitTree :: (Measured v a) =>
    (v -> Bool) -> v -> FingerTree v a -> Split (FingerTree v a) a
splitTree _ _ Empty = illegal_argument "splitTree"
splitTree _ _ (Single x) = Split Empty x Empty
splitTree p i (Deep _ pr m sf)
  | p vpr       =  let  !(Split l x r)     =  splitDigit p i pr
                   in   Split (maybe Empty digitToTree l) x (deepL r m sf)
  | p vm        =  let  !(Split ml xs mr)  =  splitTree p vpr m
                        !(Split l x r)     =  splitNode p (vpr `mappend` measure ml) xs
                   in   Split (deepR pr  ml l) x (deepL r mr sf)
  | otherwise   =  let  !(Split l x r)     =  splitDigit p vm sf
                   in   Split (deepR pr  m  l) x (maybe Empty digitToTree r)
  where
    vpr     =  i    `mappend`  measure pr
    vm      =  vpr  `mappend`  measure m

(><) is also excessively lazy, in my opinion. While there's a theoretical advantage to building only as much as is immediately necessary, repeated appends will build up thunk chains just under the first node, which are lousy for practical performance. I found that forcing (the rebuilt portion of) the spine was very helpful for appends in Data.Sequence; I imagine it would be so here too.