From 732b8f42029eced5e53debbff367131c2ea366ee Mon Sep 17 00:00:00 2001 From: Timotej Lazar Date: Sun, 3 Apr 2016 18:11:08 +0200 Subject: Prolog: add introduction for the sets group and make it visible --- prolog/problems/lists_advanced/count_3/common.py | 96 ------- prolog/problems/lists_advanced/count_3/en.py | 11 - prolog/problems/lists_advanced/count_3/sl.py | 45 --- prolog/problems/sets/count_3/common.py | 96 +++++++ prolog/problems/sets/count_3/en.py | 11 + prolog/problems/sets/count_3/sl.py | 45 +++ prolog/problems/sets/diff_3/common.py | 4 +- prolog/problems/sets/famrel.svg | 343 +++++++++++++++++++++++ prolog/problems/sets/intersect_3/common.py | 4 +- prolog/problems/sets/intro_sl.html | 281 +++++++++++++++++++ prolog/problems/sets/is_subset_2/common.py | 4 +- prolog/problems/sets/is_superset_2/common.py | 4 +- prolog/problems/sets/powerset_2/common.py | 4 +- prolog/problems/sets/sl.py | 8 +- prolog/problems/sets/subset_2/common.py | 4 +- prolog/problems/sets/union_3/common.py | 4 +- 16 files changed, 797 insertions(+), 167 deletions(-) delete mode 100644 prolog/problems/lists_advanced/count_3/common.py delete mode 100644 prolog/problems/lists_advanced/count_3/en.py delete mode 100644 prolog/problems/lists_advanced/count_3/sl.py create mode 100644 prolog/problems/sets/count_3/common.py create mode 100644 prolog/problems/sets/count_3/en.py create mode 100644 prolog/problems/sets/count_3/sl.py create mode 100644 prolog/problems/sets/famrel.svg create mode 100644 prolog/problems/sets/intro_sl.html diff --git a/prolog/problems/lists_advanced/count_3/common.py b/prolog/problems/lists_advanced/count_3/common.py deleted file mode 100644 index 7d66d6b..0000000 --- a/prolog/problems/lists_advanced/count_3/common.py +++ /dev/null @@ -1,96 +0,0 @@ -from operator import itemgetter -import socket - -import prolog.engine -import prolog.util -from server.hints import Hint, HintPopup - -id = 120 -number = 110 -visible = False -facts = None - -solution = '''\ -count(_, [], 0). -count(X, [X|T], N) :- - count(X, T, NT), - N is NT + 1. -count(X, [Y|T], NT) :- - X \== Y, - count(X, T, NT). -''' - -hint_type = { - 'eq_instead_of_equ_markup': HintPopup('eq_instead_of_equ_markup'), - 'eq_instead_of_equ': Hint('eq_instead_of_equ'), - 'predicate_always_false': Hint('predicate_always_false'), - 'base_case': Hint('base_case'), - 'recursive_case': Hint('recursive_case'), - 'timeout': Hint('timeout'), -} - -test_cases = [ - ('count(a, [], X)', - [{'X': '0'}]), - ('count(r, [a, r, b, c, r], X)', - [{'X': '2'}]), - ('count(l, [l, l, l, 1, 2, 3], X)', - [{'X': '3'}]), - ('count(z, [a, b, c, z, z], X)', - [{'X': '2'}]), -] - -def test(code, aux_code): - n_correct = 0 - engine_id = None - try: - engine_id, output = prolog.engine.create(code=code+aux_code, timeout=1.0) - if engine_id is not None and 'error' not in map(itemgetter(0), output): - # Engine successfully created, and no syntax error in program. - for query, answers in test_cases: - if prolog.engine.check_answers(engine_id, query=query, answers=answers, timeout=1.0): - n_correct += 1 - except socket.timeout: - pass - finally: - if engine_id: - prolog.engine.destroy(engine_id) - - hints = [{'id': 'test_results', 'args': {'passed': n_correct, 'total': len(test_cases)}}] - return n_correct, len(test_cases), hints - -def hint(code, aux_code): - tokens = prolog.util.tokenize(code) - - try: - engine_id, output = prolog.engine.create(code=code+aux_code, timeout=1.0) - - # strict equality testing instead of simple matching - # this is usually (but not necessarily) wrong - targets = [prolog.util.Token('EQ', '==')] - marks = [(t.pos, t.pos + len(t.val)) for t in tokens if t in targets] - if marks: - return [{'id': 'eq_instead_of_equ_markup', 'start': m[0], 'end': m[1]} for m in marks] + \ - [{'id': 'eq_instead_of_equ'}] - - # missing/failed base case - if not prolog.engine.ask_truthTO(engine_id, 'count(42, [], 0)'): - return [{'id': 'base_case'}] - - # target predicate seems to always be false - if not prolog.engine.ask_truthTO(engine_id, 'count(_, _, _)'): - return [{'id': 'predicate_always_false'}] - - # base case works, the recursive doesn't (but it doesn't timeout) - # this may be left as the last, most generic hint - if not prolog.engine.ask_truth(engine_id, 'count(42, [2, 41, 42, -22, 42], 2)'): - return [{'id': 'recursive_case'}] - - except socket.timeout as ex: - return [{'id': 'timeout'}] - - finally: - if engine_id: - prolog.engine.destroy(engine_id) - - return [] diff --git a/prolog/problems/lists_advanced/count_3/en.py b/prolog/problems/lists_advanced/count_3/en.py deleted file mode 100644 index 481fd1c..0000000 --- a/prolog/problems/lists_advanced/count_3/en.py +++ /dev/null @@ -1,11 +0,0 @@ -name = 'count/3' -slug = 'find the number of occurrences of an element in list' - -description = '''\ -

