Work for CS-381, Programming Language Fundamentals
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

#### 103 lines 2.5 KiB Raw Permalink Blame History

 `module HW2 where` ``` ``` `-- | Binary trees with nodes labeled by values of an arbitrary type.` `data Tree a` ` = Node a (Tree a) (Tree a)` ` | End` ` deriving (Eq,Show)` ``` ``` `-- | One step in a path, indicating whether to follow the left subtree (L)` `-- or the right subtree (R).` `data Step = L | R` ` deriving (Eq,Show)` ``` ``` `-- | A path is a sequence of steps. Each node in a binary tree can be` `-- identified by a path, indicating how to move down the tree starting` `-- from the root.` `type Path = [Step]` ``` ``` `-- | Create a leaf node.` `leaf :: a -> Tree a` `leaf x = Node x End End` ``` ``` `-- | An example tree.` `ex :: Tree Int` `ex = Node 4 (Node 3 (leaf 2) End)` ` (Node 7 (Node 5 End (leaf 6))` ` (leaf 8))` ``` ``` `instance Functor Tree where` ` fmap f End = End` ` fmap f (Node v l r) = Node (f v) (fmap f l) (fmap f r)` ``` ``` `-- | Map a function over a tree. Applies the given function to every label` `-- in the tree, preserving the tree's structure.` `--` `-- >>> mapTree odd End` `-- End` `--` `-- >>> mapTree even (Node 5 (leaf 2) End)` `-- Node False (Node True End End) End` `--` `-- >>> (mapTree not . mapTree even) (Node 5 End (leaf 2))` `-- Node True End (Node False End End)` `--` `-- >>> mapTree (+10) ex` `-- Node 14 (Node 13 (Node 12 End End) End) (Node 17 (Node 15 End (Node 16 End End)) (Node 18 End End))` `--` `-- >>> ex == (mapTree (subtract 27) . mapTree (+27)) ex` `-- True` `--` `mapTree :: (a -> b) -> Tree a -> Tree b` `mapTree = fmap` ``` ``` ``` ``` `-- | Get the value at the node specified by a path. Returns 'Nothing' if` `-- the given path is invalid.` `--` `-- >>> valueAt [] ex` `-- Just 4` `--` `-- >>> valueAt [L,L] ex` `-- Just 2` `--` `-- >>> valueAt [L,R] ex` `-- Nothing` `--` `-- >>> valueAt [R,L,R] ex` `-- Just 6` `--` `-- >>> valueAt [L,L,L] ex` `-- Nothing` `--` `valueAt :: Path -> Tree a -> Maybe a` `valueAt _ End = Nothing` `valueAt [] (Node a _ _) = Just a` `valueAt (x:xs) (Node _ l r) = valueAt xs \$ if x == L then l else r` ``` ``` `-- | Find a path to a node that contains the given value.` `--` `-- >>> pathTo 3 (leaf 5)` `-- Nothing` `--` `-- >>> pathTo 5 ex` `-- Just [R,L]` `--` `-- >>> pathTo 6 ex` `-- Just [R,L,R]` `--` `-- >>> pathTo 4 ex` `-- Just []` `--` `-- >>> pathTo 10 ex` `-- Nothing` `--` ``` ``` `pathTo :: Eq a => a -> Tree a -> Maybe Path` `pathTo _ End = Nothing` `pathTo v (Node a l r) = orElse currentNode \$ orElse (pathHelper v l L) \$ pathHelper v r R` ` where` ` currentNode = if a == v then Just [] else Nothing` ` pathHelper _ tree dir = fmap (dir:) (pathTo v tree)` ` orElse m1 m2 = if isJust m1 then m1 else m2` ``` isJust mx = mx /= Nothing ```