[Haskell-cafe] Re: Interesting problem from Bird (4.2.13)

[wren ng thornton]

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