count(X, L, N): N is the number of times the element X appears in the list L.

-
-?- count(1, [1,2,1,3,1], N).
-  N = 3.
-
''' - -hint = {} diff --git a/prolog/problems/lists_advanced/count_3/sl.py b/prolog/problems/lists_advanced/count_3/sl.py deleted file mode 100644 index 1e3f5d2..0000000 --- a/prolog/problems/lists_advanced/count_3/sl.py +++ /dev/null @@ -1,45 +0,0 @@ -name = 'count/3' -slug = 'Preštej kolikokrat se element pojavi v seznamu' - -description = '''\ -

count(X, L, N): N je število kolikokrat se element X pojavi v seznamu L.

-
-?- count(1, [1,2,1,3,1], N).
-  N = 3.
-
''' - -hint = { - 'eq_instead_of_equ': '''\ -

Operator == je strožji od operatorja = v smislu, da je za slednjega dovolj, -da elementa lahko naredi enaka (unifikacija). Morda z uporabo = narediš predikat -memb/2 delujoč tudi v kakšni drugi smeri.

-

Seveda pa lahko nalogo rešiš brez obeh omenjenih operatorjev, spomni se, da lahko unifikacijo narediš -implicitno že kar v argumentih predikata (glavi stavka).

-''', - - 'eq_instead_of_equ_markup': '''\ -

Morda bi bil bolj primeren operator za unifikacijo (=)?

-''', - - 'base_case': '''\ -

Si pomislil na robni pogoj? Kaj je najbolj enostaven primer, ko je element v seznamu? -Do katerega elementa najlažje prideš?

-''', - - 'recursive_case': '''\ -

Robni primer deluje. Kaj pa rekurzivni, splošni, primer?

-''', - - 'predicate_always_false': '''\ -

Vse kaže, da tvoj predikat vedno vrne "false". Si mu dal pravilno ime, si se morda pri imenu zatipkal?

-

Če je ime pravilno, se morda splača preveriti tudi, če se nisi zatipkal kje drugje, -je morda kakšna pika namesto vejice ali obratno, morda kakšna spremenljivka z malo začetnico?

-

Možno je seveda tudi, da so tvoji pogoji prestrogi ali celo nemogoči (kot bi bila npr. zahteva, -da je X hkrati starš in sestra od Y ali kaj podobno zlobnega).

-''', - - 'timeout': '''\ -

