Programowanie deklaratywne

Haskell

Zasoby WWW:

HaskellWiki – Strona domowa języka Haskell
Implementacje Haskella:
- The Glasgow Haskell Compiler (GHC)
- Hugs 98
Tutoriale:
Haskell Hierarchical Libraries

Zadania:

- Napisać jednoargumentową funkcję silnia zwracającą silnię ze swojego argumentu. Przykład użycia:
```
> silnia 0
1
> silnia 5
120
```
- Napisać jednoargumentową funkcję fib taką, że fib n zwraca n-ty element ciągu Fibonacciego zdefiniowanego w nastepujący sposób:
  
  Przykład użycia:
```
> fib 0
0
> fib 30
832040
```
Obie funkcje napisać w dwóch wersjach – jednej korzystającej bezpośrednio z rekurencyjnej definicji, drugiej – implementującej algorytm iteracyjny (korzystającej z rekursji ogonowej).
Funkcje sinus i cosinus można zdefiniować w nastepujący sposób:

Napisać funkcje sin i cos obliczające ospowiednio sinus i cosinus ze swojego argumentu korzystając z powyższych wzorów. Iteracja ma się zakończyć gdy moduł kolejnego składnika sumy będzie mniejszy od pewnej wybranej wartośći (odpowiednio małej).
Napisać nastepujące funkcje operujące na listach:
- dlugosc – zwraca długość listy zadanej jako argument,
- odwroc – zwraca odwróconą listę zadaną jako argument,
- polacz – dwuargumentowa; zwraca listę będąca konkatenacją argumentów,
- polaczListy – dostaje w argumencie listę list; zwraca listę będącą konkatenacją wszystkich list zawartych w argumencie.
- wstaw – dostaje w argumencie posortowaną rosnąco listę i element do wstawienia do listy; zwraca listę z elementem wstawionym do niej tak żeby zachować posortowanie,
- sortWstaw – dostaje jeden argument &ndash listę, zwraca tę listę posortowaną rosnąco (np. algorytmem sortowania przez wstawianie)
Przykłady uzycia:
```
> dlugosc [1, 2, 3]
3
> odwroc [5, 6, 7]
[7, 6, 5]
> polacz ['a', 'b'] "cde"
"abcde"
> polaczListy [[1, 2], [], [3, 4, 5, 6, 7], [8]]
[1, 2, 3, 4, 5, 6, 7, 8]
> wstaw [1, 4, 8] 7
[1, 4, 7, 8]
> wstaw [1, 4, 5] 7
[1, 4, 5, 7]
> sortWstaw [5, 2, 9, 3, 1]
[1, 2, 3, 5, 9]
```
Nie korzystać ze standardowych funkcji operujących na listach.
Niech wielomian jednej zmiennej będzie reprezentowany przez listę współczynników. w kolejności od wyrazu wolnego do współczynnika przy najwyższej potędze. Np. wielomian 5x⁴ - 3x + 2 będzie reprezentowany przez listę [2, -3, 0, 0, 5]. Wielomian zerowy reprezentowany jest przez pustą listę. Zaimplementować nastepujące funkcje:
- addPoly :: (Num a) => [a] -> [a] -> [a]
  — realizująca dodawanie wielomianów,
- mulPoly :: (Num a) => [a] -> [a] -> [a]
  — realizująca mnożenie wielomianów.
  Wskazówka: można wykorzystać fakt, że
  (a₀ + a₁x + ... + a_nxⁿ) × (b₀ + b₁x + ... + b_mx^m) = a₀ × (b₀ + b₁x + ... + b_mx^m) + [(a₁ + ... + a_nx^n-1) × (b₀ + b₁x + ... + b_mx^m)] × x.
Lista wynikowa nie może zawierać nadmiarowych zer na końcu nawet jeżeli argumenty zawierają.
Przykład:
```
> addPoly [1, 2] [-5, 5, 6]
[-4,7,6]
> addPoly [1, -2, 0, 3] [-1, 2, 0, -3, 0]
[]
> mulPoly [1, 2, 1] [2, -3]
[2,1,-4,-3]
```
Zbiory mogą być reprezentowane przez funkcje logiczne zwracające True dla elementów należących do zbioru i False dla nienależących. Na przykład dwuelementowy zbiór a zawierający elementy 1 i 2 możemy zdefiniować w nastepujący sposób:
```
a 1 = True
a 2 = True
a _ = False
```
lub
```
a = \x -> x == 1 || x == 2
```
Zdefiniować następujące zbiory i operacje na zbiorach:
- pusty – zbiór pusty,
- parzyste, nieparzyste – zbiór wszystkich liczb – odpowiednio parzystych i nieparzystych,
- tworzZbior – dostaje w argumencie listę; zwraca zbiór złożony z elementów listy,
- nalezy element zbior – czy zadany element należy do zadanego zbioru,
- dodaj element zbior – zwraca zbiór z dodanym elementem,
- odejmij element zbior – zwraca zbiór z zabranym elementem,
- suma zbiorA zbiorB – suma zbiorów,
- iloczyn zbiorA zbiorB – iloczyn zbiorów,
- roznica zbiorA zbiorB – różnica zbiorów,
- dopelnienie zbior – dopełnienie zbioru.
Zdefiniować funkcję wybierz, która dla zadanego zbioru i listy elementów zwróci listę tylko tych elementów, które należą do zbioru. Wskazówka: można użyć funkcji filter .
Przykłady użycia:
```
> wybierz pusty [1, 3, 4, 5, 9]
[]
> wybierz (dodaj nieparzyste 6) [2, 3, 4, 5, 6, 7, 8, 9]
[3, 5, 6, 7, 9]
> wybierz (odejmij 3 (suma (tworzZbior [1, 2, 3, 4]) (tworzZbior [3, 8]))) [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 2, 4, 8]
```
Macierz liczbowa może być reprezentowana jako niepusta lista wierszy, przy czym każdy wiersz jest reprezentowany jako niepusta lista liczb.

