これはかなり好きな問題。でもちょっとテストケースが弱い気がする。

## 解法

• A single node will never have more than $10$ children.

なので、やればよい。以下のような構造になる。

data Tree = Tree
{ value :: Int
, children :: [Tree]
}

data Zipper = Zipper
{ tree :: Tree
, lefts :: [Tree]
, rights :: [Tree]
, parents :: [([Tree], Int, [Tree])]
}


## 実装

reverseを忘れないように。

module Main where
import Data.List

data Tree = Tree
{ value :: Int
, children :: [Tree]
}

data Zipper = Zipper
{ tree :: Tree
, lefts :: [Tree]
, rights :: [Tree]
, parents :: [([Tree], Int, [Tree])]
}

initialTree :: Zipper
initialTree = Zipper (Tree 0 []) [] [] []

command :: Zipper -> IO Zipper
command z = do
let t = tree z
l <- getLine
case words l of
["change", x] ->
return z { tree = t { value = read x } }
["print"] -> do
print $value t return z ["visit", "left"] -> do let (l : ls) = lefts z return z { lefts = ls, tree = l, rights = t : rights z } ["visit", "right"] -> do let (r : rs) = rights z return z { lefts = t : lefts z, tree = r, rights = rs } ["visit", "parent"] -> do let ((ls, v, rs) : ps) = parents z return$ Zipper (Tree v (reverse (lefts z) ++ [t] ++ rights z)) ls rs ps
["visit", "child", n] -> do
let (ls, t' : rs) = splitAt (read n - 1) (children t)
return $Zipper t' (reverse ls) rs ((lefts z, value t, rights z) : parents z) ["insert", "left", x] -> return z { lefts = Tree (read x) [] : lefts z } ["insert", "right", x] -> return z { rights = Tree (read x) [] : rights z } ["insert", "child", x] -> return z { tree = t { children = Tree (read x) [] : children t } } ["delete"] -> do let ((ls, v, rs) : ps) = parents z return$ Zipper (Tree v (reverse (lefts z) ++ rights z)) ls rs ps

main :: IO ()
main = do