TdE 20170705

[leadermaxone]

In class we saw this exercise taken from the above mentioned exam

-- 2) Define a purely functional (i.e. non destructive)
-- version of the reverse presented in Es. 1.3.
-- which takes a binary tree and keeps
-- it structure, but “reversing” all the values in the leaves
-- E.g.

-- t1 = Branch (Branch (Leaf 1) (Leaf 2)) (Leaf 3),
-- E.g. revtree t1 is Branch (Branch (Leaf 3) (Leaf 2)) (Leaf 1).

we solved it this way

tfringe :: Tree a -> [a]
tfringe Nil = []
tfringe (Leaf v) = [v]
tfringe (Branch l r) = (tfringe r) ++ (tfringe l)

revtree :: Tree a -> Tree a
revtree t1 = a where 
	(a,_) = revtree' t1 (tfringe t1) where
		revtree' :: Tree a -> [a] -> (Tree a, [a])
		revtree' Nil xs = (Nil,xs)
		revtree' (Leaf v) (x:xs) = ((Leaf x),xs)
		revtree' (Branch l r) xs = let (l', xs') = revtree' l xs;
									   (r', xs'') = revtree' r xs'
								    in ((Branch l' r'),xs'')

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))

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.

[leonardoarcari]

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.

[riccardotommasini]

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?

[leadermaxone]

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!