[SOLVED] CS Group members:

Group members:
* Han-Hsing Pao, 933651943
* Jiayu Han, 932907189
* Name, ID

Grading note: 10pts total
* 2pts each for encodeList and mapTree
* 3pts each for valueAt and pathTo
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))

| Encode a list as a tree with only right branches.

>>> encodeList []
End

>>> encodeList [1,2,3,4]
Node 1 End (Node 2 End (Node 3 End (Node 4 End End)))

>>> encodeList 😀
Node : End (Node – End (Node D End End))

encodeList :: [a]-> Tree a
encodeList [] = End
encodeList (x:xs) = Node x End (encodeList xs)

If stdin is empty, we just need to output as End, which is the base case.
Since Encode is a list as a tree with only right branches, the left branch
is always gonna be End. The format is just (Node x end xs), which is just a simple
recursion.

| Map a function over a tree. Applies the given function to every label
in the tree, preserving the trees 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 f End= End
mapTree f (Node x y z) = Node (f x) (mapTree f y) (mapTree f z)

| 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 x _ _) = Just x
valueAt (L:xs) (Node _ leftside _)= valueAt xs leftside
valueAt (R:xs) (Node _ _ rightside) = valueAt xs rightside

Since the output is Just[] or Nothing, we need to use Maybe.
First we need to set the base cases:
if there is an end, then output will be Nothing
if the path is empty, then output will be Just x
else we just need to do recursion based on the indicators from the list
for either left subtree or right subtree.

| 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 x End= Nothing
pathTo x (Node xs leftside rightside)
| x == xs= Just []
| otherwise= case (pathTo x leftside, pathTo x rightside ) of
(Just p, _) -> Just (L:p)
(_, Just p) -> Just (R:p)
_ -> Nothing

First, we set the base case for End, which will return Nothing.
There will be 3 cases:
x == xs, returns Just []
search left subtree
search right subtree
We use pair to group both left and right recursion together, which add L/R to
the current path list till the value is found, otherwise the value is not found
after recursion, return Nothing.