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$. Zdefiniuj wprost procedurę prod, która na podstawie funkcji $f$ i $g$ wyznacza funkcję $h$ dla proceduralnej definicji produktów. (let prod f g x p = p (f x) (g x);;)
• 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 można rozszerzyć liczby naturalne Churcha do liczb całkowitych?
• Jak za pomocą operatora punktu stałego można wyznaczać procedury wzajemnie rekurencyjne?

Laboratorium

• Napisz procedurę exists, która dla danego*;predykatu i listy sprawdzi, czy na liście jest element spełniający predykat.
• Napisz procedurę negującą predykat non: ('a -> bool) -> ('a -> bool). Za pomocą tej procedury, procedury exists oraz składania funkcji zdefiniuj procedurę forall, która sprawdza, czy dany predykat jest spełniony przez wszystkie elementy danej listy.
• Przypomnij sobie zadanie dotyczące wyliczania wartości. Rozszerz składnię wyrażeń o zmienne. Procedura obliczająca wartość wyrażenia będzie wymagać dodatkowego parametru - wartościowania zmiennych, czyli funkcji, która nazwie zmiennej przyporządkowuje jej wartość.
• Całkowanie funkcji.
• 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.