From e0fff7c4014512bf88b23136dbbb426d9d9b7511 Mon Sep 17 00:00:00 2001 From: Determinant Date: Tue, 30 May 2017 21:57:26 -0400 Subject: finish vol 7 --- 61-69/68.hs | 35 +++++++++++++++++++++++++++++++++++ 1 file changed, 35 insertions(+) create mode 100644 61-69/68.hs (limited to '61-69/68.hs') diff --git a/61-69/68.hs b/61-69/68.hs new file mode 100644 index 0000000..741795b --- /dev/null +++ b/61-69/68.hs @@ -0,0 +1,35 @@ +data Tree a = Empty | Branch a (Tree a) (Tree a) deriving (Show, Eq) + +stringToTree :: Monad m => [Char] -> m (Tree Char) + +stringToTree "" = return (Empty) +stringToTree [x] = return (Branch x Empty Empty) +stringToTree x = fmap fst $ parse x + where parse (x:xs) + | x == ',' || x == ')' = return (Empty, x:xs) + parse (x:y:xs) + | y == ',' || y == ')' = return (Branch x Empty Empty, y:xs) + | y == '(' = do (lt, ',':xs') <- parse xs + (rt, ')':xs'') <- parse xs' + return (Branch x lt rt, xs'') + parse _ = fail "parse error" + +treeToPreorder :: Tree Char -> [Char] + +treeToPreorder Empty = "" +treeToPreorder (Branch x l r) = x:treeToPreorder l ++ treeToPreorder r + +treeToInorder :: Tree Char -> [Char] + +treeToInorder Empty = "" +treeToInorder (Branch x l r) = treeToInorder l ++ [x] ++ treeToInorder r + + +preInTree :: Monad m => [Char] -> [Char] -> m (Tree Char) +preInTree [] [] = return Empty +preInTree (p:ps) is = do let (lis, _:ris) = break (== p) is + (lps, rps) = splitAt (length lis) ps + lt <- preInTree lps lis + rt <- preInTree rps ris + return $ Branch p lt rt +preInTree _ _ = fail "error" -- cgit v1.2.3