Programowanie funkcyjne/Procedury jeszcze wyższych rzędów/Ćwiczenia: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
← poprzednia edycja
WizualnieWikikod
Przemek (dyskusja | edycje)
799 edycji
Dorota (dyskusja | edycje)
376 edycji
Nie podano opisu zmian
 
(Nie pokazano 5 wersji utworzonych przez 2 użytkowników)
Linia 1: Linia 1:
== Praca domowa ==
* 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.
* 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.) Rozwiązując to zadanie należy wykorzystać jako strukturę danych procedury.
==Ć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. (<tt>let prod f g x p = p (f x) (g x);;</tt>)
* 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.)
* 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>.  
* 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>.  
* 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?  
* Potęgowanie funkcji w czasie logarytmicznym.
* Jak za pomocą operatora punktu stałego można wyznaczać procedury wzajemnie rekurencyjne?
* 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==

Aktualna wersja na dzień 15:57, 30 wrz 2006

Praca domowa

  • Dla dowolnych dwóch funkcji f:X→A i g:X→B istnieje dokładnie jedna taka funkcja h:X→A×B, że π1∘h=f i π2∘h=g (gdzie π1 i π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 iA:A→A+B, iB:B→A+B, że dla dowolnej pary funkcji f:A→X i g:B→X istnieje dokładnie jedna taka funkcja h:A+B→X, że h∘iA=f i h∘iB=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?
Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Programowanie_funkcyjne/Procedury_jeszcze_wyższych_rzędów/Ćwiczenia&oldid=60584”