Download the skeleton file ListsAndTrees.elm and use it as a starting point for the following problems. Look for all occurrences of TODO in comments, which point out where you should implement your solutions. Once you are done, follow the submission instructions below.
Implement the function
suffixes : List a -> List (List a)so that it returns a list of all suffixes of the input in decreasing order of length. Then, in comments, argue why your implementation runs in O(n) time and can be represented in O(n) space.
Once you have implemented the function, you should get the following behavior at the Elm REPL:
> import ListsAndTrees exposing (..)
> suffixes (List.range 1 4)
[[1,2,3,4],[2,3,4],[3,4],[4],[]] : List (List number)In this problem, you will define several functions that operate on binary trees of integers represented by the type:
type Tree a = Empty | Node a (Tree a) (Tree a)Write a function
mem : comparable -> Tree comparable -> Boolsuch that mem x t determines whether x is contained in the binary search tree t, using at most h+1 comparisons where h is the height of t. Each of the following functions constitutes one comparison: (==), (/=), (<=), (<), (>=), (>).
Write a function
fullTree : a -> Int -> Tree asuch that fullTree x h produces a completely full tree of height h where every node stores the element x. Your function should return the empty tree whenever h is less than or equal to zero. This function should run in O(h) time.
For example:
> fullTree 0 0
Empty : ListsAndTrees.Tree
> fullTree 0 1
Node 0 Empty Empty : ListsAndTrees.Tree
> fullTree 0 2
Node 0 (Node 0 Empty Empty) (Node 0 Empty Empty) : ListsAndTrees.TreeThe size of a tree is the number of (non-empty) nodes it contains. We will say a tree t is size-balanced if for any given node n in t, the two subtrees of n differ in size by at most one.
Write a function
balancedTree : a -> Int -> Tree asuch that balancedTree x n returns some balanced tree of size n, where the element x is stored at all nodes. This function should run in O(log n) time.
Hint: Use a helper function create2 that, given a size m, creates a pair of trees, one of size m and one of size m+1.
Write a function
balancedTrees : a -> Int -> List (Tree a)such that balancedTrees x n returns all balanced trees of size n, where the element x is stored at all nodes.
The following is a sanity check:
> List.map (List.length << balancedTrees 0) (List.range 0 20)
[1,1,2,1,4,4,4,1,8,16,32,16,32,16,8,1,16,64,256,256,1024] : List IntA complete tree is typically defined to be a tree where every level except possibly the last is completely full and the nodes in the last level are as far left as possible.
Write a function
completeTrees : a -> Int -> List (Tree a)such that completeTrees x h returns all complete trees of height h where x is stored at every node.
The following is a sanity check:
> List.map (List.length << completeTrees 0) (List.range 0 5)
[1,1,2,4,8,16] : List IntOne strategy for this problem is based on how breadth-first order can be used to index the nodes of a complete binary tree. For example:
Level 1 1
Level 2 2 3
Level 3 4 5 6 7
. . . . . . . .Using this observation, you can implement completeTrees by computing a full tree of height h-1 (think fullTree) and then adding “all valid rows for level h” to it (think suffixes). The key is to define a function that “adds” a row to the bottom level of an existing tree.
We will say that a tree is almost complete if all levels except possibly the last are completely full; we impose no constraints on the last level of an almost complete tree.
Write a function
almostCompleteTrees : a -> Int -> List (Tree a)such that almostCompleteTrees x h returns all almost complete trees of height h where x is stored at every node.
Think about how to refactor your solution to the previous problem so that much of it can be reused for this one. Hint: You can use subsequences in a similar way to how suffixes was used.
The following is a sanity check:
> List.map (List.length << almostCompleteTrees 0) (List.range 0 5)
[1,1,3,15,255,65535] : List IntSubmit the following file:
ListsAndTrees.elm updated with your changes. You are free to modify this file as you wish, as long as you do not change any type signatures that are provided.Your solution will be graded using a combination of automated grading scripts and manual review. It is a good idea for you to design some test cases of your own to exercise more sample behaviors than just the ones provided in the writeup. We also reserve the right to take into account the organization and style of your code when assigning grades.
If you are not able to finish all parts of the assignment, make sure that all of your submitted files compile successfully. If not, you risk getting zero points for the assignment. In particular, for each file Foo.elm, make sure that it can be loaded into the Elm REPL
% elm-repl
> import Foo
>and that it can be compiled to a standalone HTML file:
% elm-make Foo.elm --output=Foo.html
Successfully generated Foo.html