Programowanie funkcyjne/Procedury jeszcze wyższych rzędów/Ćwiczenia: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Nie podano opisu zmian |
|||
| Linia 1: | Linia 1: | ||
==Ćwiczenia== | ==Ćwiczenia== | ||
* Dla dowolnych dwóch funkcji <math>f:X \to A</math> i <math>g:X \to B</math> istnieje dokładnie jedna taka funkcja <math>h:X \to A \times B</math>, że <math>\pi_1 \circ h = f</math> i <math>\pi_2 \circ h = g</math>. Zdefiniuj wprost procedurę <tt>prod</tt>, która na podstawie funkcji <math>f</math> i <math>g</math> wyznacza funkcję <math>h</math> dla proceduralnej definicji produktów. | * Dla dowolnych dwóch funkcji <math>f:X \to A</math> i <math>g:X \to B</math> istnieje dokładnie jedna taka funkcja <math>h:X \to A \times B</math>, że <math>\pi_1 \circ h = f</math> i <math>\pi_2 \circ h = g</math> (gdzie <math>\pi_1</math> i <math>\pi_2</math> to rzuty na pierwszą i drugą współrzędną). Zdefiniuj wprost procedurę <tt>prod</tt>, która na podstawie funkcji <math>f</math> i <math>g</math> wyznacza funkcję <math>h</math> dla proceduralnej definicji produktów. | ||
* Zaimplementuj sumy rozłączne (koprodukty) za pomocą procedur. (Koprodukt zbiorów <math>A</math> i <math>B</math> to taki zbiór <math>A+B</math> wraz z włożeniami <math>i_A : A \to A+B</math>, <math>i_B : B \to A+B</math>, że dla dowolnej pary funkcji <math>f: A \to X</math> i <math>g : B \to X</math> istnieje dokładnie jedna taka funkcja <math>h:A+ | |||
* Jak można rozszerzyć liczby naturalne Churcha do liczb całkowitych? | |||
* Zaimplementuj sumy rozłączne (koprodukty) za pomocą procedur. (Koprodukt zbiorów <math>A</math> i <math>B</math> to taki zbiór <math>A+B</math> wraz z włożeniami <math>i_A : A \to A+B</math>, <math>i_B : B \to A+B</math>, że dla dowolnej pary funkcji <math>f: A \to X</math> i <math>g : B \to X</math> istnieje dokładnie jedna taka funkcja <math>h:A+B \to X</math>, że <math>h \circ i_A = f</math> i <math>h \circ i_B = g</math>. Potraktuj tę definicję dosłownie.) Należy zaimplementować włożenie <math>A</math> i <math>B</math> w <math>A+B</math> oraz procedurę, która na podstawie funkcji <math>f</math> i <math>g</math> wyznaczy funkcję <math>h</math>. | |||
* Potęgowanie funkcji w czasie logarytmicznym. Co tak na prawdę jest obliczane szybciej: funkcja wynikowa, czy jej wartość? | * 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? | * 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 <math>x</math> i <math>y</math>. 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ę <tt>origami</tt>, która dla wywołania <tt>origami l p</tt> oblicza ile warstw papieru znajdzie się w punkcie <tt>p</tt> po złożeniu papieru zgodnie z prostymi z listy <tt>l</tt> (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.] | |||
* 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 <math>x</math> i <math>y</math>. 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ę <tt>origami</tt>, która dla wywołania <tt>origami l p</tt> oblicza ile warstw papieru znajdzie się w punkcie <tt>p</tt> po złożeniu papieru zgodnie z prostymi z listy <tt>l</tt> (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. | |||
Wersja z 22:44, 28 wrz 2006
Ćwiczenia
- Dla dowolnych dwóch funkcji i istnieje dokładnie jedna taka funkcja , że i (gdzie i to rzuty na pierwszą i drugą współrzędną). Zdefiniuj wprost procedurę prod, która na podstawie funkcji i wyznacza funkcję 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 i to taki zbiór wraz z włożeniami , , że dla dowolnej pary funkcji i istnieje dokładnie jedna taka funkcja , że i . Potraktuj tę definicję dosłownie.) Należy zaimplementować włożenie i w oraz procedurę, która na podstawie funkcji i wyznaczy funkcję .
- 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 i . 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.]
