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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
WizualnieWikikod
Przemek (dyskusja | edycje)
799 edycji
Nie podano opisu zmian
 
Dorota (dyskusja | edycje)
376 edycji
Nie podano opisu zmian
 
(Nie pokazano 6 wersji utworzonych przez 2 użytkowników)
Linia 1: Linia 1:
==Ćwiczenia==
== 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.


* 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>)
* 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ść? 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==
==Ćwiczenia==


**;Napisz procedurę <tt>exists</tt>, która dla danego*;predykatu i listy sprawdzi, czy na liście jest element
* Jak można rozszerzyć liczby naturalne Churcha do liczb całkowitych?
*;spełniający predykat.
* 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>.
**;Napisz procedurę negującą predykat
* 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?
*;<tt>non: ('a -> bool) -> ('a -> bool)</tt>.*;Za pomocą tej procedury, procedury <tt>exists</tt> oraz*;składania funkcji zdefiniuj procedurę <tt>forall</tt>,*;która sprawdza, czy dany predykat jest spełniony przez wszystkie
* Jak za pomocą operatora punktu stałego można wyznaczać procedury wzajemnie rekurencyjne?
*;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 <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.

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”