How to equate lists in prolog?

Question

I have the following code, which flattens a tree into a list

tree_list(leaf(Leaf)) --> [Leaf].
tree_list(node1(Leaf, Node)) -->
        [Leaf],
        tree_list(Node).
tree_list(node2(Leaf, Node1, Node2)) -->
        tree_list(Node1),
        [Leaf],
        tree_list(Node2).
tree_list(node3(_, Node1, Node2, Node3)) -->
        tree_list(Node1),
        tree_list(Node2),
        tree_list(Node3).

Sample query and answer:

?- phrase(tree_list(node3(1,
                     node1(2, leaf(1)),
                     node2(3, leaf(1), leaf(1)),
                     node1(4, leaf(1)))), Ls).
Ls = [2, 1, 1, 3, 1, 4, 1].

I wrote a piece of code which matches to see if two lists have the same list of elements.

treeMatch([], []).
treeMatch([Th| Tt], [Ah| At]) :- Th is Ah, treeMatch(Tt, At).

The above simply goes through a list, checking to see that each index from both lists have the same element till they hit the empty list.

Trying the code with treeMatch([2, 1, 1, 3, 1, 4, 1], [2, 1, 1, 3, 1, 4, 1]) returns true.

But, if I try it with

treeMatch([2, 1, 1, 3, 1, 4, 1], phrase(tree_list(node3(1,
                     node1(2, leaf(1)),
                     node2(3, leaf(1), leaf(1)),
                     node1(4, leaf(1)))), Ls)).

I get false. Is there a way to retrieve the value of Ls and insert it directly to treeMatch to allow it to work?

You talk about treeMatch checking if the lists have the same elements. But using is/2, you check if Ah arithmetically evaluates to Th. Therefore treeMatch([2], [1+1]) will succeed, but neither will treeMatch(X,foo) nor treeMatch(2,X) (the first because foo is no arithmetic expression and the second because evaluation can only be done on ground terms). Is this the expected behaviour? My suspicion is that you actually want to check L1 = L2. — lambda.xy.x
– lambda.xy.x, Commented Dec 6, 2016 at 14:28

max66 · Accepted Answer · 2016-12-05 21:22:08Z

1

You're calling threeMatch/2 in a wrong mode.

If you call

treeMatch([2, 1, 1, 3, 1, 4, 1], phrase(tree_list(node3(1,
                     node1(2, leaf(1)),
                     node2(3, leaf(1), leaf(1)),
                     node1(4, leaf(1)))), Ls))

you ask if the list [2, 1, 1, 3, 1, 4, 1] is equal to the struct phrase(tree_list(node3..., not if it's equal to Ls.

You should split the call in 2 calls, as follows

phrase(tree_list(node3(1,
                       node1(2, leaf(1)),
                       node2(3, leaf(1), leaf(1)),
                       node1(4, leaf(1)))), Ls),
treeMatch([2, 1, 1, 3, 1, 4, 1], Ls)

so the first call (phrase/2) unifies Ls with [2, 1, 1, 3, 1, 4, 1] and treeMatch/2 verifies that [2, 1, 1, 3, 1, 4, 1] match with Ls.

-- EDIT --

The OP write

I tried it with your method and got ?- treeMatch([2, 3, 4], E). ERROR: user://3:74: is/2: Arguments are not sufficiently instantiated .

Suggestion: call treeMatch(E, [2, 3, 4]) or (better, I suppose) modify treeMatch/2 as follows

treeMatch([H | Tt], [H | At]) :- treeMatch(Tt, At).

If you use is/2 (Th is Ah) you impose one direction in your clause: the first argument can be unified with the value of the second but the second can't be unified with the value of the first.

edited Dec 5, 2016 at 21:22

answered Dec 5, 2016 at 19:06

max66

67k11 gold badges76 silver badges121 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Andrew Over a year ago

I tried it with your method and got ?- treeMatch([2, 3, 4], E). ERROR: user://3:74: is/2: Arguments are not sufficiently instantiated . Does that mean that E was not unified to [2, 3, 4]?

max66 Over a year ago

@AndrewRaleigh - improved my answer; hope this helps.

Collectives™ on Stack Overflow

How to equate lists in prolog?

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related