I am trying to create a functional array using a list, with a given function from a question. Formally, the task is to create a functional array from a list with indices starting from 1.
However, I am stuck in this task for days without any progress. Hoping for some hints to get this done..
Here is what I have done:
datatype 'a tree = Leaf
| Branch of 'a * 'a tree * 'a tree
fun addnode a Leaf = Branch (a, Leaf, Leaf)
| addnode a (Branch (b, tree1, tree2)) = Branch (a, addnode b tree2, tree1);
fun functionalarray (0, a) = Leaf
| functionalarray(n, a::b::r) = Branch(a, functionalarray(n div 2, r), functionalarray(n-1 div 2, b::r));
where addnode is the given function from the question. But I cannot think of a way to use this function. Also, I do not know why my solution doesn't work....
I imagine if I have to use the given function, I would need to perform n mod 2 such that if n is even, then I need to recursively call functionalarray to create a new branch on the left, and if n mod 2 = 1 and n is odd, then I create a new branch on the right. However, if I do this, then I do not know what to place on the left or right of the branch. For example, I could call something like
if n mod 2 = 0 then Branch(a, functionalarray(n div 2, r), ...
but I won't be using addnode and I don't know what I should put on the right of the branch.
Any help is very, very appreciated...
The addnode function inserts a new element at the leftmost position in the tree, i.e., as the first element of the array it represents. By doing so, all existing elements are effectively shifted up one index in the resulting array. So all you need to do is iterate over the input list from right to left and apply addnode for each element, starting with an empty array. Hint: this is a one-liner with List.foldr.
Of course, the question is odd in the sense that this approach inevitably creates a degenerate tree that is as unbalanced as it can get, and hence no more efficient than using a plain list to represent the array.