Open leadermaxone opened 6 years ago
In my understanding of the exercise, and I quote the exercise text, reversing a tree means
“reversing” all the values in the leaves
and not having a tree which is symmetrical to the input one.
Therefore, I believe that Nil
should not be taken into account. Nil
in my opinion stands for there's no branch here, it shouldn't be considered as a value.
So the solution should be correct as, by construction, all the leaves' values appear in reverse order.
I agree with @leonardoarcari , i think Nil has no value, is a nullary data constructor and it should stay where it is.
If you check the example, the returned tree is isomorphic to the input one, and only the values are reversed.
Moreover, in 1.3 there's no mention of it. Did you try the proposed solution?
yes of course,
Unless I understood something wrong, the revtree of a tree like
let t3 = (Branch (Branch (Leaf 3) (Leaf 4)) (Branch Nil (Leaf 5)))
should be
(Branch (Branch (Leaf 5) Nil) (Branch (Leaf 4) (Leaf 3)))
while the above solution gives
Branch (Branch (Leaf 5) (Leaf 4)) (Branch Nil (Leaf 3))
this was executed with the proposed solution. It's only that, in my mind,when i tried reversing t3 as mentioned I treated Nil as a value and swapped it around as well (on paper).
With the proposed solution t3 reversed is not isomorphic anymore...but probably my definition of isomorphism is wrong because it takes into account Values and Nil as well.
Anyways, it appears I was making the problem more difficult than what it was. Thanks!
In class we saw this exercise taken from the above mentioned exam
we solved it this way
Unless I understood something wrong, the revtree of a tree like
should be
while the above solution gives
and this is because in revtree' whenever we pattern match a (Nil,xs) we substitute it with (Nil,xs) which doesn't work when the Nil is not in a symmetrical position.
how can we solve this issue?
It would suffice to write down Nil in our list given by tfringe whenever it is matched (and not []), but Nil is of type Tree, not of type a and the compiler gives an error on types when trying to build a list of a
I remember it being addressed in class but missed the answer. Any help would be appreciated, Thanks.