Tree.hs

{-# LANGUAGE DerivingStrategies #-}
{-# LANGUAGE LambdaCase #-}

module Tree where

data Tree a = Leaf | Node (Tree a) a (Tree a)
  deriving stock (Eq, Show)
  
data Direction = L | R
  deriving stock (Eq, Show)
  
insertAt :: [Direction] -> Tree a -> Tree a -> Maybe (Tree a)
insertAt dirs target t = case dirs of
  [] -> Just t
  (d : ds) -> case target of 
    Leaf -> Nothing
    Node l x r -> case d of
      L -> Node <$> insertAt ds l t <*> pure x <*> pure r
      R -> Node l x <$> insertAt ds r t