Kacper's Wiki

Narzędzia użytkownika

Narzędzia witryny

Ślad:
notatki:prolog

Różnice

Różnice między wybraną wersją a wersją aktualną.

Odnośnik do tego porównania

Poprzednia rewizja po obu stronachPoprzednia wersja
Nowa wersja		Poprzednia wersja
notatki:prolog [2025/05/13 22:49] – administratornotatki:prolog [2025/05/27 14:56] (aktualna) – administrator
Linia 1: Linia 1:
-====== Prolog ======+====== Prolog: Podstawy programowania logicznego ======
 ===== Programy do uruchomienia Prologa ===== ===== Programy do uruchomienia Prologa =====
  
Linia 44: Linia 44:
 Przykłady: Przykłady:
   * Jeśli mamy fakt ''rodzic(jozef, jacek)'', zapytanie ''\+ rodzic(jozef, jacek).'' zwróci fałsz.   * Jeśli mamy fakt ''rodzic(jozef, jacek)'', zapytanie ''\+ rodzic(jozef, jacek).'' zwróci fałsz.
-  * Jeśli mamy zapytanie ''\+ rodzic(krzysztof'', jacek). (które nie jest zapisane jako fakt w bazie), to zwróci prawdę.+  * Jeśli mamy zapytanie ''\+ rodzic(krzysztof, jacek).'' (które nie jest zapisane jako fakt w bazie), to zwróci prawdę.
  
 </WRAP> </WRAP>
