module MultiTreeZipper where

(|>) = flip ($)

data MultiTree a
  = Node a [MultiTree a] -- children intended to be non-empty
  | Empty
  deriving (Show)

data MultiTreeZipper a = Z (MultiTree a, Path a)
  deriving (Show)

type PathStep a =
  ( a               -- parent node value
  , [MultiTree a]   -- left sibings, in reverse order
  , [MultiTree a]   -- right siblings
  )

type Path a = [PathStep a]

goLeft, goRight, goUp, goDownFirst :: MultiTreeZipper a -> MultiTreeZipper a

goLeft (Z (t, (x, l:left, right) : up)) = Z (l, (x, left, t:right) : up)
goRight (Z (t, (x, left, r:right) : up)) = Z (r, (x, t:left, right) : up)
goUp (Z (t, (x, left, right) : up)) = Z (Node x (reverse left ++ [t] ++ right), up)
goDownFirst (Z (Node x (t:children), up)) = Z (t, (x, [], children) : up)