Je morda na delu potencialno neskončna rekurzija? Kako se bo ustavila?

-

Morda pa je kriv tudi manjkajoč, neustrezen ali preprosto nekompatibilen (s splošnim primerom) robni pogoj?

-''', -} diff --git a/prolog/problems/sets/count_3/common.py b/prolog/problems/sets/count_3/common.py new file mode 100644 index 0000000..e770eaa --- /dev/null +++ b/prolog/problems/sets/count_3/common.py @@ -0,0 +1,96 @@ +from operator import itemgetter +import socket + +import prolog.engine +import prolog.util +from server.hints import Hint, HintPopup + +id = 120 +number = 10 +visible = True +facts = None + +solution = '''\ +count(_, [], 0). +count(X, [X|T], N) :- + count(X, T, NT), + N is NT + 1. +count(X, [Y|T], NT) :- + X \== Y, + count(X, T, NT). +''' + +hint_type = { + 'eq_instead_of_equ_markup': HintPopup('eq_instead_of_equ_markup'), + 'eq_instead_of_equ': Hint('eq_instead_of_equ'), + 'predicate_always_false': Hint('predicate_always_false'), + 'base_case': Hint('base_case'), + 'recursive_case': Hint('recursive_case'), + 'timeout': Hint('timeout'), +} + +test_cases = [ + ('count(a, [], X)', + [{'X': '0'}]), + ('count(r, [a, r, b, c, r], X)', + [{'X': '2'}]), + ('count(l, [l, l, l, 1, 2, 3], X)', + [{'X': '3'}]), + ('count(z, [a, b, c, z, z], X)', + [{'X': '2'}]), +] + +def test(code, aux_code): + n_correct = 0 + engine_id = None + try: + engine_id, output = prolog.engine.create(code=code+aux_code, timeout=1.0) + if engine_id is not None and 'error' not in map(itemgetter(0), output): + # Engine successfully created, and no syntax error in program. + for query, answers in test_cases: + if prolog.engine.check_answers(engine_id, query=query, answers=answers, timeout=1.0): + n_correct += 1 + except socket.timeout: + pass + finally: + if engine_id: + prolog.engine.destroy(engine_id) + + hints = [{'id': 'test_results', 'args': {'passed': n_correct, 'total': len(test_cases)}}] + return n_correct, len(test_cases), hints + +def hint(code, aux_code): + tokens = prolog.util.tokenize(code) + + try: + engine_id, output = prolog.engine.create(code=code+aux_code, timeout=1.0) + + # strict equality testing instead of simple matching + # this is usually (but not necessarily) wrong + targets = [prolog.util.Token('EQ', '==')] + marks = [(t.pos, t.pos + len(t.val)) for t in tokens if t in targets] + if marks: + return [{'id': 'eq_instead_of_equ_markup', 'start': m[0], 'end': m[1]} for m in marks] + \ + [{'id': 'eq_instead_of_equ'}] + + # missing/failed base case + if not prolog.engine.ask_truthTO(engine_id, 'count(42, [], 0)'): + return [{'id': 'base_case'}] + + # target predicate seems to always be false + if not prolog.engine.ask_truthTO(engine_id, 'count(_, _, _)'): + return [{'id': 'predicate_always_false'}] + + # base case works, the recursive doesn't (but it doesn't timeout) + # this may be left as the last, most generic hint + if not prolog.engine.ask_truth(engine_id, 'count(42, [2, 41, 42, -22, 42], 2)'): + return [{'id': 'recursive_case'}] + + except socket.timeout as ex: + return [{'id': 'timeout'}] + + finally: + if engine_id: + prolog.engine.destroy(engine_id) + + return [] diff --git a/prolog/problems/sets/count_3/en.py b/prolog/problems/sets/count_3/en.py new file mode 100644 index 0000000..481fd1c --- /dev/null +++ b/prolog/problems/sets/count_3/en.py @@ -0,0 +1,11 @@ +name = 'count/3' +slug = 'find the number of occurrences of an element in list' + +description = '''\ +

count(X, L, N): N is the number of times the element X appears in the list L.

