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

Ćwiczenia

• 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.

• 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$.
• Potęgowanie funkcji w czasie logarytmicznym. Co tak na prawdę jest obliczane szybciej: funkcja wynikowa, czy jej wartość?
• Jak za pomocą operatora punktu stałego można wyznaczać procedury wzajemnie rekurencyjne?
• 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.) [Jest to bardzo ładne zadanie. Należy tu wykorzystać procedury jako strukturę danych reprezentującą stan kartki.]