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

  #ewaluacja-wyrazen*;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.