+
+?- count(1, [1,2,1,3,1], N).
+  N = 3.
+
''' + +hint = {} diff --git a/prolog/problems/sets/count_3/sl.py b/prolog/problems/sets/count_3/sl.py new file mode 100644 index 0000000..1e3f5d2 --- /dev/null +++ b/prolog/problems/sets/count_3/sl.py @@ -0,0 +1,45 @@ +name = 'count/3' +slug = 'Preštej kolikokrat se element pojavi v seznamu' + +description = '''\ +

count(X, L, N): N je število kolikokrat se element X pojavi v seznamu L.

+
+?- count(1, [1,2,1,3,1], N).
+  N = 3.
+
''' + +hint = { + 'eq_instead_of_equ': '''\ +

Operator == je strožji od operatorja = v smislu, da je za slednjega dovolj, +da elementa lahko naredi enaka (unifikacija). Morda z uporabo = narediš predikat +memb/2 delujoč tudi v kakšni drugi smeri.

+

Seveda pa lahko nalogo rešiš brez obeh omenjenih operatorjev, spomni se, da lahko unifikacijo narediš +implicitno že kar v argumentih predikata (glavi stavka).

+''', + + 'eq_instead_of_equ_markup': '''\ +

Morda bi bil bolj primeren operator za unifikacijo (=)?

+''', + + 'base_case': '''\ +

Si pomislil na robni pogoj? Kaj je najbolj enostaven primer, ko je element v seznamu? +Do katerega elementa najlažje prideš?

+''', + + 'recursive_case': '''\ +

Robni primer deluje. Kaj pa rekurzivni, splošni, primer?

+''', + + 'predicate_always_false': '''\ +

Vse kaže, da tvoj predikat vedno vrne "false". Si mu dal pravilno ime, si se morda pri imenu zatipkal?

+

Če je ime pravilno, se morda splača preveriti tudi, če se nisi zatipkal kje drugje, +je morda kakšna pika namesto vejice ali obratno, morda kakšna spremenljivka z malo začetnico?

+

Možno je seveda tudi, da so tvoji pogoji prestrogi ali celo nemogoči (kot bi bila npr. zahteva, +da je X hkrati starš in sestra od Y ali kaj podobno zlobnega).

+''', + + 'timeout': '''\ +

Je morda na delu potencialno neskončna rekurzija? Kako se bo ustavila?

+

Morda pa je kriv tudi manjkajoč, neustrezen ali preprosto nekompatibilen (s splošnim primerom) robni pogoj?

