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

wren ng thornton wren at freegeek.org
Fri Mar 6 23:49:19 EST 2009

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