Napisać funkcję mnoz_mac zwracającą iloczyn macierzy zadanych jako argumenty. Jeżeli m1 lub m2 nie reprezentują poprawnych macierzy lub reprezentują macierze, których nie można przez siebie pomnożyć, to wynikiem jest lista pusta ([]).

Lista nie reprezentuje poprawnej macierzy jeżeli, np. jest pustą listą, jej elementy są pustymi listami, jej elementy są różnej długości.
Napisać funkcję take2d :: Int -> Int -> [[a]] -> [[a]] taką, że wywołanie take2d y x w zwraca y-elementową listę list powstałych przez wzięcie pierwszych x elementów z każdego z pierwszych y elementów (też list) z listy w. Jeżeli któraś z list nie ma wystarczającej liczby elementów, to odpowiadające jej lista wynikowa też jest krótsza. Przykłady:
```
> take2d 4 3 [[1,2,3,4],[5,6],[7,8,9,10],[],[11,12]]
[[1,2,3],[5,6],[7,8,9],[]]
> take2d 5 2 [[1,2,3],[4,5,6]]
[[1,2],[4,5]]
```
Napisać funkcję wykres :: (Int -> Int -> Bool) -> [[Int]] zwracającą nieskończoną listę nieskończonych list. Funkcja wykres dostaje jeden argument – dwuargumentową funkję logiczną f. Jeżeli f m n zwraca wartość True, to m-ty element n-tej listy wyniku ma wartość 1, a w przeciwnym razie – 0. Na przykład dla funkcji take2d zdefiniowanej jak w zadaniu nr
```
> take2d 4 7 (wykres (\x y -> x == y + 1))
[[0,1,0,0,0,0,0],[0,0,1,0,0,0,0],[0,0,0,1,0,0,0],[0,0,0,0,1,0,0]]
> take2d 4 7 (wykres (\x y -> y > 1 && x > 2))
[[0,0,0,0,0,0,0],[0,0,1,1,1,1,1],[0,0,1,1,1,1,1],[0,0,1,1,1,1,1]]
```
Typ DzienTyg reprezentujący dni tygodnia jest zdefiniowany w nastepujący sposób:
data DzienTyg = Pon | Wt | Sr | Czw | Pt | Sob | Niedz
Napisać funkcje:
- jutro :: DzienTyg -> DzienTyg,
- pojutrze :: DzienTyg -> DzienTyg,
- zaDni :: Int -> DzienTyg -> DzienTyg
  — jaki dzień tygodnia będzie za zadana liczbę dni; liczba dni może być też ujemna,
- wczoraj :: DzienTyg -> DzienTyg,
- przedwczoraj :: DzienTyg -> DzienTyg,
Typ DzienRoku reprezentujący dzień w roku jest zdefiniowany w nastepujący sposób:
```
data DzienRoku =
  NowyRok |
  DzienDziecka |
  MD Int Int       -- pierwszy argument oznacza miesiąc, drugi dzień
```
Napisać funkcje:
- dzien :: DzienRoku -> Int,
- miesiac :: DzienRoku -> Int,
- dzienTygodnia :: DzienRoku -> Int -> DzienTyg
  — jaki dzień tygodnia będzie w zadanym dniu zadanego roku,
- wielkanoc :: Int -> DzienRoku,
  — kiedy będzie Wielkanoc w danym roku.
Wskazówki:
- Wielkanoc zawsze przypada w pierwszą niedzielę po pierwszej pełni Księżyca przypadającej po równonocy wiosennej ;-)
- Bardziej przydatna wskazówka
- Kolejna przydatna wskazówka
Drzewo binarne może być albo drzewem pustym, albo składać się z korzenia i dwóch drzew: lewego poddrzewa i prawego poddrzewa. Zdefiniować typ BinaryTree reprezentujący drzewo binarne i napisać nastepujące funkcje:
- left, right :: BinaryTree t -> BinaryTree t
  — zwracają odpowiednio lewe i prawe poddrzewo,
- root :: BinaryTree t -> t
  — zwraca korzeń drzewa,
- find :: (Eq a) => a -> BinaryTree a -> Bool
  — sprawdza, czy element równy argumentowi jest w drzewie,
- inOrder, bfs :: BinaryTree a -> [a]
  — przeszukuje drzewo odpowiednio wgłąb w kolejności in-order i wszerz; zwraca listę zawierającą elementy w kolejności przeszukiwania.