+''', +} diff --git a/prolog/problems/sets/diff_3/common.py b/prolog/problems/sets/diff_3/common.py index 1f00d5c..578d203 100644 --- a/prolog/problems/sets/diff_3/common.py +++ b/prolog/problems/sets/diff_3/common.py @@ -5,8 +5,8 @@ import prolog.engine import server.problems id = 130 -number = 37 -visible = False +number = 40 +visible = True facts = None solution = '''\ diff --git a/prolog/problems/sets/famrel.svg b/prolog/problems/sets/famrel.svg new file mode 100644 index 0000000..bff500c --- /dev/null +++ b/prolog/problems/sets/famrel.svg @@ -0,0 +1,343 @@ + + + + + + +famrel + + +tina + +  tina♀ + + +william + +  william♂ + + +tina->william + + + + +sally + +  sally♀ + + +melanie + +  melanie♀ + + +sally->melanie + + + + +andrew + +  andrew♂ + + +sally->andrew + + + + +joanne + +  joanne♀ + + +steve + +  steve♂ + + +joanne->steve + + + + +jill + +  jill♀ + + +jill->joanne + + + + +vanessa + +  vanessa♀ + + +susan + +  susan♀ + + +vanessa->susan + + + + +patricia + +  patricia♀ + + +john + +  john♂ + + +patricia->john + + + + +michelle + +  michelle♀ + + +estelle + +  estelle♀ + + +george + +  george♂ + + +estelle->george + + + + +helen + +  helen♀ + + +jerry + +  jerry♂ + + +helen->jerry + + + + +elaine + +  elaine♀ + + +anna + +  anna♀ + + +elaine->anna + + + + +kramer + +  kramer♂ + + +elaine->kramer + + + + +margaret + +  margaret♀ + + +nevia + +  nevia♀ + + +margaret->nevia + + + + +alessandro + +  alessandro♂ + + +margaret->alessandro + + + + +ana + +  ana♀ + + +aleksander + +  aleksander♂ + + +ana->aleksander + + + + +luana + +  luana♀ + + +nevia->luana + + + + +daniela + +  daniela♀ + + +nevia->daniela + + + + +william->vanessa + + + + +william->patricia + + + + +thomas + +  thomas♂ + + +thomas->sally + + + + +thomas->william + + + + +jeffrey + +  jeffrey♂ + + +thomas->jeffrey + + + + +andrew->joanne + + + + +patrick + +  patrick♂ + + +patrick->susan + + + + +john->michelle + + + + +michael + +  michael♂ + + +john->michael + + + + +frank + +  frank♂ + + +frank->george + + + + +george->kramer + + + + +morty + +  morty♂ + + +morty->jerry + + + + +jerry->anna + + + + +aleksandr + +  aleksandr♂ + + +aleksandr->aleksander + + + + +aleksander->luana + + + + +aleksander->daniela + + + + + diff --git a/prolog/problems/sets/intersect_3/common.py b/prolog/problems/sets/intersect_3/common.py index afece71..78cecb7 100644 --- a/prolog/problems/sets/intersect_3/common.py +++ b/prolog/problems/sets/intersect_3/common.py @@ -5,8 +5,8 @@ import prolog.engine import server.problems id = 129 -number = 36 -visible = False +number = 30 +visible = True facts = None solution = '''\ diff --git a/prolog/problems/sets/intro_sl.html b/prolog/problems/sets/intro_sl.html new file mode 100644 index 0000000..3763628 --- /dev/null +++ b/prolog/problems/sets/intro_sl.html @@ -0,0 +1,281 @@ + + + + + Prolog: negacija in rez + + + + +

Prolog: negacija in rez

+

+Kot ste videli, smo konjunkcijo in disjunkcijo spoznali že takoj v prvem sklopu. +Verjetno ste se že tedaj spraševali, kako je s tretjo, na nek način +komplementarno, logično operacijo, to je negacijo. Tako je, načrtno smo +zavlačevali z njeno predstavitvijo! Boste hitro videli, zakaj. No, sedaj pa je +vendarle napočil čas, da ugriznemo še v to jabolko. +

+ +

Rez (!)

+

+Začnimo z rezom, saj ga bomo kasneje potrebovali za definicijo negacije. Rez v +prologu imenujemo posebej cilj, ki ga označimo s klicajem (!). Ta +cilj vedno uspe (v tem smislu je enak kot true), a ima stranski +učinek. Le-ta je, da prepreči ostale možne alternative. Poglejmo to kar na +primeru. Za hip si spet naložimo dejstva o družinskih drevesih iz prvega sklopa, +da lahko na njih naredimo nekaj demonstracij. +

+ +
+ + + +
Graf (gozd) družinskih relacij
+
+ +
+?- parent(thomas, X).
+X = william ;
+X = sally ;
+X = jeffrey ;
+no.
+
+ +

+Zgornje vprašanje smo v naravnem jeziku interpretirali kot „kdo vse je otrok od +Thomasa?“ Vidimo, da ima Thomas tri otroke. Zdaj pa bomo na različne načine +našteli njegove vnuke in pri tem demonstrirali delovanje reza. +

+
+?- parent(thomas, X), parent(X, Y).
+X = william, Y = vanessa ;
+X = william, Y = patricia ;
+X = sally, Y = andrew ;
+X = sally, Y = melanie ;
+no.
+
+ +

+To vprašanje našteje vse vnuke; kar poskusi. No, saj si sprogramiral to v prvem +sklopu. Vseh vnukov je… štirje so! +

+

+Kaj pa tole vprašanje? +

+
+?- parent(thomas, X), parent(X, Y), !.
+X = william, Y = vanessa ;
+no.
+
+ +

+Oho! Klicaj (rez) je napravil svoje. Pomislimo, kaj se je zgodilo: ko je naletel +na klicaj, je prolog zamrznil trenutno (delno) rešitev – vrednosti spremenljivk +X in Y ter ni več dovolil drugih rešitev, čeprav smo +videli, da obstajajo. To je navsezadnje njegova naloga. +

+

+Še bolj zanimiv/poučen primer: +

+
+?- parent(thomas, X), !, parent(X, Y).
+X = william, Y = vanessa ;
+X = william, Y = patricia ;
+no.
+
+ +

+Klicaj smo sedaj postavili med oba cilja. In dobili smo… samo vnuka preko prvega +starša, torej Williama. Seveda, prolog je naletel na klicaj po tem, ko je našel +prvo rešitev za cilj parent(thomas, X) in je zato zamrznil rešitev +samo za spremenljivko X. Cilj parent(X, Y), ki je +sedaj v resnici parent(william, Y) se izvaja normalno, v smislu, da +se generirajo (na zahtevo) vse možne rešitve za Y. +

+ +

Uporaba reza

+

+Načeloma se rezu poskušamo izogibati. Seveda pa je včasih zelo koristen za +optimizacijo, ko odrežemo veje kar sami, ker vemo, da jih ne potrebujemo. +Dostikrat tudi skrajša kodo – če je to res potrebno v prologu, je veliko +vprašanje :) +

+

+Kot ste videli, rez poreže rešitve (od tu mu tudi ime). To seveda dostikrat +vpliva na prologovo „večsmernost“, ki je običajno zaželena lastnost. Rez jo +večinoma prepreči. +

+

+Glavna uporaba reza pa je pri definiciji negacije. +

+ +

Negacija v prologu

+

+Negacija je v prologu definirana takole: poskusim dokazati, da velja cilj +(predikat) P. Če mi to ne uspe, potem rečem, da velja ne +P. Ali s primerom: +

+
+?- parent(jeffrey, X).
+no.
+
+

+Ta cilj odgovarja na vprašanje „ali je Jeffrey oče?“ Kot vidimo, prolog poskuša +to dokazati, a je odgovor „no“. Zato rečemo, da velja ravno obratno: „Jeffrey ni +oče.“ Skratka, če velja negacija v prologu, to pomeni, da prolog ni uspel +dokazati cilja, ki ga negiramo! +

+

+Natančna definicija je naslednja: +

+
+not(P) :-
+    P, !, fail
+    ;
+    true.
+
+

+Kot vidiš, smo v tej definiciji uporabili rez. Preberimo logično: če velja, da +je uspel cilj P, potem to rešitev zamrznemo (rez!) in rečemo „no“ +– za to poskrbi cilj fail, ki nikoli ne uspe. +

+

+Do cilja true zaradi reza lahko pridemo samo, če P ne uspe in ne +naletimo na klicaj. Kar poskusi. +

+

+Še komentar o sintaksi: za negacijo lahko uporabljamo predikat not +(odvisno od verzije prologa), običajno pa preprosto uporabljamo operator +\+. Spodnje vprašanje pomeni: „ali Jeffrey ni starš?“ +

+
+?- \+ parent(jeffrey, X).
+yes.
+
+

+In še nekaj: rezultat negacije je vedno odgovor da ali ne, spremenljivkam se +vrednosti ne priredijo. Ne pozabi, da v bistvu cilj pod negacijo ne uspe. +

+ +

Primer uporabe

+

+Sprogramirajmo predikat count(X, L, N), ki prešteje koliko +elementov X se skriva v seznamu L in rezultat vrne v +N. +

+

+Prva, naivna implementacija je naslednja. Razmišljajmo rekurzivno. V praznem +seznamu je točno nič elementov X. Sicer pa imamo vsaj en element, +to je glava seznama. Pa predpostavimo, da rekurzija lepo prešteje, koliko +X-ov se skriva v repu (ki je krajši, torej si rekurzijo lahko +privoščimo). Sedaj pa imamo dve možnosti: ali je glava enaka X, ali +pa ni. V prvem primeru rezultatu rekurzije prištejemo ena, v drugem pa ne. +

+
+count(X, [], 0).        % robni pogoj: v praznem seznamu se nič ne skriva, tudi X ne ;)
+count(X, [X|T], N) :-   % prva možnost: glava je enaka X
+    count(X, T, NT),    % Hej, rekurzija, koliko X-ov se skriva v repu? Aha, NT, hvala!
+    N is NT + 1.
+count(X, [_|T], NT) :-  % druga možnost: glava ni enaka X
+    count(X, T, NT).
+
+

+Videti je v redu, tudi logično se bere nekako smiselno. Pa poglejmo, kaj pravi +prolog. +

+
+?- count(a, [a,b,c,a,a,b,b,a,d], N).
+N = 4.
+
+

+Ha! Deluje! No no, ne tako hitro. Nismo poskusili dobiti vseh odgovorov. Zakaj +pa bi jih potrebovali, boš vprašal. Jih ne, vendar nikoli ne veš, kdaj bodo +nenadoma prišli v poštev, ko bo prolog poleg štetja počel še kaj v kombinaciji. +In navsezadnje, saj nočeš, da vračamo najprej pravilen rezultat, potem pa… +poglejmo kaj. +

+
+?- count(a, [a,b,c,a,a,b,b,a,d], N).
+N = 4 ;
+N = 3 ;
+N = 3 ;
+N = 2 ;
+…
+
+

+Hmmm. Kako, kako pa to dobimo? Hja, pomislimo. Ena možnost je, da glava enaka +X, druga pa, da ni enaka X. A tega nikoli nismo zares +povedali prologu. Druga veja je count(X, [_|T], NT), ki pa pove, da +je prvi element (glava) seznama lahko karkoli. Karkoli! Torej tudi +X. Obe veji si torej nista disjunktni, relacija med njima je OR in +ne XOR, kot bi si želeli. Kako bi to naredili? Ena možnost je, da z rezom +preprečimo drugo vejo, kadar prva uspe. Takole. +

+
+count(X, [], 0).          % robni pogoj: v praznem seznamu se nič ne skriva, tudi X ne ;)
+count(X, [X|T], N) :- !,  % prva možnost: glava je enaka X
+    count(X, T, NT),      % Hej, rekurzija, koliko X-ov se skriva v repu? Aha, NT, hvala!
+    N is NT + 1.
+count(X, [_|T], NT) :-    % druga možnost: glava ni enaka X
+    count(X, T, NT).
+
+

+Kot vidiš je v tem primeru rez spremenil logični pomen programa (XOR med vejama +namesto OR). Tudi zato se ga izogibamo, ker je to lahko nevarno – težje beremo +program. +

+

+Druga možnost je uporaba negacije. V drugi veji negiramo cilj, da mora glava +biti enaka X. +

+
+count(X, [], 0).        % robni pogoj: v praznem seznamu se nič ne skriva, tudi X ne ;)
+count(X, [X|T], N) :-   % prva možnost: glava je enaka X
+    count(X, T, NT),    % Hej, rekurzija, koliko X-ov se skriva v repu? Aha, NT, hvala!
+    N is NT + 1.
+count(X, [H|T], NT) :-  % druga možnost: glava ni enaka X
+    \+ X = H,
+    count(X, T, NT).
+
+

+Seveda bi negiran cilj „X se ne more prilagoditi H“ lahko zapisali +z operatorjem \=, a smo za demonstracijo uporabili negacijo. +

+ +

Za konec

+

+Če se da, se tudi negacije (tako kot reza) izogibamo. Ker vsebuje rez, ima enak +negativen vpliv na „večsmernost“. Seveda to vedno ne gre, zato pa jo imamo – +pravim samo, da se je izogni, če se da. Kje še lahko naletiš na probleme? V +kombinaciji negacije s spremenljivkami, ki še nimajo vrednosti. Poglej tale +primer, ki želi odgovor na vprašanje, ali ima Thomas kakšnega sina: +

+
+?- \+ female(X), parent(thomas, X).
+no.
+
+

+Kako, prosim? Prologu se je zmešalo! Saj Thomas ima kar dva sina! Ima, ima, +ampak poglejmo, kaj smo vprašali. Mislili smo povsem logično: X ni +ženska in je otrok od Thomasa. Vse lepo in prav. Aker je negacija definirana v +prologu kot neuspeh cilja pod negacijo, je prologovo sklepanje naslednje: ali +lahko dokažem (zadostim) cilj „X je ženska“? Lahko, v bazi je +veliko žensk, izberem poljubno za X. Zato pa je negiran cilj +seveda… napačen! Torej ne! Če bi stvari obrnili, tako da bi negiran cilj +preverjali za konkretno vrednost za X, bi bilo vse, kot smo si +zamislili. Takole: +

+
+?- parent(thomas, X), \+ female(X).
+X = william ;
+X = jeffrey.
+
+

+Zdaj vidiš, zakaj nismo negacije uporabljali takoj od začetka. Seveda je zelo +koristna, včasih brez nje preprosto ne gre. Vendar pa je potrebno biti previden. +Če se trikov in problemov zavedaš, potem je tudi negacija povsem obvladljiva. +Seveda pa, če se da, se je je najbolje izogniti. +

+ + + diff --git a/prolog/problems/sets/is_subset_2/common.py b/prolog/problems/sets/is_subset_2/common.py index 9985a9d..04daab7 100644 --- a/prolog/problems/sets/is_subset_2/common.py +++ b/prolog/problems/sets/is_subset_2/common.py @@ -5,8 +5,8 @@ import prolog.engine import server.problems id = 132 -number = 39 -visible = False +number = 60 +visible = True facts = None solution = '''\ diff --git a/prolog/problems/sets/is_superset_2/common.py b/prolog/problems/sets/is_superset_2/common.py index 7a5e373..efefd02 100644 --- a/prolog/problems/sets/is_superset_2/common.py +++ b/prolog/problems/sets/is_superset_2/common.py @@ -5,8 +5,8 @@ import prolog.engine import server.problems id = 131 -number = 38 -visible = False +number = 50 +visible = True facts = None solution = '''\ diff --git a/prolog/problems/sets/powerset_2/common.py b/prolog/problems/sets/powerset_2/common.py index 1090bfa..efcc39b 100644 --- a/prolog/problems/sets/powerset_2/common.py +++ b/prolog/problems/sets/powerset_2/common.py @@ -5,8 +5,8 @@ import prolog.engine import server.problems id = 134 -number = 41 -visible = False +number = 80 +visible = True facts = None solution = '''\ diff --git a/prolog/problems/sets/sl.py b/prolog/problems/sets/sl.py index 2d593a8..1e6a409 100644 --- a/prolog/problems/sets/sl.py +++ b/prolog/problems/sets/sl.py @@ -1,2 +1,8 @@ name = 'Množice' -description = 'Delo z množicami predstavljenimi s seznami; negacija in rez (!) v prologu.' +description = '''\ +

+Uporaba +negacije in reza +za implementacijo predikatov za delo z množicami. +

+''' diff --git a/prolog/problems/sets/subset_2/common.py b/prolog/problems/sets/subset_2/common.py index e67c4c4..33d56a2 100644 --- a/prolog/problems/sets/subset_2/common.py +++ b/prolog/problems/sets/subset_2/common.py @@ -5,8 +5,8 @@ import prolog.engine import server.problems id = 133 -number = 40 -visible = False +number = 70 +visible = True facts = None solution = '''\ diff --git a/prolog/problems/sets/union_3/common.py b/prolog/problems/sets/union_3/common.py index c955fef..f358744 100644 --- a/prolog/problems/sets/union_3/common.py +++ b/prolog/problems/sets/union_3/common.py @@ -5,8 +5,8 @@ import prolog.engine import server.problems id = 128 -number = 35 -visible = False +number = 20 +visible = True facts = None solution = '''\ -- cgit v1.2.1