tree.hs

{-# LANGUAGE NoImplicitPrelude #-}
module Tree where

import P hiding (Left, Right)

data Tree a = Leaf a | Bin (Tree a) (Tree a)

data Circular a = Node a (Circular a) (Circular a) 

-- pre-order traversal
--
--   .
--  / \
-- 0   .
--    / \
--   .   .
--  / \  |\
-- 1   5 7 3
--
-- 0 <-> 1 <-> 5 <-> 7 <-> 3 <-> 0 <-> ...
--
toCircular :: Tree a -> Circular a
toCircular t =
  let
    go :: Tree a -> Circular a -> Circular a
    go (Leaf a) n =
      let
        x =
          Node a x n
      in
        x
    go (Bin t1 t2) n =
      let
        x1 =
          go t1 x2
        x2 =
          go t2 n
      in
        x1
  in
    go t (toCircular t)

-- view 8 . toCircular $ t
-- [0,1,5,7,3,0,1,5]
view :: Int -> Circular a -> [a]
view 0 _ =
  []
view n (Node a _ t2) =
  a : view (n-1) t2