% week04.pl

% ALAIN V. DE LARA

%###############################################################################

%###############################################################################

/*###############################################################################

#################################################################################

QUESTION 1

----------

zipUnzip([1,2,3],[a,b,c],[X,Y,Z])==>

X = 1-a

Y = 2-b

Z = 3-c

#################################################################################

###############################################################################*/

zipunzip([],[],[]).

zipunzip([A|AT],[B|BT],[A-B|LT]):-zipunzip(AT,BT,LT).

/*###############################################################################

#################################################################################

QUESTION 2

----------

Define your versions of the build-in predicates:

-length/2,

-sort/2,

-msort/2,

-merge/3,

-merge_set/3.

Name your functions:

-my_length/2,

-my_sort/2,

-my_msort/2,

-my_merge/3,

-my_merge_set/3.

#################################################################################

###############################################################################*/

my_len([],0).

my_len([L|LS],NumElem):-my_len(LS,N), NumElem is N+1.

takesublist([X|_],[X],1,1).

takesublist([X|Xs],[X|Ys],1,K):-K>1,

K1 is K-1,

takesublist(Xs,Ys,1,K1).

takesublist([_|Xs],Ys,I,K):-I>1,

I1 is I-1,

K1 is K-1,

takesublist(Xs,Ys,I1,K1).

even(X):-M is mod(X,2),

M = 0.

my_splithalf(S,L1,L2):-my_len(S,K),

not(even(K)),

M is truncate(K/2)+1,

M<K,

takesublist(S,L1,1,M),

takesublist(S,L2,M+1,K),!.

my_splithalf(S,L1,L2):-my_len(S,K),

even(K),

M is truncate(K/2),

M<K,

takesublist(S,L1,1,M),

takesublist(S,L2,M+1,K).

my_merge( [], L, L ).

my_merge( L,[], L ).

my_merge( [F|FS], [S|SS], [F|M]) :- F =< S, my_merge( FS ,[S|SS] , M ).

my_merge( [F|FS], [S|SS], [S|M]) :- F > S, my_merge( [F|FS], SS , M ).

% remove adjacent redundancy

% good for already sorted list

% remredun([6,6,7,7,7,8,8,8,8],X)==>X=[6,7,8]

remredun([],[]).

remredun([X],[X]).

remredun([X,X|Xs],Zs) :- remredun([X|Xs],Zs).

remredun([X,Y|Ys],[X|Zs]) :- X\=Y, remredun([Y|Ys],Zs).

my_sortpre([],[]).

my_sortpre([E],[E]).

my_sortpre([A,B|T],S):-my_splithalf([A,B|T],L1,L2),

my_sortpre(L1,S1),

my_sortpre(L2,S2),

my_merge(S1,S2,S).

my_sort(UL,FinalList):-my_sortpre(UL,TempList),

remredun(TempList,FinalList).

my_msort(L,S):-my_sortpre(L,S).

% my "my_merge" does the same as merge_set

my_merge_set(L1,L2,F):-my_merge(L1,L2,F).

/*###############################################################################

#################################################################################

QUESTION 3

----------

range(a, b, L)===>

L=[a,a+1,a+2,.....b-2,b-1,b]

#################################################################################

###############################################################################*/

/*-----------------------------------------

range(H,H,[]).

range( Low , Hig , [L1|LT] ):- Low < Hig,

L1 is Low+1,

range(L1,Hig,LT).

%BUGGED :

%range(1,9,X) ==> X=[2,3,4,5,6,7,8,9]

--------------------------------------------*/

range(H,H,[H]).

range( Low , Hig , [P1|LT] ):- Low < Hig,

L1 is Low+1,

P1 is L1-1,

range(L1,Hig,LT).

/*###############################################################################

#################################################################################

QUESTION 4

?- is_range(A, B, [1, 2, 3, 4])==> A=1 and B=4

?- is_range(A, B, [4, 5, 7]) ==> No

#################################################################################

###############################################################################*/

% mylast(List,L):-reverse(List,[L|LT]).

mylast(X,[X]).

mylast(X,[_|L]):-mylast(X,L).

myfirst([X|_],F):- F is X.

%----- using range defined previously -----

is_range(L,H,List):- myfirst(List,Low),

mylast(List,Hig),

range(Low,Hig,Genlist),

List=Genlist,

L is Low,

H is Hig.

/*###############################################################################

#################################################################################

QUESTION 5

Use two calls to append/3 and a test for the empty list to define

is_subsequence(?Sub, +Seq), which succeeds if Sub unifies with any

non-empty subsequence of Seq, including Seq itself.

?- is_subsequence(Sub, [4, 5, 6, 7]).

Sub = [4] ;

Sub = [4, 5] ;

Sub = [4, 5, 6] ;

Sub = [4, 5, 6, 7] ;

Sub = [5] ;

Sub = [5, 6] ;

Sub = [5, 6, 7] ;

Sub = [6] ;

Sub = [6, 7] ;

Sub = [7] ;

No

#################################################################################

###############################################################################*/

/*------------------------------------------

?- append([1,2,3],[4,5,6],Z).

Z = [1, 2, 3, 4, 5, 6];

No

STEP 1: obtain the Prefixes

?- append(X,_,[1,2,3,4,5,6]).

X = [] ;

X = [1] ;

X = [1, 2] ;

X = [1, 2, 3] ;

X = [1, 2, 3, 4] ;

X = [1, 2, 3, 4, 5] ;

X = [1, 2, 3, 4, 5, 6] ;

No

STEP 2: obtain the Suffixes from the prefixes

?- append(_,Y,[1,2,3,4,5,6]).

Y = [1, 2, 3, 4, 5, 6] ;

Y = [2, 3, 4, 5, 6] ;

Y = [3, 4, 5, 6] ;

Y = [4, 5, 6] ;

Y = [5, 6] ;

Y = [6] ;

Y = [] ;

No

------------------------------------------*/

/*****************************************

is_subseq(X,List):- append(_,X,Temp),

append(Temp,_,List),

X\=[].

% the code above is bugged==> ERROR: Out of global stack

******************************************/

is_subseq(X,List):- append(Temp,_,List),

append(_,X,Temp),

X\=[].

/*###############################################################################

#################################################################################

#################################################################################

###############################################################################*/