what does the follow prolog codes do? -

what does the follow prolog codes do? -

i having problem understanding codes below. can explain step step happening if have follow input:

append([1,2,3], lst).

actually, don;t how 1 , 2 appended list lst result.

append([_], []). append([h|t], [h|n]) :- append(t,n).

it sounds you're new prolog. if so, welcome! let's analyze this.

this unfortunately-named function has 2 clauses. prolog looks @ clauses in order see 1 applies. when finds 1 matches, tries perform it. if there's failure somewhere in performing it, , seek next option. exactly these choice points varies depending on program; in program, 1 @ clause level, deciding rule use.

one way of looking @ first rule is saying "a list 1 element, regardless of element is, related empty list." looking @ append([_], []), if had x = [foo] , y = [], hold, because [foo] one-item list , [] empty list. rule prolog style, because work regardless of instantiation: supply left or right or neither, doesn't matter.

the sec clause quite simple. says left argument , right argument related if both start same item, , if rest of lists related same predicate. in other words, if have 2 lists x , y such append(x, y) true, append([h|x], [h|y]) true. doesn't matter h , doesn't matter x , y are, except insofar implied append/2.

thinking logically, if know one-item list related empty list, , list related list starts same item , otherwise same, kinds of lists can related lists every item same, except left list has 1 more item in @ end not nowadays on right. [1,2,3,4] related [1,2,3], [1,2,3,foo] , [1,2,3].

procedurally, let's @ happens predicate processed set of arguments:

append([1,2,3], x).

the first rule won't match on [1,2,3]. must @ sec rule:

append([1|[2,3]], [1|x]) :- append([2,3], x).

we can repeat:

append([2|[3]], [2|y]) :- append([3], y).

now first rule does match:

append([3], []).

so putting together:

append([1,2,3], [1|x]) implies append([2,3], x=[2|y]) implies append([3], y=[]) y = [] x = [2] right side [1,2].

a prolog trace show same information:

?- trace, append([1,2,3], x). call: (7) append([1, 2, 3], _g1633) ? creep call: (8) append([2, 3], _g1752) ? creep call: (9) append([3], _g1755) ? creep exit: (9) append([3], []) ? creep exit: (8) append([2, 3], [2]) ? creep exit: (7) append([1, 2, 3], [1, 2]) ? creep

what makes prolog code confusing doesn't you've told prolog how anything. , it's true, haven't, specifying true logically, prolog able figure out itself. pretty clever code. if haskell, we'd talking built-in function init, returns of list lastly item.

hope helps!

prolog