Paradygmaty programowania/Ćwiczenia 7: Programowanie w logice - przegląd

Zadanie 1

Napisać funktor służący do obliczania długości listy.

Wskazówka:

Rzecz może wyglądać tak:

     len([], 0).
     len([_ | Lst], X) := len(Lst, Y), X is Y+1.

Nota bene: Czy takiego funktora można użyć do wygenerowania listy o podanej długości, np. pytając len(X, 3)? Sprawdź. Co by się stało, gdybyśmy zamienili kolejność termów w poprzedniku? Sprawdź...

Zadanie 2

Napisać funktor służący do sumowania elementów listy (przy założeniu, że lista składa się z samych liczb).

Wskazówka:

Zwróć uwagę na podobieństwo do obliczania długości listy.

Zadanie 3

Oszacować złożoność przykładów podanych na końcu wykładu (append, reverse, member) w funkcji długości przetwarzanych list. Czy zależy to od sposobu użycia tych funktorów (policzenie wyniku lub tylko sprawdzenie)?

Zadanie 4

Podany w przykładzie funktor member sprawdza przynależność elementu do listy nie zakładając nic o uporządkowaniu listy. Gdyby założyć, że lista zawiera np. liczby uporządkowane rosnąco, można by przerwać szukanie, gdy tylko dojdziemy do liczby większej niż szukana. Napisz taką wersję funktora. Można korzystać z infiksowych operatorów porównywania liczb.

Zadanie 5*

Napisać w Prologu program sortujący listę.

Wskazówka:

Klasyczne (choć bardzo nieefektywne) rozwiązanie prologowe polega na opisaniu sortowania w następujący sposób:

     sort(X, Y) :- perm(X, Y), uporządkowana(X).

Tu perm(X, Y) oznacza, że lista X jest permutacją listy Y, zaś uporządkowana(X) — że lista X jest uporządkowana. Innymi słowy, żeby posortować listę, generujemy różne permutacje, aż trafimy na właściwą... Można zatem zadawać pytania np.:

     sort(X, [3, 5, 2, 7, 4]).
     sort([1, 2, 3], [3, 1, 2]).

Odpowiedzi to oczywiście X = [2, 3, 4, 5, 7] oraz Tak.

Zadanie 6

Napisać program prologowy opisujący relacje rodzinne, wraz z przykładową bazą faktów. Program powinien pozwalać na wyliczanie, kto jest czyim ojcem, matką, synem, córką, dziadkiem, wujem, ciotką itp. Przykładowe fakty mogą wyglądać tak:

     kobieta(anna).
     kobieta(ewa).
     mężczyzna(jan).
     mężczyzna(jerzy).
     matka(anna, jerzy).
     ojciec(jan, jerzy).

Zauważmy, że stwierdzenia typu kobieta(anna) i mężczyzna(jerzy) są potrzebne nie tylko do rozstrzygnięcia pewnych relacji (np. syn/córka, brat/siostra), ale również do generowania rozwiązań, gdy pytanie zawiera zmienne.