Dla typu DzienRoku zdefiniowanego jak w zadaniu nr zdefiniować operatory „==”, „<” i „>”.
Niech będzie dany następujący typ reprezentujący drzewa napisów:
```
data DNap = Nil | Wezel String DNap DNap
```
- Nil oznacza drzewo puste,
- Wezel X D1 D2 oznacza węzeł, który przechowuje informację X. D1 oznacza najbardziej lewego syna tego węzła, a D2 najbliższego prawego brata. Jeżeli węzeł nie ma syna (brata) to D1 (odpowiednio D2) ma wartość Nil.
Np. drzewo
jest reprezentowane jako
Wezel "1" (Wezel "2" Nil (Wezel "3" (Wezel "5" Nil Nil) (Wezel "4" Nil Nil))) Nil.
Niech będzie dane drzewo przechowujące napisy w następujący sposób:
- w korzeniu przechowywane jest zawsze słowo puste (""),
- w drzewie nie ma dwóch takich samych słów,
- jeżeli słowo S1 jest prefiksem (właściwym) słowa S2 to węzeł przechowujący S1 jest przodkiem węzła przechowującego S2.
- jeżeli słowo S1 jest wcześniej w alfabecie niż słowo S2 i węzły je przechowujące mają wspólnego ojca, to węzeł przechowujący S2 jest prawym bratem węzła przechowującego S1.
Przykład:
czyli:
```
Wezel ""
      (Wezel "ba"
             (Wezel "bal" (Wezel "balowy" Nil Nil)
             (Wezel "banan" Nil
             (Wezel "baran" (Wezel "baranina" Nil Nil)
             Nil)))
      (Wezel "kra"
             (Wezel "kraj" (Wezel "kraje" (Wezel "krajewski" Nil Nil) Nil)
             (Wezel "kram" Nil Nil))
      (Wezel "ser" Nil
      (Wezel "z"
             (Wezel "ze" (Wezel "zez" (Wezel "zezowaty" Nil Nil) Nil) Nil)
             Nil))))
      Nil
```
Napisać funkcje:
- wstaw :: String -> DNap -> DNap – zwraca drzewo z wstawionym napisem.
- znajdz :: String -> DNap -> Bool – sprawdza, czy zadany napis występuje w drzewie,
- listaSlow :: DNap -> [String] – zwraca listę słów z drzewa uporządkowaną alfabetycznie,
- usun :: String -> DNap -> DNap – zwraca drzewo z usuniętym słowem; jeżeli słowa nie ma w drzewie to zwraca drzewo bez zmian.
Typ DNap ma należeć do klasy Show, a funkcja show ma być zaimplementowana tak, żeby zwracała napis przedstawiający drzewo w następujący sposób:
```
|-ba
| |-bal
| | \-balowy
| |-banan
| \-baran
|   \-baranina
|-kra
| |-kraj
| | \-kraje
| |   \-krajewski
| \-kram
|-ser
\-z
  \-ze
    \-zez
      \-zezowaty
```
("|-ba\n| |-bal\n| | \\-balowy\n...").

Napisać funkcję, która dla zadanej gramatyki bezkontekstowej zwróci listę wszystkich słów języka opisywanego przez tę gramatykę.

Gramatyka reprezentowana jest przez listę produkcji, symbole terminalne przez napisy (typ String), symbole nieterminalne (zmienne) przez liczby całkowite (typ Int). Produkcja reprezentowana jest przez parę typu (Int, [Symbol]), przy czym pierwszy element pary oznacza lewą stronę produkcji, a drugi prawą. Typ Symbol zdefiniowany jest w następujący sposób: data Symbol = Term String | Nieterm Int. Symbol początkowy reprezentowany jest zawsze przez liczbę 1.

Np. następująca gramatyka opisująca język palindromów złożonych z zer i jedynek

P -> ø
P -> 0
P -> 1
P -> 0P0
P -> 1P1

może być reprezentowana przez

[
 (1, [Term ""]),
 (1, [Term "0"]),
 (1, [Term "1"]),
 (1, [Term "0", Nieterm 1, Term "0"]),
 (1, [Term "1", Nieterm 1, Term "1"])
]

