Gleb Alexeyev wrote:
Here's my attempt though it's not really different from using built-in lists:
viewCL CatNil = Nothing viewCL (Wrap a) = Just (a, CatNil) viewCL (Cat a b) = case viewCL a of Nothing -> viewCL b Just (x, xs) -> Just (x, Cat xs b)
My solution was a refinement on this. split = go id where go _ Nil = Nothing go k (Wrap a) = Just (a, k Nil) go k (xs :++: ys) = case go ((ys :++:) . k) xs of Nothing -> go k ys view -> view The trick is in the CPS instead of the direct approach of the original. In the original, if you have a strongly left-branching tree then you need to break the whole spine and you end up constructing another strongly left-branching spine. In this version we construct a right-branching spine instead, which allows future calls to be faster. *Main> inL[1..5] (((Wrap 1 :++: Wrap 2) :++: Wrap 3) :++: Wrap 4) :++: Wrap 5 *Main> viewCL $ inL[1..5] Just (1,(((Nil :++: Wrap 2) :++: Wrap 3) :++: Wrap 4) :++: Wrap 5) *Main> split $ inL[1..5] Just (1,Wrap 2 :++: (Wrap 3 :++: (Wrap 4 :++: Wrap 5))) -- Live well, ~wren