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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
