-- CSci 117, Lab 2: Functional techniques, iterators/accumulators,-- and higher-order functions. Make sure you test all of your functions,-- including key tests and their output in comments after your code.
---- Part 1: Basic structural recursion ----------------
-- 1. Merge sort
-- Deal a list into two (almost) equal-sizes lists by alternating elements-- For example, deal [1,2,3,4,5,6,7] = ([1,3,5,7], [2,4,6])-- and deal [2,3,4,5,6,7] = ([2,4,6], [3,5,7])-- Hint: notice what's happening between the answers to deal [2..7] and-- deal (1:[2..7]) above to get an idea of how to approach the recursiondeal :: [a] -> ([a],[a])deal [] = undefineddeal (x:xs) = let (ys,zs) = deal xs in undefined
-- Now implement merge and mergesort (ms), and test with some-- scrambled lists to gain confidence that your code is correctmerge :: Ord a => [a] -> [a] -> [a]merge [] ys = undefinedmerge xs [] = undefinedmerge (x:xs) (y:ys) | x | x > y = undefined
ms :: Ord a => [a] -> [a]ms [] = []ms [x] = [x]ms xs = undefined -- general case: deal, recursive call, merge
-- 2. A backward list data structure
-- Back Lists: Lists where elements are added to the back ("snoc" == rev "cons")-- For example, the list [1,2,3] is represented as Snoc (Snoc (Snoc Nil 1) 2) 3data BList a = Nil | Snoc (BList a) a deriving (Show,Eq)
-- Add an element to the beginning of a BList, like (:) doescons :: a -> BList a -> BList acons = undefined
-- Convert a usual list into a BList (hint: use cons in the recursive case)toBList :: [a] -> BList atoBList = undefined
-- Add an element to the end of an ordinary listsnoc :: [a] -> a -> [a]snoc = undefined
-- Convert a BList into an ordinary list (hint: use snoc in the recursive case)fromBList :: BList a -> [a]fromBList = undefined
-- 3. A binary tree data structuredata Tree a = Empty | Node a (Tree a) (Tree a) deriving (Show, Eq)
-- Count number of Empty's in the treenum_empties :: Tree a -> Intnum_empties = undefined
-- Count number of Node's in the treenum_nodes :: Tree a -> Intnum_nodes = undefined
-- Insert a new node in the leftmost spot in the treeinsert_left :: a -> Tree a -> Tree ainsert_left = undefined
-- Insert a new node in the rightmost spot in the treeinsert_right :: a -> Tree a -> Tree ainsert_right = undefined
-- Add up all the node values in a tree of numberssum_nodes :: Num a => Tree a -> asum_nodes = undefined
-- Produce a list of the node values in the tree via an inorder traversal-- Feel free to use concatenation (++)inorder :: Tree a -> [a]inorder = undefined
-- 4. A different, leaf-based tree data structuredata Tree2 a = Leaf a | Node2 a (Tree2 a) (Tree2 a) deriving Show
-- Count the number of elements in the tree (leaf or node)num_elts :: Tree2 a -> Intnum_elts = undefined
-- Add up all the elements in a tree of numberssum_nodes2 :: Num a => Tree2 a -> asum_nodes2 = undefined
-- Produce a list of the elements in the tree via an inorder traversal-- Again, feel free to use concatenation (++)inorder2 :: Tree2 a -> [a]inorder2 = undefined
-- Convert a Tree2 into an equivalent Tree1 (with the same elements)conv21 :: Tree2 a -> Tree aconv21 = undefined
---- Part 2: Iteration and Accumulators ----------------
-- Both toBList and fromBList from Part 1 Problem 2 are O(n^2) operations.-- Reimplement them using iterative helper functions (locally defined using-- a 'where' clause) with accumulators to make them O(n)toBList' :: [a] -> BList atoBList' = undefined
fromBList' :: BList a -> [a]fromBList' = undefined
-- Even tree functions that do multiple recursive calls can be rewritten-- iteratively using lists of trees and an accumulator. For example,sum_nodes' :: Num a => Tree a -> asum_nodes' t = sum_nodes_it [t] 0 where sum_nodes_it :: Num a => [Tree a] -> a -> a sum_nodes_it [] a = a sum_nodes_it (Empty:ts) a = sum_nodes_it ts a sum_nodes_it (Node n t1 t2:ts) a = sum_nodes_it (t1:t2:ts) (n+a)
-- Use the same technique to convert num_empties, num_nodes, and sum_nodes2-- into iterative functions with accumulators
num_empties' :: Tree a -> Intnum_empties' = undefined
num_nodes' :: Tree a -> Intnum_nodes' = undefined
sum_nodes2' :: Num a => Tree2 a -> asum_nodes2' = undefined
-- Use the technique once more to rewrite inorder2 so it avoids doing any-- concatenations, using only (:).-- Hint 1: (:) produces lists from back to front, so you should do the same.-- Hint 2: You may need to get creative with your lists of trees to get the-- right output.inorder2' :: Tree2 a -> [a]inorder2' = undefined
---- Part 3: Higher-order functions ----------------
-- The functions map, all, any, filter, dropWhile, takeWhile, and break-- from the Prelude are all higher-order functions. Reimplement them here-- as list recursions. break should process each element of the list at-- most once. All functions should produce the same output as the originals.
my_map :: (a -> b) -> [a] -> [b]my_map = undefined
my_all :: (a -> Bool) -> [a] -> Boolmy_all = undefined
my_any :: (a -> Bool) -> [a] -> Boolmy_any = undefined
my_filter :: (a -> Bool) -> [a] -> [a]my_filter = undefined
my_dropWhile :: (a -> Bool) -> [a] -> [a]my_dropWhile = undefined
my_takeWhile :: (a -> Bool) -> [a] -> [a]my_takeWhile = undefined
my_break :: (a -> Bool) -> [a] -> ([a], [a])my_break = undefined
-- Implement the Prelude functions and, or, concat using foldr
my_and :: [Bool] -> Boolmy_and = undefined
my_or :: [Bool] -> Boolmy_or = undefined
my_concat :: [[a]] -> [a]my_concat = undefined
-- Implement the Prelude functions sum, product, reverse using foldl
my_sum :: Num a => [a] -> amy_sum = undefined
my_product :: Num a => [a] -> amy_product = undefined
my_reverse :: [a] -> [a]my_reverse = undefined
---- Part 4: Extra Credit ----------------
-- Convert a Tree into an equivalent Tree2, IF POSSIBLE. That is, given t1,-- return t2 such that conv21 t2 = t1, if it exists. (In math, this is called-- the "inverse image" of the function conv21.) Thus, if conv21 t2 = t1, then-- it should be that conv 12 t1 = Just t2. If there does not exist such a t2,-- then conv12 t1 = Nothing. Do some examples on paper first so you can get a-- sense of when this conversion is possible.conv12 :: Tree a -> Maybe (Tree2 a)conv12 = undefined
-- Binary Search Trees. Determine, by making only ONE PASS through a tree,-- whether or not it's a Binary Search Tree, which means that for every-- Node a t1 t2 in the tree, every element in t1 is strictly less than a and-- every element in t2 is strictly greater than a. Complete this for both-- Tree a and Tree2 a.
-- Hint: use a helper function that keeps track of the range of allowable-- element values as you descend through the tree. For this, use the following-- extended integers, which add negative and positvie infintiies to Int:
data ExtInt = NegInf | Fin Int | PosInf deriving Eq
instance Show ExtInt where show NegInf = "-oo" show (Fin n) = show n show PosInf = "+oo"
instance Ord ExtInt where compare NegInf NegInf = EQ compare NegInf _ = LT compare (Fin n) (Fin m) = compare n m compare (Fin n) PosInf = LT compare PosInf PosInf = EQ compare _ _ = GT -- Note: defining compare automatically defines <,><=,>, >=, ==, /=bst :: Tree Int -> Boolbst = undefined bst2 :: Tree2 Int -> Boolbst2 = undefined