Homework 2

Instructions

The source code of this homework can be found here. You should fill in the definitions of the required functions but do not change the types of the functions.

How to submit: Submit this file and a MinMax.lhs file via the submit server.

> module HW2 where
> import Prelude hiding (map)

Problem 1: Programming Patterns

In the class we “saw” mapping and folding on lists. Here you are required to port these patterns on Trees.

A tree is either empty or contains a value and two subtrees:

> data Tree a = Tip | Bin a (Tree a) (Tree a)
>   deriving (Eq, Show)

For testing, we define few trees

> tree1 = Tip 
> tree2 = Bin 1 (Bin 2 Tip Tip) Tip  
> tree3 = Bin 0  tree2 tree2
> tree4 = Bin "I am" (Bin "a" Tip Tip) (Bin "tree" Tip Tip)

1. Mapping: Define a function that maps all elements of a tree. For example,

map (+1)    tree2 = Bin 2 (Bin 3 Tip Tip) Tip
map (++"!") tree4 = Bin "I am!" (Bin "a!" Tip Tip) (Bin "tree!" Tip Tip)

> map :: (a -> b) -> Tree a -> Tree b 
> map f t = error "Define me!"

2. Folding: Define a function that folds the elements of a tree, top to bottom and left to right; so that

fold (++) "" tree4 == "I amatree"
fold (+)  0  tree3 == 6

> fold :: (b -> a -> b) -> b -> Tree a -> b 
> fold f b = error "Define me!"

3. Elements: Use your fold function to define a function that returns the list of all the elements of the tree. For example,

elems  tree2 == [2,1]
elems  tree4 == ["tree","a","I am"] 

> elems :: Tree a -> [a]
> elems t = error "Define me!"

Problem 2: Merge Sort

In this problem, you will implement the standard merge sort algorithm.

The function mergeSort splits the input list at halves, recursively sorts both halves and merges the two sorted halves.

> mergeSort :: [Int] -> [Int]
> mergeSort []  = [] 
> mergeSort [x] = [x]
> mergeSort xs  = merge (mergeSort ys) (mergeSort zs)
>   where 
>   (ys,zs)     = splitHalf xs

1. List splitting: Define the function splitHalf xs that split the input list into two sublists. For example:

splitHalf [1..4] == ([1,2],[3,4])
splitHalf [1..5] == ([1,2],[3,4,5])

Hint: You can use the function splitAt.

> splitHalf :: [a] -> ([a],[a])
> splitHalf xs = error "Define me!"

2. Merging: Define the function merge that merges two sorted lists. For example,

merge [1, 5, 9] [2,8] == [1,2,5,8,9]

Your definition should satisfy the below type signature that reads as follows: The input lists contain elements of type a that satisfies the constraint Ord. This constraint lets you use any of the standard following comparison operators on elements of the input lists

(<), (<=), (>), (>=) :: Ord a => a -> a -> Bool   

> merge :: Ord a => [a] -> [a] -> [a]
> merge xs ys = error "Define me!"

3. Raising the Ord constraint: Haskell defines the data type Ordering as follows:

data Ordering = LT | EQ | GT

to represent less, equal, and greater comparison respectively. Moreover the library function compare is defined so that

compare x y == LT <=> x <  y
compare x y == EQ <=> x == y
compare x y == GT <=> x >  y

Redefine the merge and mergeSort functions to take an explicit comparison argument. That is, complete the definitions below so that

mergeBy compare xs == merge xs 

> mergeBy :: (a -> a -> Ordering) -> [a] -> [a] -> [a]
> mergeBy cmp xs ys     = error "Define me!"
> 
> mergeSortBy :: (a -> a -> Ordering) -> [a] -> [a]
> mergeSortBy cmp xs ys = error "Define me!"

Problem 3: Fancy Sort

Merge sort is an efficient sorting algorithm, but it does not perform well when the input list is already sorted! The goal of this problem is to implement a different sorting algorithm, fancySort that performs excellent when the list is already increasing or even decreasing.

The idea behind fancySort is the following.

