Haskell - find path to value of nodes

Question

The question for this problem is:

Tree holds data of type a. Function findpath which given a function f, some data x and a tree t, returns the lists of paths (possibly empty) in t to the nodes of the form Node d where f d is equal to x.

Declared structure of data types used in this problem:

data Btree a = ND | Data a |  Branch (Btree a) (Btree a)
           deriving (Show,Eq)

data Dir = L | R 
       deriving (Show,Eq)

type Path =  [Dir]

My attempt to solve this function:

findpath :: Eq b => (a -> b) -> b -> Btree a -> [Path]
findpath f x (Data d)                = [[]]
findpath f x ND                      = [[]]
findpath f x (Branch (Data d) right) = [[L]] ++ (findpath f x right)
findpath f x (Branch left (Data d))  = [[R]] ++ (findpath f x left)

Data used for testing:

tree1 = Branch ND ND
tree2 = Branch ND (Data 3)
tree3 = Branch tree1 tree2

A function call to test the function:

1. findpath (2*) 3 tree2
2. findpath (2*) 2 tree2
3. findpath (2*) 3 tree1

The output it gives is:

1. [[R],[]]
2. [[R],[]] - incorrect
3. Throws exception

Any help on the findpath function will be highly appreciated.

In the case `findpath f x (Data d)` don't you need to check whether `f d == x` ? Otherwise, `f` and `x` are never used! This is not the only issue, but you can start fixing this. — chi, Mar 12 '19 at 14:26
Well, you start with the problem that your list of paths can _never_ be empty because none of your functions actually return an empty list. So you violate your own specification right away. You also never actually check if your `x` is equal to your `d`, so of course the paths you get are wrong. — Cubic, Mar 12 '19 at 14:27
This question is much improved compared to your previous draft, nice work! — Daniel Wagner, Mar 12 '19 at 15:06
Thank you for the replies. I will amend my code using these recommendations. — Mantas Astra, Mar 12 '19 at 15:34
As a hint try to handle the general case `findpath f x (Branch left right)` where `left` and `right` can be arbitrary subtrees. Right now you require that one of them is `Data ...`, which is not always the case. You need to use recursion and carefully add some `L` or `R` in the right places. Likely some concatenation of lists will be useful. It's not trivial when you are a beginner, so don't panic if you can't see the solution at first. — chi, Mar 12 '19 at 15:43
By the way, on a complete tangent, I think the spec for this function isn't so great. I'd much prefer the type signature `findpath :: (a -> Bool) -> Btree a -> [Path]`, and replace "where f d is equal to x" in the spec with "where f d is True". This way callers can use other predicates than exact equality if they like. Of course, the two forms of `findpath` are easily interconvertible by `findpathDA f x = findpathDW ((x==) . f)` and `findpathDW p = findpathDA p True`, but still. — Daniel Wagner, Mar 12 '19 at 17:53
Thank you for your insight. It makes the function even better. — Mantas Astra, Mar 12 '19 at 17:56
I thought at first that you might be able to apply https://stackoverflow.com/questions/36474647/haskell-depth-for-each-node-in-binary-tree-using-reader-monad here, but your type of tree is different enough that the trick in that answer won't work. The machinery you need to transfer that idea to this situation is rather too much for a Stack Overflow answer, but would probably make a good blog post! — Benjamin Hodgson, Mar 12 '19 at 19:56

Daniel Wagner · Accepted Answer · 2019-03-12T19:12:30.977

Let's take things one case at a time, using exactly the cases from the data definition of Btree. That is, since

data Btree a = ND | Data a | Branch (Btree a) (Btree a)

then we will consider exactly the following shapes of trees, and no others:

ND
Data d
Branch l r

Let's begin.

findpath f x ND = {- TODO -}

Recall the specification:

Function findpath which given a function f, some data x and a tree t, returns the list of paths (possibly empty) in t to the nodes of the form Data d where f d is equal to x.

(I've assumed where you wrote "Node d", you meant "Data d", to align with your definition of trees, and changed "lists" to "list".)

In the current case, we have f and x as described, and t = ND. Substituting these in the description of what we should return, we get:

the list of paths in ND to the nodes of the form Data d where ...

Since ND does not contain any nodes of the form Data d, there are no such paths. So:

findpath f x ND = []

Next case:

findpath f x (Data d) = {- TODO -}

Now we have t = Data d. Revising the spec again, we must return

the list of paths in Data d to the nodes of the form Data d where f d is equal to x.

Okay, well, then we must check whether f d is equal to x or not, hey?

findpath f x (Data d) = if f d == x
    then {- TODO -}
    else {- TODO -}

If f d == x, then there's exactly one path to a node of the form Data d where f d is equal to x -- namely, the empty path. If not f d == x, then there's no such paths. So:

findpath f x (Data d) = if f d == x
    then [[]]
    else []

And the last case:

findpath f x (Branch l r) = {- TODO -}

Revising the specification once again, now with t = Branch l r, we must return

the list of paths in Branch l r to the nodes of the form Data d where f d is equal to x.

Now you may feel a little bit stuck. After all, l and r are so general, that it's hard to know whether there are paths into them to nodes of the form Data d, right? So how can you discover whether there's a path into Branch l r that eventually ends at a Data d node? Of course, if there were only a way to find out the answer to those two subquestions, perhaps we could augment those paths, hey?

Luckily, we have a function that answers the subquestion: findpath itself. So let's answer the subquestions, and then think about what to do.

findpath f x (Branch l r) = {- TODO -} where
    pathsInL = findpath f x l
    pathsInR = findpath f x r

Okay, so we have some paths in the tree l that lead to nodes of the form Data d where f x is equal to d (respectively, some paths in the tree r). How can we transform those paths to be paths in the tree Branch l r? Easy: by prepending L (respectively, R) to each of the paths. Then we can combine the two collections of paths together.

At this point I am going to stop providing code: I think the key missing insight for you should already be above in the recursive skeleton provided. However, I will suggest some functions that you may find helpful while fleshing out the last little bits of the skeleton:

(:) can be used to prepend a new Dir to a Path.
map can be used to upgrade a function which modifies a single Path into one that modifies an entire list of Paths.
(++) can be used to concatenate two lists of Paths, producing a single list that has all the elements of each of its two arguments.

Give it a shot, and let us know where you next get stuck!

@DrAnonymous Hah, whoops! I didn't quite transliterate the spec into code correctly in the `Data d` case. Can you spot the bug? =) — Daniel Wagner, Mar 12 '19 at 17:30
So the bug is in the "if f x == d" namely "x". I believe that it has something to do with Eq function and therefore, in this case, x type is not the same as Data d type. But I have no idea how to fix this. I kept staring at the code for the past hour :D — Mantas Astra, Mar 12 '19 at 17:33
@DrAnonymous I'll give you a very strong hint: spec says "f d is equal to x", code says `f x == d`. — Daniel Wagner, Mar 12 '19 at 17:34
I thought about it and implemented it before. This got rid of the error but now every time I test the function it outputs empty list "[]". So now I believe that there is an issue somewhere else in my code. Anyway, thank you for helping me! — Mantas Astra, Mar 12 '19 at 17:37
@DrAnonymous Do you believe the empty list result is incorrect? For what call? What do you believe the correct result is? — Daniel Wagner, Mar 12 '19 at 17:39
Let us [continue this discussion in chat](https://chat.stackoverflow.com/rooms/189901/discussion-between-dr-anonymous-and-daniel-wagner). — Mantas Astra, Mar 12 '19 at 17:39

Haskell - find path to value of nodes

1 Answers1