Algorithms and Data Structures Wiki

List process- handling sequences of elements - is a powerful technique in prolog.

Prolog uses brackets [...] as list builder. The notation [X|Y] represents a list whose first element is X and Y as its tail. A finite list can be explicitly enumerated, such as, [1,2,3,4].

Declaring lists[]

Here is how you declare a domain for list of integers.

domains
     list=integer*

Similarly you may also declare symbol* or real*.

Predicates[]

member(integer,list)

delete(integer,list,list)

append(list,list,list)

reverse(list,list)

perm(list,list)

subset(list,list)

union(list,list,list)

intersection(list,list,list)

mergesort(list,list)

split(list,list,list)

merge(list,list,list)

Clauses[]

member(X,[X|R]).

member(X,[Y|R]):-X<>Y,member(X,R).

delete(X,[X|R],R).

delete(X,[H|T],[H|S]):-delete(X,T,S).

append([],X,X).

append([H|T],Z,[H|S]):-append(T,Z,S).

reverse([],[]).

reverse([H|X],Y):-reverse(X,Z),append(Z,[H],Y).

perm([],[]).

perm([X|Y],Z):-perm(Y,W),delete(X,Z,W).

subset([],_).

subset([H|T],S):-member(H,S),subset(T,S).

union([],Z,Z).

union([H|T],X,Y):-member(H,X),union(T,X,Y).

union([H|T],X,[H|Y]):-not(member(H,X)),union(T,X,Y).

intersection([],X,[]).

intersection([H|T],X,[H|Y]):-member(H,X),intersection(T,X,Y).

intersection([H|T],X,Y):-not(member(H,X)),intersection(T,X,Y).

mergesort([],[]).

mergesort([A],[A]).

mergesort([A,B|T],S):-split([A,B|T],L1,L2),mergesort(L1,S1),mergesort(L2,S2),merge(S1,S2,S)

split([],[],[]).

split([A],[A],[]).

split([A,B|R],[A|Ra],[B|Rb]):-split(R,Ra,Rb).

merge(A,[],A).

merge([],B,B).

merge([A|Ra],[B|Rb],[A|M]):-A=<B,merge(Ra,[B|Rb],M).

merge([A|Ra],[B|Rb],[B|M]):-A>B,merge([A|Ra],Rb,M).