• First, grap all the sorted sequences that appear in the input list and
• then, merge all the sorted sublists together.

> fancySort :: Ord a => [a] -> [a]
> fancySort = mergeAll . sequences

1. Merging: Define the function mergeAll that uses the merge from Problem 2 to merge a list of sorted lists into a single sorted list. For example,

mergeAll [[1, 5, 9], [2,8], [7]] == [1,2,5,7,8,9]

> mergeAll :: Ord a => [[a]] -> [a]
> mergeAll xs = error "Define me!"

The fancySort function creates the sorted sequences as follows. If the input list (a:b:xs) looks like ascending, that is a < b, then we call ascending' with the “accumulated” sorted list [a] and a “pivot” element b with the goal to collect the rest of the ascending list. Otherwise we call descending with dual arguments and goals. For example,

sequences [1, 2, 3, 2, 1] == [[1,2,3],[1,2],[]]
sequences [1, 2, 3, 4, 5] == [[1,2,3,4,5],[]]
sequences [5, 4, 3, 2, 1] == [[1,2,3,4,5],[]]

> sequences :: Ord a => [a] -> [[a]]
> sequences (a:b:xs)
>   | a < b     = ascending' b [a] xs
>   | otherwise = descending b [a] xs
> sequences xs  = [xs]

The function ascending' a as (b:bs) takes as input the pivot element a, the increasing accumulator as, and the unsorted list xs. If the pivot is less than b, it puts the pivot in the head of the accumulator and recurses, otherwise, it returns the first sorted sequence reverse(a:as) and calls back to sequences to construct the next descending sequence.

> ascending' :: Ord a => a -> [a] -> [a] -> [[a]]
> ascending' a as (b:bs)
>   | a < b = ascending' b (a:as) bs
> ascending' a as bs = (reverse(a:as)):sequences bs

2. Define descending: Follow the definition of ascending' to define descending that returns the first descending sequence it finds and calls back to sequences for the rest. For example,

descending 4 [] [3, 2, 1]       == [[1,2,3,4],[]]
descending 0 [] [3, 2, 1]       == [[0],[1,2,3],[]]
descending 0 [] [1, 2, 3, 2, 1] == [[0],[1,2,3],[1,2],[]]

Note that descending should only find strictly descending sequences, i.e.

descending 1 [] [1, 2]          == [[1],[1,2],[]]

> descending :: Ord a => a -> [a] -> [a] -> [[a]]
> descending a as bs = error "Define me!"

3. (Difficult) Optimize ascending: Ascending on an increasing list gives us back exactly one sequence:

ascending' 0 [] [1, 2, 3, 4] == [[0,1,2,3,4],[]]

but to do so, the ascending' definition imposes a huge performance leak as it has to reverse the returning list. Define a higher order ascending that satisfies the below type signature, does not reverse the returning sequence and still behaves like ascending' in that

forall xs, a: ascending a id xs == ascending' a [] xs  

where id is the identity functions.

Restrictions: Increasing lists should be accessed only once! You are not allowed to use reverse, (++), or any other list operations. Define ascending only by using

• one comparison,

• recursive calls to ascending and sequences,

• function application and abstraction (i.e., lambda),

• the list data constructors ([] and (:)),

• and no intermediate helper functions.

> ascending :: Ord a => a -> ([a] -> [a]) -> [a] -> [[a]]
> ascending a as bs = error "Define me!"

Finally, replace the call to ascending' with ascending in the sequences definition.

Problem 4: Tic-Tac-Toe

• Step 1: Download the tic-tac-toe game.

git clone https://github.com/nikivazou/tic-tac-toe.git

• Step 2: Install the game and play against the random strategy.

cd tic-tac-toe/
stack install 
tic-tac-toe

• Step 3: Follow the description in the src/Player/MinMax.lhs file.

• Step 4: Import and call your player. In src/TicTacToe.hs add

import Player.MinMax (playerMinMax)

then in src/TicTacToe.hs#L11 replace

player1 = playerHuman "Me!"

with

player1 = playerMinMax

and make sure that your playerMinMax always wins the computer.