Haskell Language

This is import file

module BinTree where

data BinTree a = Leaf | Node a (BinTree a) (BinTree a)

deriving (Eq,Ord)

sing :: a -> BinTree a

sing x = Node x Leaf Leaf

e = Node 1 (sing 2) (Node 3 (sing 3) (sing 4))

e1 = Node 1 (Node 3 (sing 4) (sing 3)) (sing 2)

e2 = Node 10 (Node 30 (sing 40) (sing 30)) (sing 20)

e3 = Node 10 (sing 30) (sing 20)

e4 = Node 1 (sing 4) (Node 9 (sing 9) (sing 16))

e5 = Node 1 (sing 2) (Node 3 e3 (sing 4))

bst = Node 10 (Node 6 (sing 5) (sing 7)) (Node 13 (sing 11) (sing 15))

bst1 = Node 10 (Node 6 (sing 5) (Node 7 Leaf (sing 8))) (Node 13 (sing 11) (sing 15))

showTree :: Show a => BinTree a -> String

showTree Leaf = "*"

showTree (Node x l r) = "[" ++ show x ++ " " ++ showTree l ++ " " ++ showTree r ++ "]"

instance Show a => Show (BinTree a) where

show = showTree

Here is the question I need help

module Exercises(module Exercises,module BinTree) where

import BinTree

{- the output tree should be just like the input

tree, except that the left and right subtrees of

every node have been switched. -}

mirror :: BinTree a -> BinTree a

mirror = undefined

{- implement a function similar to map for lists, but working on BinTrees.

In more detail: btMap takes in a function from a to b, and should apply

that function to all the values stored in the input BinTree, to obtain

the output BinTree. -}

btMap :: (a -> b) -> BinTree a -> BinTree b

btMap = undefined

{- return the data stored in the BinTree, using a

postfix traversal (so the value stored at each

node appears after values in its subtrees). I

will go over some similar code, which you can

find in the Inclass.hs file for week3 on ICON,

on Tuesday, Feb. 7. -}

toListPost :: BinTree a -> [a]

toListPost = undefined

{- swap the first and second elements of the list, then

repeat. When you get to a list with just one value

or the empty list, return that list. -}

swap2 :: [a] -> [a]

swap2 = undefined

{- combine the two lists by taking one element from the first,

then an element from the second, and so forth. If one list

ends before the other, return the other. -}

knit :: [a] -> [a] -> [a]

knit = undefined

{- return all the subtrees you find at the given depth,

which you may assume is greater than or equal to zero.

At depth 0, you should return a list containing the input tree.

For depth greater than 0, if the input tree is a Leaf, return

the empty list.

-}

btDrop :: Int -> BinTree a -> [BinTree a]

btDrop = undefined

{- this is like zipWith on lists.

The given function should be applied to corresponding values

at Nodes. If one tree has a Node and the other has a Leaf,

just return Leaf. -}

btZipWith :: (a -> b -> c) -> BinTree a -> BinTree b -> BinTree c

btZipWith = undefined

{- We can represent paths into a tree as a list of booleans. Each

Bool indicates whether we should recurse into the left subtree (True) or

the right one (False). Given a path and a tree, return the subtree found

by following the path. If the tree ends in a leaf before the path ends,

then return Nothing. -}

btSubtree :: [Bool] -> BinTree a -> Maybe (BinTree a)

btSubtree = undefined

{- insert the given element of type a into the given BinTree,

viewed as a binary search tree. That is, you may assume

that in any subtree (Node y l r), all data in l are less than

or equal to y, and all data in r are greater than y.

You should insert the new element into the tree in a way

that maintains this property: insert to the left if the new element

is less than or equal to y, and otherwise insert to the right.

If you encounter a Leaf you just create a new singleton tree with

the new element.

If you forgot about binary search trees a little, just search online

for "binary search tree insert". -}

bstInsert :: Ord a => a -> BinTree a -> BinTree a

bstInsert = undefined