Linia 381: Linia 381:
 ''motyw_mordercy(M).'' ''motyw_mordercy(M).''
  
 +====== Struktury listowe w języku Prolog ======
 +
 +Struktury listowe w języku **Prolog** stanowią podstawowy mechanizm reprezentacji zbiorów danych. Listy są strukturami rekurencyjnymi, co umożliwia ich elastyczne przetwarzanie.
 +
 +===== Definicja listy =====
 +
 +Lista w Prologu to uporządkowany zbiór elementów, zapisany w nawiasach kwadratowych i oddzielony przecinkami:
 +
 +<code prolog>
 +[el1, el2, el3]
 +</code>
 +
 +Lista może być również pusta:
 +
 +<code prolog>
 +[]
 +</code>
 +
 +===== Operacje na listach =====
 +
 +====== Dostęp do elementów ======
 +
 +Lista może być rozbita na głowę (pierwszy element) i ogon (reszta listy):
 +
 +<code prolog>
 +[H|T]
 +</code>
 +
 +  - **H** – głowa listy (head)
 +  - **T** – ogon listy (tail)
 +
 +Przykład:
 +
 +<code prolog>
 +?- [H|T] = [1,2,3].
 +H = 1,
 +T = [2,3].
 +</code>
 +
 +====== Sprawdzanie przynależności ======
 +
 +Operator `member/2` sprawdza, czy element należy do listy:
 +
 +<code prolog>
 +member(X, [a,b,c]).
 +</code>
 +
 +====== Łączenie list ======
 +
 +Operator `append/3` służy do łączenia dwóch list:
 +
 +<code prolog>
 +append([1,2], [3,4], Result).
 +Result = [1,2,3,4].
 +</code>
 +
 +====== Długość listy ======
 +
 +Predykat `length/2` służy do określania długości listy:
 +
 +<code prolog>
 +length([a,b,c], N).
 +N = 3.
 +</code>
 +
 +===== Rekurencja na listach =====
 +
 +Ze względu na rekurencyjny charakter list, większość algorytmów operujących na listach korzysta z rekurencji.
 +
 +Przykład sumowania elementów listy:
 +
 +<code prolog>
 +sum([], 0).
 +sum([H|T], S) :-
 +    sum(T, S1),
 +    S is H + S1.
 +</code>
 +
 +===== Lista jako struktura danych =====
 +
 +Listy mogą zawierać zmienne, inne listy, a także złożone struktury:
 +
 +<code prolog>
 +[[a,b], [c,d]]
 +</code>
 +
 +Mogą także być niedomknięte (ang. open-ended lists):
 +
 +<code prolog>
 +[1,2|X]
 +</code>
 +
 +Jest to przydatne przy konstruowaniu dynamicznych list.
 +
 +===== Wypisywanie elementów listy =====
 +
 +Predykat wypisujący każdy element listy w osobnej linii:
 +
 +<code prolog>
 +print_list([]).
 +print_list([H|T]) :-
 +    write(H), nl,
 +    print_list(T).
 +</code>
 +
 +Przykład użycia:
 +
 +<code prolog>
 +?- print_list([apple, banana, cherry]).
 +apple
 +banana
 +cherry
 +</code>
 +
 +===== Wyodrębnianie pierwszego elementu listy =====
 +
 +Aby uzyskać pierwszy element listy, możemy użyć dopasowania wzorców (pattern matching) z użyciem operatora |.
 +
 +Przykładowy predykat:
 +
 +<code prolog>
 +first_element([H|_], H).
 +</code>
 +
 +  - **[H|_]** – dopasowuje listę, gdzie `H` to pierwszy element, a `_` ignoruje resztę.
 +  - **H** – zmienna zwracająca pierwszy element.
 +
 +Przykład użycia:
 +
 +<code prolog>
 +?- first_element([a, b, c], X).
 +X = a.
 +</code>
 +
 +===== Wyodrębnianie drugiego elementu listy =====
 +
 +Aby uzyskać drugi element listy, możemy użyć dopasowania wzorców, omijając pierwszy element.
 +
 +Predykat:
 +
 +<code prolog>
 +second_element([_, Second|_], Second).
 +</code>
 +
 +  - **[_, Second|_]** – ignoruje pierwszy element (`_`), przypisuje drugi do zmiennej `Second`, a resztę ignoruje.
 +
 +Przykład użycia:
 +
 +<code prolog>
 +?- second_element([x, y, z], X).
 +X = y.
 +</code>
 +
 +===== Wyodrębnianie ostatniego elementu listy =====
 +
 +Aby uzyskać ostatni element listy, możemy wykorzystać rekurencyjne dopasowanie wzorców.
 +
 +Predykat:
 +
 +<code prolog>
 +last_element([X], X).
 +last_element([_|T], X) :-
 +    last_element(T, X).
 +</code>
 +
 +  - **[X]** – dopasowanie jednoelementowej listy (ostatni element).
 +  - **[_|T]** – rekurencyjne przeszukiwanie ogona listy, aż zostanie tylko jeden element.
 +
 +Przykład użycia:
 +
 +<code prolog>
 +?- last_element([a, b, c, d], X).
 +X = d.
 +</code>
 +Wywołania rekurencyjne:\\
 +{{.:pasted:20250527-131822.png}}
 +
 +===== Znajdowanie elementu w liście =====
 +
 +Aby sprawdzić, czy dany element znajduje się w liście, można skorzystać z wbudowanego predykatu `member/2`, albo zdefiniować własną wersję.
 +
 +Wersja oparta na rekurencji:
 +
 +<code prolog>
 +in_list([X|_], X).
 +in_list([_|T], X) :-
 +    in_list(T, X).
 +</code>
 +
 +  - **[X|_]** – dopasowanie, jeśli pierwszy element listy to szukany element.
 +  - **[_|T]** – rekurencyjne przeszukiwanie ogona listy.
 +
 +Przykład użycia:
 +
 +<code prolog>
 +?- in_list([1, 2, 3, 4], 3).
 +true.
 +
 +?- in_list([a, b, c], d).
 +false.
 +</code>
 +
 +Alternatywa: użycie wbudowanego predykatu `member/2`:
 +
 +<code prolog>
 +?- member(3, [1,2,3,4]).
 +true.
 +</code>
 +
 +===== Sprawdzanie, czy lista jest uporządkowana rosnąco =====
 +
 +Predykat sprawdzający, czy elementy listy numerycznej rosną lub są równe (nie maleją):
 +
 +<code prolog>
 +sorted_asc([]).
 +sorted_asc([_]).
 +sorted_asc([X, Y | T]) :-
 +    X =< Y,
 +    sorted_asc([Y | T]).
 +</code>
 +
 +  - **[]** i **[ _ ]** — lista pusta lub jednoelementowa jest uporządkowana.
 +  - **[X, Y | T]** — sprawdzamy, czy pierwszy element jest mniejszy lub równy drugiemu, a następnie rekurencyjnie resztę listy.
 +
 +Przykład użycia:
 +
 +<code prolog>
 +?- sorted_asc([1, 2, 2, 4, 5]).
 +true.
 +
 +?- sorted_asc([1, 3, 2, 4]).
 +false.
 +</code>
 +
 +===== Wstawianie elementu do listy uporządkowanej rosnąco =====
 +
 +Predykat, który wstawia element `X` do posortowanej listy rosnącej `List`, zwracając nową listę `Result`, również uporządkowaną rosnąco:
 +
 +<code prolog>
 +insert_sorted(X, [], [X]).
 +insert_sorted(X, [H|T], [X,H|T]) :-
 +    X =< H.
 +insert_sorted(X, [H|T], [H|R]) :-
 +    X > H,
 +    insert_sorted(X, T, R).
 +</code>
 +
 +  - Jeśli lista jest pusta, nowa lista to `[X]`.
 +  - Jeśli `X` jest mniejsze lub równe pierwszemu elementowi `H`, wstawiamy `X` przed `H`.
 +  - W przeciwnym razie rekurencyjnie wstawiamy `X` w ogon listy.
 +
 +Przykład użycia:
 +
 +<code prolog>
 +?- insert_sorted(3, [1, 2, 4, 5], Result).
 +Result = [1, 2, 3, 4, 5].
 +</code>
 +
 +
 +===== Sortowanie listy metodą wstawiania =====
 +
 +Predykat sortujący listę numeryczną rosnąco za pomocą algorytmu sortowania przez wstawianie (*insertion sort*).
 +
 +Definicja:
 +
 +<code prolog>
 +insert_sorted(X, [], [X]).
 +insert_sorted(X, [H|T], [X,H|T]) :-
 +    X =< H.
 +insert_sorted(X, [H|T], [H|R]) :-
 +    X > H,
 +    insert_sorted(X, T, R).
 +
 +insertion_sort([], []).
 +insertion_sort([H|T], Sorted) :-
 +    insertion_sort(T, SortedT),
 +    insert_sorted(H, SortedT, Sorted).
 +</code>
 +
 +Opis działania:
 +  - `insert_sorted/3` – wstawia element w odpowiednie miejsce w posortowanej liście.
 +  - `insertion_sort/2` – rekurencyjnie sortuje ogon listy i wstawia bieżący element.
 +
 +Przykład użycia:
 +
 +<code prolog>
 +?- insertion_sort([4, 1, 3, 2], Sorted).
 +Sorted = [1, 2, 3, 4].
 +</code>
 +
 +
 +===== Obliczanie długości listy =====
 +
 +Predykat `length_list/2` oblicza długość listy – czyli liczbę jej elementów – za pomocą rekurencji.
 +
 +Definicja:
 +
 +<code prolog>
 +length_list([], 0).
 +length_list([_|T], N) :-
 +    length_list(T, N1),
 +    N is N1 + 1.
 +</code>
 +
 +  - **[]** – pusta lista ma długość 0.
 +  - **[_|T]** – ignorujemy pierwszy element i rekurencyjnie liczymy długość ogona listy, zwiększając wynik o 1.
 +
 +Przykład użycia:
 +
 +<code prolog>
 +?- length_list([a, b, c, d], N).
 +N = 4.
 +</code>
 +
 +Alternatywnie, można użyć wbudowanego predykatu `length/2`:
 +
 +<code prolog>
 +?- length([a, b, c, d], N).
 +N = 4.
 +</code>
 +
 +===== Sumowanie elementów listy =====
 +
 +Predykat `sum_list/2` oblicza sumę wszystkich elementów numerycznych znajdujących się w liście.
 +
 +Definicja:
 +
 +<code prolog>
 +sum_list([], 0).
 +sum_list([H|T], Sum) :-
 +    sum_list(T, Rest),
 +    Sum is H + Rest.
 +</code>
 +
 +  - **[]** – suma pustej listy to 0.
 +  - **[H|T]** – dodajemy bieżący element `H` do sumy pozostałych elementów `T`.
 +
 +Przykład użycia:
 +
 +<code prolog>
 +?- sum_list([1, 2, 3, 4], S).
 +S = 10.
 +</code>
 +
 +Można również użyć wbudowanego predykatu `sum_list/2`, który działa identycznie:
 +
 +<code prolog>
 +?- sum_list([1,2,3,4], S).
 +S = 10.
 +</code>
 +
 +===== Średnia arytmetyczna elementów listy =====
 +
 +Predykat `average_list/2` oblicza średnią arytmetyczną wszystkich elementów numerycznych w liście.
 +
 +Wymaga dwóch pomocniczych predykatów:
 +  * `sum_list/2` – oblicza sumę elementów,
 +  * `length_list/2` – oblicza długość listy.
 +
 +Definicja:
 +
 +<code prolog>
 +sum_list([], 0).
 +sum_list([H|T], Sum) :-
 +    sum_list(T, Rest),
 +    Sum is H + Rest.
 +
 +length_list([], 0).
 +length_list([_|T], N) :-
 +    length_list(T, N1),
 +    N is N1 + 1.
 +
 +average_list(List, Avg) :-
 +    sum_list(List, Sum),
 +    length_list(List, Length),
 +    Length > 0,
 +    Avg is Sum / Length.
 +</code>
 +
 +Opis działania:
 +  - Najpierw obliczamy sumę elementów listy.
 +  - Następnie obliczamy jej długość.
 +  - Obliczamy średnią jako `Sum / Length`.
 +
 +Przykład użycia:
 +
 +<code prolog>
 +?- average_list([2, 4, 6, 8], A).
 +A = 5.0.
 +</code>
 +
 +Uwaga: predykat sprawdza, czy długość listy jest większa od zera, aby uniknąć dzielenia przez zero.
  
  
notatki/prolog.1747169375.txt.gz · ostatnio zmienione: przez administrator

Narzędzia strony

Wszystkie treści w tym wiki, którym nie przyporządkowano licencji, podlegają licencji: GNU Free Documentation License 1.3
GNU Free Documentation License 1.3