How palindrome check in prolog works?

Question

I have a question about how Prolog works. I never studied Prolog, but the time has come to face that language. I searched a piece of code for palindrome check and I found this

pal([]).
pal([_]).
pal(Pal) :-
   append([H|T], [H], Pal),
   pal(T).

For example I call pal([abccba]). and pal([abcdba]).. I understand how it works (it takes the head and the tail - 1 and appends the head to the tail's end). However, I don't understand why when the pal(T) is called with [c, c] the result is true, but when it's called with [c, d] it fails on append?

Can anyone explain to me how it works?

Did you try stepping through it? `pal([c,d])` query won't match `pal([])` or `pal([_])` but will match `pal(Pal)` with `Pal = [c,d]`. Then `append([H|T], [H], [c,d])` will fail because `append` cannot find an `H` such that `[H|T]` appended to `[H]` yields `[c,d]`. That is, there's not a list that looks like, `[H, ..., H]` which can be unified with `[c,d]`. So the entire predicate fails. — lurker, Jan 17 '17 at 21:27
I stepped through it and the trick is when the `Pal = [c, c]` in append it looks like this, `append([H|T] = [c], [H] = [c], Pal = [c, c])` so, if it takes only the head why it didn't work on `Pal = [c, d]` this must to take only the head that is `[c]`, sincerely i don't understand . — Frederick Castello, Jan 17 '17 at 21:32
`append([H|T], [H], [c, d])` has two occurrences of `H`, so (in a sense) it puts two constraints on its value. This asks if there is an `H` that is both the first and the last element of `[c, d]`. There isn't. `H` cannot be both `c` and `d` at the same time. — Isabelle Newbie, Jan 17 '17 at 21:37
I explained in my comment why it doesn't work with `Pal = [c, d]`. You must think about what `append` means. `append(A, B, C)` means you can get `C` if you append `B` to `A`. However, in your palindrome predicate, you are *constraining* `A` and `B` to be `[H|T]` and `[H]`. Note that `H` cannot have two different values at the same time. So this says `[c, d]` would need to match `[H]` appended to `[H|T]`, which looks like `[H, ..., H]`. What value for `H` would allow `[H, ..., H]` match `[c, d]` even if `...` is nothing? — lurker, Jan 17 '17 at 21:41
@DavidBrossard, I do not believe this is a duplicate of the linked question. This question is asking *why* a particular implementation works. The linked question shows a few different solutions, none of which exactly match the solution in this question and do not offer an answer to the OP's question. — lurker, Jan 17 '17 at 21:43
@DavidBrossard the comment below the post says, "**marked** as duplicate by David Brossard, ..." — lurker, Jan 17 '17 at 22:20

How palindrome check in prolog works?

0 Answers0