Programowanie funkcyjne/Procedury jeszcze wyższych rzędów/Ćwiczenia

From Studia Informatyczne

Praca domowa

  • Dla dowolnych dwóch funkcji f:X \to A i g:X \to B istnieje dokładnie jedna taka funkcja h:X \to A \times B, że \pi_1 \circ h = f i \pi_2 \circ h = g (gdzie \pi_1 i \pi_2 to rzuty na pierwszą i drugą współrzędną). Zdefiniuj wprost procedurę prod, która na podstawie funkcji f i g wyznacza funkcję h dla proceduralnej definicji produktów.
  • Zadanie o Origami. Dana jest lista prostych zorientowanych wyznaczająca ciąg złożeń papieru. Kartka papieru to kwadrat jednostkowy. Każda prosta jest reprezentowana przez parę różnych punktów. Punkt to para współrzędnych x i y. Papier jest składany w ten sposób, że z prawej strony prostej (patrząc w kierunku od pierwszego punktu do drugiego) jest przekładany na lewą. Napisz procedurę origami, która dla wywołania origami l p oblicza, ile warstw papieru znajdzie się w punkcie p po złożeniu papieru zgodnie z prostymi z listy l (Przyjmujemy, że na linii złożenia są obie składane warstwy papieru.) Rozwiązując to zadanie należy wykorzystać jako strukturę danych procedury.


Ćwiczenia

  • Jak można rozszerzyć liczby naturalne Churcha do liczb całkowitych?
  • Zaimplementuj sumy rozłączne (koprodukty) za pomocą procedur. (Koprodukt zbiorów A i B to taki zbiór A+B wraz z włożeniami i_A : A \to A+B, i_B : B \to A+B, że dla dowolnej pary funkcji f: A \to X i g : B \to X istnieje dokładnie jedna taka funkcja h:A+B \to X, że h \circ i_A = f i h \circ i_B = g. Potraktuj tę definicję dosłownie.) Należy zaimplementować włożenie A i B w A+B oraz procedurę, która na podstawie funkcji f i g wyznaczy funkcję h.
  • Zaimplementuj iterowanie procedur w czasie logarytmicznym (podobnie do potęgowania liczb). Co tak na prawdę jest obliczane w czasie logarytmicznym: procedura wynikowa, czy jej wynik?
  • Jak za pomocą operatora punktu stałego można wyznaczać procedury wzajemnie rekurencyjne?