W przypadku gramatyk opisujących języki nieskończone, wynik też musi być listą nieskończoną. W takim przypadku nie wystarczy żeby dowolona liczba różnych słów należących do języka występowała w liście (tak będzie np. dla powyższej gramatyki i listy ["", "0", "00", "000", "0000", ...]). Musi być też spełniony warunek, żeby każde słowo należące do języka występowało na pewnej pozycji w liście (np. lista

["", "0", "1", "00", "000", "010", "11", "101", "111", "0000", "00000", "00100", "0110", "01010",
          "01110", "1001", "10001", "10101", "1111", "11011", "11111", ...]

Inny przykład: dla gramatyki

Stmt -> p
Stmt -> Var:=Exp
Stmt -> if(Var)(Stmt)(Stmt)
Stmt -> while(Var)(Stmt)
Stmt -> (Stmt;Stmt)
Var  -> x
Expr -> Var
Expr -> Expr+Expr

i wywołania z argumentem odpowiadającym tej gramatyce

take 40 (slowa_z_gramatyki [
  (1, [Term "p"]),
  (1, [NieTerm 2, Term ":=", NieTerm 3]),
  (1, [Term "if(", NieTerm 2, Term ")(", NieTerm 1, Term ")(", NieTerm 1, Term ")"]),
  (1, [Term "while(", NieTerm 2, Term ")(", NieTerm 1, Term ")"]),
  (1, [Term "(", NieTerm 1, Term ";", NieTerm 1, Term ")"]),
  (2, [Term "x"]),
  (3, [NieTerm 2]),
  (3, [NieTerm 3, Term "+", NieTerm 3])
])

wynikiem może być lista:

[
"p",
"if(x)(p)(p)",
"while(x)(p)",
"(p;p)",
"x:=x",
"if(x)(p)(if(x)(p)(p))",
"if(x)(p)(while(x)(p))",
"if(x)(p)((p;p))",
"if(x)(if(x)(p)(p))(p)",
"if(x)(if(x)(p)(p))(if(x)(p)(p))",
"if(x)(if(x)(p)(p))(while(x)(p))",
"if(x)(if(x)(p)(p))((p;p))",
"if(x)(while(x)(p))(p)",
"if(x)(while(x)(p))(if(x)(p)(p))",
"if(x)(while(x)(p))(while(x)(p))",
"if(x)(while(x)(p))((p;p))",
"if(x)((p;p))(p)",
"if(x)((p;p))(if(x)(p)(p))",
"if(x)((p;p))(while(x)(p))",
"if(x)((p;p))((p;p))",
"while(x)(if(x)(p)(p))",
"while(x)(while(x)(p))",
"while(x)((p;p))",
"(p;if(x)(p)(p))",
"(p;while(x)(p))",
"(p;(p;p))",
"(if(x)(p)(p);p)",
"(if(x)(p)(p);if(x)(p)(p))",
"(if(x)(p)(p);while(x)(p))",
"(if(x)(p)(p);(p;p))",
"(while(x)(p);p)",
"(while(x)(p);if(x)(p)(p))",
"(while(x)(p);while(x)(p))",
"(while(x)(p);(p;p))",
"((p;p);p)",
"((p;p);if(x)(p)(p))",
"((p;p);while(x)(p))",
"((p;p);(p;p))",
"x:=x+x",
"if(x)(p)(x:=x)",
]

Mamy daną planszę w kształcie ćwierćpłaszczyzny ograniczonej z lewej strony i z góry. Plansza podzielona jest na pola. Każde pole określone jest za pomocą dwóch współrzędnych całkowitych (indeksowane od zera w górę). Po planszy porusza się pionek startujący z pozycji (0, 0) i początkowo skierowany w prawo. W każdym ruchu pionek może zostać skierowany w jedną z czterech stron (w górę, w dół, w lewo lub w prawo) bądź przesunąć się naprzód o jedno pole. Na odwiedzonych polach pionek zostawia ślad. Pionek może poruszać się także poza planszą, ale nie zostawia wtedy śladu.

Napisać program, wyświetlający stan planszy, pobierający od użytkownika zestaw komend dla pionka, wyświetlający stan planszy po wykonaniu komend, znów wyświetlający stan planszy, itd.

Zestaw komend jest pojedynczym wierszem, którego każdy znak albo jest komendą, albo jest ignorowany. Komendy są małymi literami: n, e, s i w oznaczają skierowanie pionka odpowiednio w górę, prawo, dół i lewo, f oznacza przejście naprzód o jedno pole, a q oznacza koniec działania programu.
Plansza wyświetlana jest w następujący sposób: najpierw wyświetlany jest wiersz ze współrzędnymi pionka w formacie (x, y) (x oznacza współrzędną w poziomie, a y w pionie), a następnie prostokątne otoczenie pionka o wysokości 11 i szerokości 21. Pionek jest zawsze na środku wyświetlanego prostokąta i wyświetlany jest jako „^”, „>”, „v” lub „<” w zależności od kierunku, w którym jest skierowany. Nieodwiedzone pola leżące na planszy wyświetlane są jako „#”, odwiedzone jako „.”, a obszar poza planszą jako „~”. Np. początkowy stan planszy będzie wyświetlony tak:
```
(0, 0)
~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~>##########
~~~~~~~~~~###########
~~~~~~~~~~###########
~~~~~~~~~~###########
~~~~~~~~~~###########
~~~~~~~~~~###########
```
Przykładowa sesja użytkownika z programem może wyglądać tak:
```
(0, 0)
~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~>##########
~~~~~~~~~~###########
~~~~~~~~~~###########
~~~~~~~~~~###########
~~~~~~~~~~###########
~~~~~~~~~~###########
fffffsffffwffffffffs
(-3, 4)
~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~......##
~~~~~~~~~~~~~#####.##
~~~~~~~~~~~~~#####.##
~~~~~~~~~~~~~#####.##
~~~~~~~~~~v~~......##
~~~~~~~~~~~~~########
~~~~~~~~~~~~~########
~~~~~~~~~~~~~########
~~~~~~~~~~~~~########
~~~~~~~~~~~~~########
affbffffecfffffndfff12ff3fff
```
(znaki a, b,c,d,1,2 i 3 są ignorowane)
```
(2, 2)
~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~......#######
~~~~~~~~#####.#######
~~~~~~~~##^##.#######
~~~~~~~~##.##.#######
~~~~~~~~......#######
~~~~~~~~##.##########
~~~~~~~~##.##########
~~~~~~~~##.##########
ffffffffffffffffffffffffff
(2, -24)
~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~^~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~
effffffffffsfffffffffffffffffffffffffffffff
(12, 7)
.##.######.##########
.##.######.##########
....######.##########
.#########.##########
.#########.##########
.#########v##########
.####################
.####################
.####################
#####################
#####################
fffeffsqffffwfffff
```
Obliczenia związane z komendami wydawanymi w tym samym wierszu co q mogą być wykonane, ale mogą też zostać opuszczone, bo plansza po zmianach i tak nie zostanie już wyświetlona.

Prolog

Zasoby WWW:

Implementacje Prologa:
Zadania programistyczne:
- P-99: Ninety-Nine Prolog Problems
- The First 10 Prolog Programming Contests
Wikipedia:
- Prolog - Wikipedia, the free encyclopedia
- Prolog (język programowania) - Wikipedia, wolna encyklopedia
Tutoriale, kursy:
Zastosowania Prologa:
- systemy ekspertowe
  - Building Expert Systems in Prolog
- przetwarzanie języka naturalnego
  - Natural Language Processing in Prolog
  - Prolog and Natural-Language Analysis
- sztuczna inteligencja — ogólnie
  - Artificial Intelligence through Prolog by Neil C. Rowe
Programowanie w logice:
- Logic, Programming and Prolog (2ed) by Ulf Nilsson and Jan Maluszynski
- An Introduction to Logic Programming through Prolog

Zadania:

W pliku rodzina.pl dopisać brakujące predykaty. Predykaty kobieta, mezczyzna i dziecko reprezentują nastepujące związki rodzinne:
Drzewa binarne możemy reprezentować w następujący sposób:
- atom nil oznacza drzewo puste
- bt(L, R, P) oznacza drzewo, którego korzeniem jest R, lewym synem L, a prawym P.
Napisać predykaty:
- jest_drzewem(D) — sprawdzający, czy D jest drzewem,
- korzen(D, R) — uzgadniający R z korzeniem drzewa D,
- lewy(D, L) — uzgadniający L z lewym synem drzewa D,
- prawy(D, P) — uzgadniający P z prawym synem drzewa D,
- wstaw(D, X, DX) — traktujący drzewo D jak drzewo BST przechowujące liczby; DX uzgadnia się z drzewem powstałym po wstawieniu X do drzewa D; do drzewa nie można wstawić dwóch takich samych elementów; do porównywania wartości można użyć odpowiednich predykatów wbudowanych (SWI Prolog Reference Manual - 4.26 Arithmetic).
Niech będzie dana następująca reprezentacja drzew:
- n oznacza drzewo puste,
- d(X, D1, D2) oznacza węzeł, który przechowuje informację X. D1 oznacza najbardziej lewego syna tego węzła, a D2 najbliższego prawego brata. Jeżeli węzeł nie ma syna (brata) to D1 (odpowiednio D2) jest równe n.
Np. drzewo

jest reprezentowane jako
d(1, d(2, n, d(3, d(5, n, n), d(4, n, n))), n).
Niech będzie dane drzewo przechowujące słowa (reprezentowane jako atomy) w następujący sposób:
- w korzeniu przechowywane jest zawsze słowo puste (atom ''),
- w drzewie nie ma dwóch takich samych słów,
- jeżeli słowo S1 jest prefiksem (właściwym) słowa S2 to węzeł przechowujący S1 jest przodkiem węzła przechowującego S2.
- jeżeli słowo S1 jest wcześniej w alfabecie niż słowo S2 i węzły je przechowujące mają wspólnego ojca, to węzeł przechowujący S2 jest prawym bratem węzła przechowującego S1.
Przykład:
czyli:
```
d('', d(ba, d(bal, d(balowy, n, n), d(banan, n, d(baran, d(baranina, n, n), n))),
      d(kra, d(kraj, d(kraje, d(krajewski, n, n), d(kram, n, n)), n),
      d(ser, n,
      d(z, d(ze, d(zez, d(zezowaty, n, n), n), n), n)))), n)
```
Napisać predykaty:
- wstaw(D1, S, D2) — wstawia słowo S do drzewa D1 (jeżeli da się wstawić);D2 uzgadnia z wynikiem,
- znajdz(D, S) — sprawdza, czy S występuje w D,
- wyswietl(D) — wyświetla wszystkie słowa z D w porządku alfabetycznym — po jednym słowie w wierszu, (predykaty write, nl)
- usun(D1, S, D2) — usuwa słowo S z drzewa D1; D2 uzgadnia z wynikiem.
Do porównywania atomów można użyć predykatu @<, do „cięcia” atomów można użyć predykatu sub_atom.
Napisać nastepujące predykaty działające na listach (nie używać predykatów wbudowanych i z biblioteki SWI Prologa):
- wstaw_sort(X, L, LX) — wstawia X do posortowanej niemalejąco listy L; LX uzgadnia się z wynikiem,
- sort_wstaw(L, LSort) — LSort uzgadnia się z posortowaną listą L (użyć algorytmu sortowania przez wstawianie),
- wstaw(X, L, LX) — wstawia X do listy L (w dowolne miejsce); LX uzgadnia się z wynikiem; np.
```
?- wstaw(4, [a, 4, x, 5], X).

X = [4, a, 4, x, 5] ;

X = [a, 4, 4, x, 5] ;

X = [a, 4, 4, x, 5] ;

X = [a, 4, x, 4, 5] ;

X = [a, 4, x, 5, 4] ;

No
```
- wybierz(L, X, Reszta) — X ugadnia się z dowolnym elemntem listy L; Reszta uzgadnia się z listą zlożoną z pozostałych elementów; np.
```
?- wybierz([3, 2, 1], X, R).

X = 3
R = [2, 1] ;

X = 2
R = [3, 1] ;

X = 1
R = [3, 2] ;

No
```
- polacz(A, B, AB) — AB uzgadnia się z listą powstałą po skonkatenowaniu list A i B,
- polacz_listy(Ls, L) — L uzgadnia się z listą powstałą po skonkatenowaniu list będących elementami listy Ls,
- odwroc(L, OdwL) — OdwL uzgadnia się z odwróconą listą L
- typy(L, LT) — LT uzgadnia się z taką listą, że każdemu elementowi listy L odpowiada w liście LT atom informujący o jego typie. Dla liczby całkowitej jest to atom int, dla atomu po prostu atom, a dla innych wartości atom inny; np.
```
?- typy([4.0, d, [1, 2], 'Ala', 4, 5, d(4)], X).

X = [inny, atom, inny, atom, int, int, inny]
```
  SWI Prolog Reference Manual - 4.5 Verify Type of a Term
- oblicz(LCyfr, Liczba) — LCyfr jest listą liczb jednocyfrowych; Liczba uzgadnia się z liczbą całkowitą złożoną z cyfr zadanych przez LCyfr,
- Napisać następujące predykaty generujące (tzn. uzgadniające G ze wszystkimi możliwymi pasującymi listami) odpowiednio permutacje, wariacje, wariacje z powtórzeniami, kombinacje listy L (N oznacza długość generowanych list):
  - permutacja(L, G)
  - wariacja(L, N, G)
  - wariacja_zp(L, N, G)
  - kombinacja(L, N, G) — w tym przypadku każdy wynik ma oznaczać inną kombinację N-elementową zbioru zadanego listą L (np. listy [1, 2, 3] i [1, 3, 2] oznaczają tę samą kombinację).
Mamy dane działanie:
NINE * THREE = NEUF * TROIS.
Każda litera oznacza inna cyfrę. Napisać predykat kryptarytm(E, F, H, I, N, O, R, S, T, U) znajdujący cyfry ukryte pod poszczególnymi literami.
Napisać predykat arytmograf(+L1, +OP, +L2, +W, -Z, -ZX) — „+” przed argumentem oznacza, że argument musi być uzgodniony, a „-”, że nie musi.

OP jest jednym z atomów '+', '-', '*', '/' i oznacza odpowiednie działanie (dodawanie, odejmowanie, mnożenie, dzielenie całkowite). L1, L2 i W są listami liczb jednocyfrowych i atomów. Każdy z tych atomów oprócz 'x' oznacza inną cyfrę (w każdej z list tę samą). Atom 'x' oznacza dowolną cyfrę (każde jego wystąpienie może oznaczać inną cyfrę). Lista [c1, c2, ...] oznacza liczbę złożoną z cyfr c1, c2, ... W jest wynikiem działania operatora OP na L1 i L2. Z jest listą par atomów i cyfr, które im odpowiadają, a ZX listą cyfr, które odpowiadają kolejnym wystąpieniom atomu 'x' w podanym działaniu.

Na przykład zapis „A53 + 4B = 1C7” oznacza działanie „153 + 44 = 197”, zapis „AX3 + AXB = 4A4” oznacza „203 + 221 = 424”, „213 + 211 = 424”, lub „223 + 201 = 424”, czyli
```
?- arytmograf([a, 5, 3], +, [4, b], [1, c, 7], L, LX).

L = [[a|1], [b|4], [c|9]]
LX = [] ;

No
?- arytmograf([a, x, 3], +, [a, x, b], [4, a, 4], L, LX).

L = [[b|1], [a|2]]
LX = [0, 2] ;

L = [[b|1], [a|2]]
LX = [1, 1] ;

L = [[b|1], [a|2]]
LX = [2, 0] ;

No
```
Mamy dany język programowania używający dla wyrażeń nawiasowej notacji prefiksowej, np. pascalowe wyrażenie (wynik = 4) and ((x + 2) < 8) będzie w nim zapisane tak: (and (= wynik 4) (< (+ x 2) 8)). W języku jest instrukcja podstawienia (set), selekcji (if), iteracji (while) oraz sekwencja instrukcji. Instrukcje też zapisywane są w nawiasowej notacji prefiksowej, a sekwencja instrukcji jako ciąg instrukcji ograniczonych nawiasami (instrukcja pusta to ()). Na przykład pascalowa instrukcja
```
while n < 10 do
  begin
    a := a + x;
    y := y * a;
    n := n + 1
  end
```
będzie zapisana jako
```
(while 
  (< n 10)
  ((set a (+ a x))
   (set y (* y a))
   (set n (+ n 1))))
```
Dokładna gramatyka języka wygląda tak (program składa się z jednej instrukcji; instrukcja oznaczona jest symbolem St):
- St ::= (if BExp St St) | (while BExp St) | (set Id Exp) | (LSt)
- LSt ::= St LSt | ø (ø oznacza symbol pusty)
- Exp ::= AExp | BExp
- AExp ::= Num | Id | (+ AExp AExp) | (- AExp AExp) | (* AExp AExp) | (/ AExp AExp) | (if BExp AExp AExp)
- BExp ::= Id | true | false | (or BExp BExp) | (and BExp BExp) | (not BExp) | (= AExp AExp) | (< AExp AExp) | (> AExp AExp) | (if BExp BExp BExp)
Num oznacza liczbę całkowitą bez znaku (4, 0, 65, 123, itp.). Id oznacza identyfikator. Identyfikatory składają się z samych małych liter i nie mogą być żadnym ze słów spośród if, while, set, or, and, not, true, false. / onacza dzielenie całkowite (jedyne typy danych w języku to typ całkowity i logiczny). Zmienne nie mają określonych typów danych (tzn. ta sama zmienna może przechowywać czasem wartość całkowitą, a czasem logiczną). Użycie zmiennej przechowującej wartość złego typu powoduje błąd podczas wykonywania programu.
Napisać predykat lex(Program, SymboleLeksykalny) dokonujący analizy leksykalnej programu zadanego pierwszym parametrem. Parametr Program jest atomem zawierającym kod źródłowy programu. Wynikiem (parametr SymboleLeksykalne) jest lista symboli leksykalnych. Symbol leksykalny oznaczający identyfikator X reprezentowany jest przez term id(X), a symbol leksykalny oznaczający liczbę N reprezentowany jest przez term num(N). Pozostałe symbole leksykalne reprezentowane są przez atomy if, while, set, and, or, not, +, -, *, /, =, <, >, ( i ). Dwa sąsiadujące leksemy, z których żaden nie jest nawiasem muszą być oddzielone od siebie przynajmniej jednym białym znakiem. Poza tym białe znaki nie mają żadnego znaczenia. Dla programów z błędami leksykalnymi predykat kończy się porażką.
Przykłady:
```
?- lex('(set x (= 3 4))', S).
S = ['(', set, id(x), '(', =, num(3), num(4), ')', ')'] ;
No

?- lex('((( while 3 3 not)aa true', S).
S = ['(', '(', '(', while, num(3), num(3), not, ')', id(aa), true] ;
No

?- lex('(=3 x)', S).
No

?- lex('(set Wx 4)', S).
No

?- lex('  (set \t\t\n    x (> 4 3))\n  \t', S).
S = ['(', set, id(x), '(', >, num(4), num(3), ')', ')'] ;
No
```
Napisać predykat syntax(SymboleLeksykalne, DrzewoSkladniowe) dokonujący analizy składniowej programu zadanego pierwszym parametrem. Parametr SymboleLeksykalne jest listą symboli leksykalnych w postaci takiej jak wynik działania predykatu lex z poprzedniego zadania. Drzewo dla każdego elementu języka jest reprezentowane przez listę, której głową jest korzeń drzewa, a kolejne elementy odpowiadają poddrzewom. Drzewo sekwencji instrukcji reprezentowane jest przez listę, w której przechowywane są same poddrzewa (odpowiadajace kolejnym instrukcjom sekwencji). Liśćmi drzew są identyfikatory oraz stałe liczbowe i logiczne (reprezentowane tak jak odpowiadające im symbole leksykalne). W korzeniach drzew mogą być słowa kluczowe i operatory (if, while, set, and, or, not, +, -, *, /, =, <, >). Założyć, że pierwszy parametr reprezentuje program bez błędów leksykalnych. Predykat ma odrzucać programy niepoprawne składniowo.
Przykłady:
```
?- syntax(['(', '(', set, id(x), num(1), ')', '(', set, id(y), num(2), ')', ')'], D).
D = [[set, id(x), num(1)], [set, id(y), num(2)]] ;
No

?- lex('(if (not (= x y)) () (set x 0))', S),  syntax(S, D).
S = ['(', if, '(', not, '(', =, id(x), id(y), ')', ')', '(', ')', '(', set, id(x), num(0), ')', ')']
D = [if, [not, [=, id(x), id(y)]], [], [set, id(x), num(0)]] ;
No

?- syntax(['(', +, num(3), num(4), ')'], D).
No

?- syntax(['(', '(', set, id(a), num(3), ')'], D).
No

?- lex('((set x 5) (while (> x 0) (set x (- x 1))))', S), syntax(S, D).
S = ['(', '(', set, id(x), num(5), ')', '(', while, '(', >, id(x), num(0), ')', '(', set, id(x), '(', -, id(x), num(1), ')', ')', ')', ')']
D = [[set, id(x), num(5)], [while, [>, id(x), num(0)], [set, id(x), [-, id(x), num(1)]]]] ;
No
```
Napisać predykat run(DrzewoSkladniowe, Zmienne) wykonujący program zadany parametrem DrzewoSkladniowe. Zmienna Zmienne ma zostać uzgodniona z listą par przechowującą wartości wszystkich zmiennych po wykonaniu programu. Parametr DrzewoSkladniowe ma być postaci takiej jak wynik działania predykatu syntax z poprzedniego zadania. Założyć, że pierwszy parametr reprezentuje poprawny składniowo program. Jeżeli podczas wykonania programu wystapi błąd (użycie niezainicjowanej zmiennej, zmienna złego typu, dzielenie przez zero), to predykat kończy się porażką (a nie zgłoszeniem błędu przez interpreter).
Przykłady:
```
?- lex('(
|         (set x 2)
|         (set y 7)
|         (set a (- x y))
|         (if (< a 0)
|             (set a (- 0 a))
|             ()
|         )
|         (set wynik 1)
|         (while (> a 1)
|                (
|                  (set wynik (* wynik a))
|                  (set a (- a 1))
|                )
|         )
|       )',
|      S), syntax(S, D), run(D, Z).

S = ['(', '(', set, id(x), num(2), ')', '(', set, id(...)|...]
D = [[set, id(x), num(2)], [set, id(y), num(7)], [set, id(a), [-, id(x), id(...)]], [if, [<, id(a), num(...)], [set, id(...)|...], []], [set, id(wynik), num(1)], [while, [>|...], [...|...]]]
Z = [[x, 2], [y, 7], [a, 1], [wynik, 120]] ;
No

?- run([set, id(x), [/, num(3), num(0)]], Z).
No

?- run([], Z).
Z = [] ;
No

?- run([if, id(x), [], [set, id(x), num(5)]], Z).
No

?- run([while, true, []], Zm).
...
```
Rozważmy następującą grę: mamy pewną liczbę stosów, na każdym z nich leży pewna liczba elementów. W grę gra dwóch graczy wykonujących na przemian ruchy. Ruch polega na zabraniu z jednego ze stosów dowolnej niezerowej liczby elementów. Wygrywa ten gracz, po którego ruchu na żadnym stosie nie ma żadnego elementu.

Napisać predykat strategia_wygr(Stosy, StosyP) sprawdzający, czy gracz, którego jest ruch ma strategię wygrywającą. Pierwszy parametr musi być uzgodniony i oznacza stan gry przed ruchem. Drugi parametr — wynikowy — uzgadnia się ze stanami gry po ruchu realizującym strategię. Oba parametry są listami liczb naturalnych, z których każda oznacza liczbę elementów na jednym ze stosów (w liście nie są przechowywane informacje o ewentualnych pustych stosach).
```
?- strategia_wygr([5], P).
P = [] ;
No

?- strategia_wygr([2, 2, 3], P).
P = [1, 2, 3] ;
P = [2, 1, 3] ;
P = [2, 2] ;
No

?- strategia_wygr([2, 2], P).
No
```
Rozważmy grę różniącą się od gry z poprzedniego zadania tym, że ruch polega zabraniu dokładnie dwóch lub trzech elementów z jednego ze stosów, a jeżeli jeden z graczy nie może wykonać ruchu, to następuje remis.
Napisać dwa predykaty:
- strategia_wygr(Stosy, StosyP) — działający analogicznie do predykatu z poprzedniego zadania,
- strategia_obr(Stosy, StosyP) — sprawdzający, czy gracz ma strategię umniemożliwiającą wygranie partii przeciwnikowi.
Stan gry w kółko i krzyżyk na planszy 3×3 można reprezentować jako listę trzech wierszy, z których każdy jest reprezentowany przez listę trzech pól. Każde pole jest reprezentowane przez jeden z trzech atomów: o – kółko, x – krzyżyk, '_' – puste pole. Np. plansza

będzie reprezentowana przez [['_', '_', o], [o, x, x], ['_', '_', '_']].

Napisać dla gry w kółko i krzyżyk na planszy 3×3 predykaty strategia_wygr(CzyjRuch, Plansza, PlanszaP) i strategia_obr(CzyjRuch, Plansza, PlanszaP) analogiczne do predykatów z poprzedniego zadania. Dodatkowy parametr CzyjRuch oznacza gracza, który wykonuje kolejny ruch (o – kółko, lub x – krzyżyk). Paramtery Plansza i PlanszaP reprezentują plansze w opisany powyżej sposób.
Niech będzie dana plansza i poruszający się po niej pionek. Informacja o planszy i sposobie poruszania się po niej pionka zawarta jest predykacie ruch(P1, P2). Dla zadanego pola (P1), w którym znajduje się pionek, predykat ten generuje wszystkie mozliwe pola, na które pionek może w tym ruchu stanąć (P2). Na przykład dla planszy:

i pionka poruszającego się tylko pionowo w górę i poziomo w prawo predykat ten może być zdefiniowany w nastepujący sposób:
```
ruch([a, 0], [a, 1]).
ruch([a, 0], [b, 0]).
ruch([b, 0], [b, 1]).
ruch([a, 1], [b, 1]).
```
Napisać predykat znajdz_droge(PolePocz, PoleKon, N, ListaPol), który dla zadanych pól początkowego (PolePocz) i końcowego (PoleKon) oraz liczby ruchów (N) znajdzie drogę (ListaPol) z pola początkowego do pola końcowego, taką że na każdym z pól pionek staje najwyżej raz i którą pionek przechodzi w zadanej liczbie ruchów. Argument ListaPol uzgadnia się z listą pól, które odwiedził pionek (lista uporządkowana jest w kolejności odwiedzania pól oraz zawiera pole początkowe i końcowe). Czyli na przykład dla powyższej planszy i ruchu zdefiniowanego jak wyżej predykat działa tak:
```
?- znajdz_droge([a, 0], [b, 1], 2, L).
L = [[a, 0], [a, 1], [b, 1]] ;
L = [[a, 0], [b, 0], [b, 1]] ;
No
```
Inny przykład — plansza jest grafem skierowanym przedstawionym na obrazku:

a ruch polega na przejściu wzdłuż krawędzi. Wtedy predykat ruch może wyglądać tak:
```
ruch(a, b).
ruch(a, c).
ruch(a, d).
ruch(a, f).
ruch(b, c).
ruch(b, d).
ruch(c, d).
ruch(c, e).
ruch(d, e).
ruch(e, a).
ruch(e, f).
ruch(f, a).
ruch(f, d).
```
a przykładowe wywołanie predykatu znajdz_droge tak:
```
?- znajdz_droge(a, e, 3, L).
L = [a, b, c, e] ;
L = [a, b, d, e] ;
L = [a, c, d, e] ;
L = [a, f, d, e] ;
No
```