Elementarz IV: Kompozycja
W poprzednim odcinku, Nauczyliśmy się używać funkcji. Zobaczyliśmy jak jedno wyrażenie może zastąpić duże ilości danych, tak jak w przykładzie z okręgiem zmieniającym się w gwiazdę, dowolnej długości ciąg punktów, wedle jednego wzorca. Zatem, taka funkcja jest też wyrażeniem pewnej idei, prawidłowości. Zobaczyliśmy też, że funkcje można ze sobą komponować, wyrażając bardziej złożone zależności, używając prostszych. W tym odcinku, bardziej szczegółowo, przedstawię te zagadnienia, z naciskiem na osiągnięcie zamierzonego celu.
Spis treści:
Cel
Żeby zilustrować kompozycję i osiąganie celu, w programowaniu, pokażę jak zaprogramować płatek Kocha, jeden z najprostszych fraktali, przypominający wyglądem płatek śniegu:
Zachęcam do przejrzenia opisu pod powyższym odnośnikiem i spróbowania rozłożenia tego zadania na małe podzadania, stosunkowo łatwe do wykonania.
Jak widzimy, płatek Kocha składa się z trzech krzywych Kocha. Stąd wniosek, że na początku chcemy uzyskać krzywą Kocha, a potem ją powielić. Czym zatem jest krzywa Kocha?
Czytamy, że jak to w matematyce zwykle bywa, nazwa odnosi się nie do konkretnego kształtu, ale pewnego rodzaju kształtów, które łączy wspólna cecha. W tym przypadku tą cechą jest to, że krzywe kocha konstruujemy z odcinka prostym przekształceniem:
- Dzielimy odcinek na 3 równe części
- Do środkowego odcinka dodajemy dwa odcinki tak, żeby utworzyły razem trójkąt równoboczny.
- Usuwamy środkowy odcinek.
Formą wyjściową krzywej Kocha jest 1 odcinek. Wykonując powyższe przekształcenie, otrzymujemy 2 formę. Każdą kolejną otrzymujemy wykonując takie przekształcenie na każdym odcinku z których składa się forma poprzednia. Wniosek?
Kluczem do zaimplementowania krzywej kocha jest zaimplementowanie pierwszego kroku dla dowolnego odcinka, a potem powielenie dla kilku odcinków. Uważny czytelnik zauważy, że takie samo działanie pozwoli nam stworzyć płatek Kocha, jeśli za kształt wyjściowy obierzemy trójkąt równoboczny.
Pierwszy krok krzywej Kocha
Podział odcinka na cześci.
Mamy dany odcinek w postaci dwóch zestawów współrzędnych, jako listę:
o = ((ax, ay), (bx, by))W jaki sposób podzielimy go na 3 części? Dane punkty będą pierwszym i ostatnim punktem wyniku, potrzebujemy znaleźć jeszcze dwa punkty, tak, żeby kolejno były w takiej samej odległości od siebie.
Najprostszy sposób to znaleźć wektor zawarty między jego punktami i podzielić jego współrzędne przez 3. Do pierwszego odcinka dodajemy kolejno wektor i jego dwukrotność. W ten sposób uzyskujemy punkty, które utworzą ten sam odcinek podzielony na 3 części.
Jak widzimy, używam tu nazwy listy jak funkcji. W ten sposób wybieram jej elementy. W przypadku zagnieżdżonych list, mogę podać kilka liczb, by wybrać elementy z list wewnętrznych. Innymi słowy, o 1 1 to pierwsza współrzędna pierwszego punktu z kształtu o, o 2 1 — pierwsza współrzędna drugiego punktu, itd.
Wprawione matematyką oko zobaczy, że: o 1 1 + krokx to to samo co o 1 1 + 1*krokx, a o 1 1 to to samo co o 1 1 + 0 * krokx. Może się wydawać mało odkrywcze, ale istotne, bo unaocznia, że przecież można napisać ostateczne wyrażenie, dzielące odcinek tak:
mapuj {i -> o 1 1 + i * krokx, o 1 2 + i * kroky}
(odlicz 4)wypróbuj!
to wyrażenie od razu zwróci wszystkie cztery punkty, tworzące 3 odcinki, które będą wyglądały identycznie jak odcinek wyjściowy. Łatwo sprawdzić:
mapuj {i -> o 1 1 + i * krokx, o 1 2 + i * kroky}
(odlicz 4), przesuń o (0, 10)wypróbuj!
W końcu, możemy zamknąć to w funkcji, która pozwoli podzielić dowolny odcinek na dowolną ilość równych części:
o = ((100,300), (500, 300));
podziel = odcinek ile -> {
dx = odcinek 2 1 - odcinek 1 1;
dy = odcinek 2 2 - odcinek 1 2;
krokx = dx / ile;
kroky = dy / ile;
mapuj {i -> odcinek 1 1 + i * krokx, odcinek 1 2 + i * kroky}
(odlicz (ile+1))
};
podziel o 3, przesuń o (0, 10)wypróbuj!
Konstukcja trójkąta równobocznego
Gdy mamy podzielony odcinek na trzy części, do środkowej części dobudowujemy trójkąt równoboczny. Innymi słowy, potrzebujemy jeszcze dwa odcinki, obrócone o 60 stopni, odpowiednio, wokoło lewego i prawego końca tego odcinka. Wygląda to tak:
podzielony = podziel o 3;
środkowy = (podzielony 2, podzielony 3);
podzielony, obróć środkowy 60 (podzielony 3),
obróć środkowy (-60) (podzielony 2)wypróbuj!
Dosyć proste prawda?
Usunięcie środkowego odcinka
Niby powinniśmy zrobić to tak:
część podzielony 1 2,
obróć środkowy (-60) (podzielony 2),
obróć środkowy 60 (podzielony 3),
część podzielony 3wypróbuj!
Funkcja część wybiera część listy. Drugi parametr oznacza numer pierwszego wydzielonego elementu, a trzeci, jeśli jest podany, ostatni.
Taki kod zadziała, to prawda. Jednak jak się zastanowić, można to zrobić prościej. Jeśli jeszcze tego nie widzisz, proponuję spojrzeć na kod jaki ten kod generuje. Najprościej zrobić to, ujmując kod w jeszcze jedną listę:
lista (
część podzielony 1 2,
obróć środkowy (-60) (podzielony 2),
obróć środkowy 60 (podzielony 3),
część podzielony 3)wypróbuj!
Kod wygląda jakoś tak:
(((100,300),(266.66666666666663,300)),
((266.66666666666663,300),(350,155.66243270259355)),
((349.99999999999994,155.66243270259355),(433.3333333333333,300)),
((433.3333333333333,300),(600,300)))I co? Ano mamy zduplikowane punkty (w końcu mamy jedną krzywą, a nie 4, jak wskazywałby ten kod. Ostatecznie wychodzi na to, że mając podzielony odcinek wystarczy dodać w jego środku jeden dodatkowy punkt i gotowe:
lista(
wstaw podzielony 2
(obróć (podzielony 2) 60 (podzielony 3)))wypróbuj!
Innymi słowy, wstaw do listy podzielony, po drugim elemencie drugi punkt z listy podzielony, obrócony o 60 stopni wokół trzeciego punktu.
Powtarzanie kroku
Gdy mamy wykonany krok dla jednego odcinka, chcemy go powtarzać dla całych krzywych. Jak to robić?
Potrzebujemy podzielić krzywą na pojedyncze odcinki. Możemy użyć do tego funkcji pary. Wówczas, możemy użyć funkcji mapuj, żeby wykonać to działanie dla każdego odcinka tworzącego krzywą, którą dostajemy na wejściu.
krok = odcinek -> {
podzielony = podziel odcinek 3;
wstaw podzielony 2
(obróć (podzielony 2) 60 (podzielony 3))
};
mapuj krok (pary o)wypróbuj!
Następnie możemy użyć funkcji powtórz, aby wykonać to samo działanie kilkakrotnie. Jednak to nie wszystko, ponieważ powyższa instrukcja powoduje utworzenie listy krzywych, a nie samą krzywą, jak oczekuje funkcja krok. Dlatego musimy użyć funkcję łącz, aby połączyć części w jedną krzywą.
lista (
powtórz o
{o -> łącz (mapuj krok (pary o))}
3)wypróbuj!
Ostatecznie możemy zebrać to razem w jedną funkcję:
koch = odcinek ile -> {
krok = odcinek -> {
podzielony = podziel odcinek 3;
wstaw podzielony 2
(obróć (podzielony 2) 60 (podzielony 3))
};
lista (powtórz odcinek
{o -> łącz (mapuj krok (pary o))}
ile)
};
koch o 3wypróbuj!
Ćwiczenia
- Wykorzystaj powyższą funkcję, żeby utworzyć kształt z początku tego tekstu. Trójkąt można łatwo wygenerować kodem: mapuj { n-> obróć (100, 225) (30+120*n) (300,225)} (odlicz 4)
- Spróbuj zmieniać stałe pojawiające się w kodzie. Co się stanie, jeśli dzielić odcinek na 4, a nie 3 częsci? Co jeśli zmienić kąt obrotu wstawianego punktu z 60 na -60 stopni?
- Zmodyfikuj kształt wejściowy, żeby uzyskać okrąg z krzywej Kocha stopnia 2. Jak zmodyfikować go, żeby powstała spirala?
Spróbuj zrozumieć
Rozważmy następujący kod:
o=(((350,440),(350,360)));
wydłuż = odc ile -> {
dx = odc 2 1 - odc 1 1;
dy = odc 2 2 - odc 1 2;
odc 1,(odc 1 1 + dx * ile,odc 1 2 + dy * ile)
};
kąt = 25
tempo = 5/6;
drzewo baza -> {
gałąź = odcinek > {
pierwsza = wydłóż (odcinek 2,
obróć (odcinek 1)
(180-kąt)
(odcinek 2))
tempo;
druga = wydłuż (odcinek 2,
obróć (odcinek 1)
(180+kąt)
(odcinek 2))
tempo;
(odcinek 1,odcinek 2,(druga 2)), pierwsza
};
dodaj = krzywa -> {
końcówka = krzywa (długość krzywa - 1),
krzywa (długość krzywa);
dodatek = gałąź końcówka;
krzywa + dodatek 1, dodatek 2
};
łącz (mapuj dodaj baza)
};
powtórz o drzewo 11wypróbuj!
Żeby nie było zbyt prosto, jest w nim kilka błędów. Na początek, popraw je, żeby zobaczyć co robi (przywyknij, programistom schodzi na to duża część czasu pracy 🤓), żeby nie było za trudno, są to tylko błędy składniowe (czyli błędny zapis logiki programu; błędy logiczne są znacznie bardziej uciążliwe).
Program definiuje 4 funkcje: wydłuż, gałąź, dodaj i drzewo. Wyjaśnij znaczenie każdej z nich. Dla każdej z nich napisz wyrażenie, które zaprezentuje jej działanie w oddzieleniu od reszty programu (podpowiedź: dwie funkcje są zdefiniowane w funkcji drzewo, żeby użyć ich na zewnątrz, trzeba je przenieść na zewnątrz.
Podsumowując
W tym odcinku zobaczyliśmy, w jaki jaki sposób możemy połączyć kilka funkcji, wyrażających proste idee, żeby wykonać bardziej złożone zadanie. Zasadniczo nie są to nowe rzeczy, w stosunku do poprzedniej lekcji (może poza definiowaniem zmiennych lokalnych w funkcji).
Z drugiej strony, jest to krytyczny punkt. Dobre zrozumienie funkcji jest podstawą dobrego programowania, stąd cały odcinek poświęcony bardziej złożonym przykładom, tak, żeby pokazać w jaki sposób, w miarę potrzeb, ujmujemy kawałki kody w deklarację funkcji, zamieniając konkretne wartości nazwami parametrów funkcji.
Zwracam też uwagę na to, że praktycznie w każdy fragment kodu możemy wyciąć (oczywiście na poziomie symboli, nie pojedynczych znaków), umieścić w funkcji i zastąpić wywołaniem tej funkcji. Za kilka odcinków zapoznamy się z programowaniem imperatywnym (obecnie dominującym), w którym tego komfortu mieć nie będziemy.
Wreszcie, myślę, że powoli staje się uciążliwe to, że cały czas musimy myśleć o tym co będzie wynikiem funkcji i czy na pewno będzie pasować do kolejnej. Mieliśmy z tym do czynienia, gdy chcieliśmy połączyć funkcje krok i powtórz, musieliśmy zastosowac funkcję łącz, żeby to połączenie mogło zadziałać. Ten problem oczywiście jest dobrze znany i jest przedmiotem typowania, którym też zajmiemy się w następnym odcinku.
