%%usage of testcases: simply typing in <name>(). and it should be true %%testcases only show that one example works, you should create more of them for yourself! %%So there is no guarantee that these testcases ensure that your implementation is correct! %%==========Problem 1.1=============== %TODO: implement removeDuplicates(List,ListWithoutDuplicates) delete([],_,[]). delete([X],X,[]). delete([Head|Tail],Head,Result):- delete(Tail,Head,Result). delete([Head|Tail],X,[Head|Result]):- Head \= X, delete(Tail,X,Result). removeDuplicates([],[]). removeDuplicates([Head|Tail],[Head|Tail2]):- delete(Tail,Head,Result), removeDuplicates(Result,Tail2). %testcase testcase_remove():- removeDuplicates([1,1,1,1,2,2,3,4,1,2,7],[1, 2, 3, 4, 7]). %-------------------------------------------------------------------- %TODO: implement myReverse(List,ReversedList) append([],List2,List2). append([Head|Tail],List2,[Head|Result]):- append(Tail,List2,Result). myReverse([],[]). myReverse([Head|Tail],ReversedList):- myReverse(Tail,TempList), append(TempList,[Head],ReversedList). %testcase testcase_reverse():- myReverse([1,2,3,4,5],[5,4,3,2,1]). %-------------------------------------------------------------------- %TODO: implement myPermutations(List,OnePossiblePermutationOfList) %note: by re-evaluating the function (using the space bar or ";"), one gets all possible permutations buildRandom(List,Element,[Element|List]). buildRandom([Head|Tail],Element,[Head|ResultList]):- buildRandom(Tail,Element,ResultList). myPermutations([],[]). myPermutations([Head|Tail],Result):- myPermutations(Tail,TempList), buildRandom(TempList,Head,Result). %testcase: testcase_permut(X):- myPermutations([1,2,3,4],X). %confirm yourself that your implementation outputs all 16 permutations and produces no doubles %-------------------------------------------------------------------- %TODO: implement zip(ListA,ListB,ZippedList) % the length difference of ListA and ListB is at most 1 % ZippedList is a list of Lists with length 2 (the last element may have length 1) zip([X],[],[[X]]). zip([],[X],[[X]]). zip([A],[B],[[A,B]]). zip([Head1|Tail1],[Head2|Tail2],Result):- zip(Tail1,Tail2,TempList), append([[Head1,Head2]],TempList,Result). %testcase testcase_zip():- zip([1,2],[3,4,5],[[1,3],[2,4],[5]]). %%==========Problem 1.2=============== %Please see the exercise sheet for detailed instructions about what these functions do tree(nil). tree(_,L,R):- tree(L), tree(R). %TODO implement construct(List,Tree) construct(List,Tree):- insert(List,nil,Tree). insert([],Tree,Tree). insert([Head|Tail],TempTree,Tree):- insert_help(Head,TempTree,NewTempTree), insert(Tail,NewTempTree,Tree). insert_help(X, nil, tree(X,nil,nil)). insert_help(X,tree(Y,L,R), tree(Y,L,NewTree)):- X>Y, insert_help(X,R,NewTree). insert_help(X,tree(Y,L,R), tree(Y,NewTree,R)):- X<Y, insert_help(X,L,NewTree). %testcase testcase_construct():- construct([5,2,4,1,3],tree(5,tree(2,tree(1,nil,nil),tree(4,tree(3,nil,nil),nil)),nil)). %-------------------------------------------------------------------- %TODO: implement count_leaves(Tree,NumberOfLeaves) count_leaves(nil,0). count_leaves(tree(_,nil,nil),1):-!. count_leaves(tree(_,L,R),Result):- count_leaves(L,Temp1), count_leaves(R,Temp2), Result is Temp1 + Temp2. %testcase testcase_count():- count_leaves(tree(3,tree(1,nil,tree(2,nil,nil)),nil),1). %TODO: Use it to test how cost efficient your previous function is (in terms of the % structure that you obtain). What can you observe for larger lists of numbers? % Answer these questions as a comment or hand in a separate file %-------------------------------------------------------------------- %TODO: implement symmetric(Tree) that is true, if the Tree is symmetric %symmetric(tree(_,nil,nil)). symmetric(tree(_,L,R)):- mirrored(L,R). mirrored(nil,nil). mirrored(tree(_,L1,R1), tree(_,L2,R2)):- mirrored(L1,R2), mirrored(R1,L2). %testcase testcase_symm():- construct([5,2,3,7,6],X), symmetric(X). %========================================= %% total test test(X):- testcase_remove(), testcase_reverse(), testcase_zip(), testcase_construct(), testcase_count(), testcase_symm(), writeln("everything correct up to myPermutations,"), writeln("now all permutations of [1,2,3,4]:"), testcase_permut(X).