2009-09-08
Geometria, sztuka, gołębie i gryzonie
Obrazek z niedzielnego spaceru ulicą Grodzką w Krakowie. Plac Marii Magdaleny - instalacja Ottmara Hörla "Dama z gronostajem" - oczywiście w nawiązaniu do naszego krakowskiego Leonarda.
2009-09-02
Witaj szkoło! (1?)
Moi bardzo młodzi acz niezbyt wierni czytelnicy zaglądający tu często w poszukiwaniu gotowców wypracowania (jak wynika z danych z google analytics) zaczynają właśnie szkołę. Mnie, bo zawsze mi to uświadamia jaki się stary powoli robię i ponieważ wbrew ogólnym tendencjom szkołę wspominam raczej dobrze, od razu łezka się w oku kręci. Szczęśliwe lata... Nie ma co!
Z dedykacją dla nich, dziś wpis przynależący do cyklu rekreacji matematyczno-informatycznych. Skoro szkoła, zatem i matematyka, skoro matematyka to algebra, skoro algebra to wielomiany, wzory skróconego mnożenia i inne tego typu przyjemności. Spróbujmy więc zobaczyć jak sobie poradzi z takimi zabawkami maszyna. Napiszemy ni mniej ni więcej tylko miniaturowy i prościutki system do obliczeń symbolicznych w języku Haskell.
Małe zastrzeżenia: nie będę używał tu całego potencjału języka, jak np. klas żeby jeszcze bardziej nie komplikować pojęciowo programu. Tematy jakie poruszę: algebra elementarna, wielomiany, typy danych, rekurencja, mapowanie list, składanie list, list comprehension (proponuję termin: ujawnianie postaci listy - nie wiem jak to przetłumaczyć dosłownie), odrobinę programowania generycznego.
Zaczynamy:
Ukłon w kierunku standardowej biblioteki, z której skorzystamy wkrótce:
Na poczatek, skoro algebra i wielomiany, to i zmienne, które będą dowolnymi łańcuchami znaków. Oczywiście to niebezpieczne założenie, bo może prowadzić do mylących nazw zmiennych, jak np taka: ", " ale nasz system będzie prościutki więc zaryzykujemy spychając konieczność pilnowania się na użytkownika. Zatem:
Zmienne w wielomianie występują w potęgach, a zapis potęgi danej zmiennej składa się z nazwy tej zmiennej i liczby całkowitej - potęgi w której występuje. W naszym systemie zareprezentujemy to jako parę (zmienna, liczba całkowita):
Teraz jednomian (ale bez współczynnika jeszcze) czyli lista potęg zmiennych
Jednomian ze współczynnikiem całkowitym (nazwany przeze mnie dla wygory PTerm-em) reprezentujemy przez parę:
I w końcu wielomian, który jest listą PTermów:
Poćwiczmy rozumienie tych reprezentacji.
Przykład 1:
Wielomian x reprezentujemy jako jednoelementowa listę PTerm-ów, której jedynym elementem jest jednomian x^1 ze współczynnikiem 1. Zatem reprezentacja będzie wyglądać: [(1,[("x",1)])]
Przykład 2:
Wielomian x*y reprezentujemy jako jednoelementowa listę PTerm-ów, której
jedynyjm elementem jest jednomian x^1*y^1 ze współczynnikiem 1. Zatem
reprezentacja będzie wyglądać: [(1,[("x",1),("y",1)])]
Przykład 3:
Wielomian x^3*y+4*y^2*z+1 reprezentujemy jako trójelementową listę:
[ (reprezentacja PTermu x^3*y), (reprezentacja PTermu 4*y^2*z), (reprezentacja PTermu 1)] =
[(1, reprezentacja jednomianu x^3*y), (4,reprezentacja jednomianu y^2*z),
(1, reprezentacja jednomianu pustego)] =
[(1,[reprezentacja potęgi x^3, reprezentacja potęgi y^1]), (4, [reprezentacja ptęgi y^2, reprezentacja ptęgi z^1]), (1,[])] =
[(1,[("x",3),("y",1)]), (4,[("y",2),("z",1)]), (1,[])]
OK. Uznaję, że zrozumieliśmy jak reprezentujemy wielomian i przy okazji przy tych rachunkach na palcach trochę polizaliśmy metody "schodzenia w głąb struktury" którą będziemy konsekwetnie stosować.
Na moment porzućmy wielomian i przejdźmy do użytecznej funkcji, której użyję wkrótce. Do sortowania. Oto prosty kod generycznej implementacji algorytmu quicksort, którego użyjemy:
Deklaracja:
i implementacja:
Deklaracja mówi nam, że jako argumenty funkcja sort przyjmie:
- funkcję przyjmującą dwa argumenty pewnego nieokreślonego typu i zwracającą dla nich jedną z wartości typu Bool (True lub False)
- listę elementów owego typu
Jako wynik działania otrzymamy znowu listę elementów tego typu.
Po cichu zakładamy, że argumenty są dobre, tzn. owa funkcja będąca pierwszym argumentem dla sort jest operacją mniejszości (z wszystkimi konsekwencjami takimi jak antysymetria i przechodniość wyznaczonej przez nią relacji).
Implementacja sort intensywnie korzysta z rekurencyjnej natury quicksorta. Zasadą algorytmu quicksort, która pozwala zrozumieć go bez trudu, a którą ujawnia wprost niniejszy kod jest taka: Weźmy pierwszy element z listy, którą chcemy posortować, potem wrzućmy do pewnej listy wszystkie elementy mniejsze od niego i posortujmy (znowu quicksortem), do drugiej listy wrzućmy wszystkie elementy większe od niego i też posortujmy. Wyliczmy następnie listę wynikową przez sklejenie rezultatów sortowania listy pierwszej, elementu wziętego na początku i rezultatów sortowania listy drugiej. W ramach ćwiczenia można spróbować indukcyjnie udowodnić sobie poprawność tego algorytmu (tzn. że rzeczywiście sortuje).
Zapis (a:rs) jest wzorcem do którego intepreter dopasuje listę z argumentu. Po dopasowaniu w zmiennej a znajdzie sie element stanowiący jej głowę, w zmiennej rs lista (być może pusta) bedąca jej ogonem.
Operacja ++ jest operacją konkatenacji czyli złączenia list, natomiast konstrukcja [ x|x<-rs, f a x ] jest operacją "list comprehension", co ja nazywam operacją "ujawnienia postaci listy" 1.
Oznacza ona, w tym wariancie, stworzenie listy tych elementów x listy rs, które spełniają f a x, gdzie f jest stosowną funkcją a a jest ustalone w danym kroku rekurencji.
Wykonajmy:
Test 1:
Wgrywamy plik w dotychczasowej postaci
Nasza funkcja sort rzeczywiście czasami działa. Oczywiście warto pobawić się i przekonać że działa rzeczywiście często :) i w różnych przypadkach.
Kolejną funkcją usługową, z której w różnych kontekstach skorzystamy, będzie funkcja simplify (uprość). Próbuję w niej zawrzeć pewien szczególny sposób upraszczania wyrażeń.
Deklaracja funkcji:
i implementacja:
Pierwsza z funkcji wziętych w argumencie przyjmuje dwa argumenty i zwraca wartość typu Bool (tzn. True lub False). Będzie pełniła rolę operatora porównania. Druga, dla dwu argumentów danego typu produkuje element tego typu i będzie pełniła rolę funkcji kumulacji.
simplify, działa tak, że przebiega listę wyszukuje wszystkie elementy listy równe ze względu na funkcję eq (pierwszy argument) i zastępuje je wszystkie elementem będacym ich kumulacją. Jak to działa w konkretnych przypadkach i dlaczego ma, jak wspomniałem, uchwycić pewną formę upraszczania zobaczymy za chwilę.
Z punktu widzenia języka, implementacja funkcji wprowadza sporo nowych konstrukcji poza znanym już dopasowaniem wzorca. Mamy więc operator $ oznaczajacy, że Haskell wyliczy wartość tego co po prawej stronie i użyje wyliczonej wartości w miejscu $.
Druga konstrukcja to wywołanie rekurencyjne nie zadeklarowanej ani nie zdefiniowanej wcześniej funkcji simplify_step. Funkcja ta jest zdefiniowana lokalnie po słowie where które oznacza własnie, że zdefiniowane zostaną lokalne funkcje. Typ funkcji simlify_step Haskell wydedukuje samodzielnie natomiast jej działanie jest następujące: funkcja bierze jako argument element typu takiego jaki użyty jest w argumentach wołającej ją funkcji simplify i listę elementów tego typu. Następnie wybiera te elementy listy lst którym argument f jest równy względem funkcji eq. Potem składa a właściwie kumuluje używając funkcji foldl wartości tej listy używając funkcji gr i wartości początkowej f. Ostatecznie dostaje pewien element typu takiego jak f. Następnie element ten użyty będzie jako głowa listy której ogonem bedzie lista tych elementów listy lst które nie będą równe f według relacji zadanej przez eq. Złożenie tej listy z głowy i ogona dokonuje się za pośrednictwem konstruktora listy : .
Nieco tajemnicza operacja foldl (której dokładną implementację warto podglądnąć w standardowym module Haskella Prelude) działa w taki sposób, że przyjmuje jako argumenty dwuargomentową funkcję typu (x ->x->x), czyli funkcję biorącą dwa argumenty pewnego typu x i zwracającą element typu x, wartość początkową typu x zgodnego z typem użytym w funkcji i listę elementów typu x . Następnie, jeżeli lista jest niepusta, oblicza wartość funkcji podanej jako argument na dwóch argumentach: zadanej wartości początkowej i głowie listy. Rezultat traktuje jako wartość początkową w rekurencyjnym wywołaniu samej siebie z tą samą funkcją jako argumentemi ogonem listy jako listą. Efektywnie, powoduje to zwijanie listy od lewej strony i kumulowanie wyniku.
Popatrzmy na przykład:
Przykład 4:
Jako funkcji w argumencie foldl użyjemy operatora + działąjącego na argumentach typu Int, jako wartości początkowej 1 a jako listy dwuelementowej listy zawierającej 2 i 3. Kto chce się sprawdzić niech spróbuje bazując na tym co napisane powyżej przewidzieć wynik. A oto rezultat Haskella
Wracamy do wielomianów. Wysiłek jaki włożyliśmy w ogólność funkcji simplify zwróci się teraz przy upraszczaniu jednomianów. Ponieważ jednomian jest listą potęg i na liście tej potęgi tej samej zmiennej moga znaleźć się więcej niż raz, wprowadźmy funkcję upraszczającą eliminującą ową patologię. Oto jej deklaracja i definicja będąca specjalizacją zdefiniowanej powyżej funkcji simplify w której jako funkcja porównująca użyte będzie porównanie pierwszych elementów pary (a więc zmiennych), a jako funkcja kumulująca dodawanie wykładników (co odpowiada mnożeniu potęg):
Mamy tu dwie nowe i ciekawe konstrukcje. Po pierwsze funkcje porównującą i kumulującą zdefiniowaliśmy jako funkcje anonimowe używając tzw lambda-abstrakcji. Przy takiej definicji po lewej stronie operatora -> deklarujemy argumenty funkcji poprzedzając je backslashem (będącym w tym kontekście daleko idącą stylizacją greckiej litery lambda), po prawej umieszczamy zaś stronie definicję działanie funkcji na argumentach.
Drugi interesujący element: nie wyspecyfikowaliśmy argumentu dla simplify_mon. Nie jest to jednak konieczne. Funkcja simplify jest trójargumentowa a w definicji simplify_mon ustalone zostały pierwsze dwa argumenty trzeci z nich pozostaje zmienny. Zatem ustalenie argumentów uczyniło z funkcji simplify funkcję jednoargumentową simplify_mon, przyjmującą jako argument argument ospowiadający trzeciemu argument funkcji simplify.
Kolejnym nowym elementem są dwie standardowe funkcje z modułu Prelude, mianowice fst i snd. Służą one do wybrania pierwszego (fst) i drugiego (snd) elementu pary.
Sprawdźmy teraz działanie simplify_mon. Musimy nasz jednomian zadać wprost
Test 4:
Uff. Coś działa.
Teraz jednomian sprowadzimy do postaci kanonicznej, co będzie oznaczało, że oprócz uproszczenia posortujemy jeszcze listę go reprezentującą względem porządku alfabetycznego zmiennych. Oto funkcja:
Inteligentny Haskell, dzięki modułowi Prelude wie jak porzenieść porządki zdefiniowane dla elementów pary leksykograficznie na porządek par. Funkcję sort już znamy. Zobaczmy canonize_mon w działaniu:
Test 5:
Zgodnie z oczekiwaniami.
Teraz sprowadźmy do postaci kanonicznej cały wielomian. Załatwimy sprawę jedną funkcją używając definicji lokalnych:
Nowym elementem tu jest interesująca funkcja map zdefiniowana w standardowym module Haskella Prelude, która przenosi działanie fukcji którą dostaje w argumencie na działanie na listach. Innymi słowy podając fukcję pewnego typu (x->y) jako argument do fukcji map otrzymujemy fukcję typu [x]->[y], która działa na liście w ten sposób, że tworzy nową listę każdy element której jest obrazem elementu fukcji wejściowej przez fukcję podaną jako argument do map.
Przykład 5:
Sprawdźmy w działaniu funkcję canonize_poly (póki co wielomian zadawać będziemy explicite - jeszcze tylko króciótko się tak pomęczymy)
Test 6:
Teraz zajmiemy się przedstawieniem naszych wielomianów w czytelnej dla nas formie, jako łancuchów znakowych. Zapisywać wielomiany będę oczywiście w sposób internetowy używając ASCII jedynie. Pedantycznie przepisywać bedę '*' w miejsce mnożenia i '^' przy potęgowaniu, jako ustępstwo na rzecz ładnego stylu dbając jedynie o unikanie gdzie nie potrzeba potęg pierwszych i mnożenia explicite przez 1. Przedstawię cały kod a potem omówię nowe elementy:
W funkcji tostring_mon użyłem wariantowej definicji funkcji, przypominającej mocno zapis matematyczny w postaci tak zwanej klamry, z drugiej zaś trony konstrukcję if...elsif.....else albo bardziej zaawansowany (bo nie oparty o typ numeryczny switch() .. case znany z C, C++ i Javy. Po znaku '|' mamy kolejne warunki spełnieni których przez argumenty oznacza, że wartością funkcji będzie to co po znaku równości.
Kolejna nowość tam to funkcja show stosująca się do pewnych typów przynależnych do klasy Show. Zamienia ona elementy tych typów (w naszym przypadku Integer jest takim typem) na łańcuchy znaków (typ String).
Przy okazji wyszło szydło z worka - String jest po prostu listą znaków (typ Char) i można wobec niego stosować te same operacje co wobec innych list.
Teraz pierwsza radość - zamienimy na napisy pierwsze wielomiany. Zacznijmy od wielomianów z testu 6:
Test 7:
Teraz mam nadzieję, że lepiej widać na czym polega kanonizacja.
Po mału doszliśmy do miejsca w którym możemy zdefiniować operacje na wielomianach. Zacznijmy od dodawania, które będziemy oznaczać fantazyjnym operatorem ~+, a które zdefiniujemy w zaskakująco prosty sposób.
Dodawanie jest więc jak widać konkatenacją list reprezentujących wielomiany. My, dla porządku jeszcze dodakowo od razu wynik konkatenacji skanonizujemy.
Ciekawy element to operator, który deklarujemy jako infix, czyli że argumenty dostawał będzie nie jak funkcja po swojej prawej stronie, ale jak porządny operator po obu swoich stronach. Dla potrzeb deklaracji jednak, musimy zaminieć go na chwilę na normalną funkcję (zdjąć z niego niejako "infiksowość") przez obłożenie go nawiasami.
Podobnie prosto zdefiniujemy mnożenie:
Tym razem korzystamy z faktu, że mnożenie wielomianów (będących sumą jednomianów) jest sumą wszystkich możliwych iloczynów par jednomianów, z których jeden pochodzi od pierwszego a drugi od drugiego wielomianu. Plus oczywiście kanonizacja dla porządku. Załatwiamy to jedną operacją ujawnienia postaci listy.
Czas na:
Test 8:
Spróbujemy pomnożyć x*(x+y+z*x^2):
Cały wielomian zrealizowany został jako wynik operacji na trywialnych wielomianach x, y, i z które zdefiniowane są po słówku where, wszystkie na raz w jedej krotce.
Wynik znowu zgodnie z oczekiwaniami.
Mając już takie narzędzia, zajmijmy się na chwilę klasyką, tj. tadam... dwumian Newtona. Policzmy go dla potęgi 5 dajmy na to:
Test 9:
Cóż, w nieco nieortodoksyjnym porządku, ale to czego należało się spodziewać.
Jak czytelnik pewnie zauważył zadawanie wielomianów w naszej surowej postaci nie jest wygodne, z tego względu pokusimy się o bardzo prosty parser, zamieniający reprezentację wielomianu jako zrozumiałego dla człowieka łańcucha znaków na reprezentację wewnętrzną. Ogólnie pisanie parsera wymaga sporo delikatności i uwagi, ale my napiszemy coś naprawdę bardzo prostego cedując na użytkownika staranność w zadawaniu wejścia dla parsera.
By zrealizować nasz parser, potrzebować będę tokenizera, tj funkcji zaminiającej łańcuch znaków na listę łańcuchów znaków będących rezultatem podzielenia listy oryginalnej na fragmenty rozdzielone z góry zadanym znakiem. Np napis "Ala ma kota" po "tokenizacji" względem znaku ' ' (spacja) stanie się listą ["Ala","ma","kota"]
Oto nasza funkcja tokenize, bioraca jako argument znak i łańcuch znaków a zwracającą stosowną listę łańcuchów:
Sprawdźmy działanie naszego tokenizera:
Test 10:
Dokładnie jak się spodziewaliśmy.
Wykorzystamy teraz funkcję tokenize do parsowania wielomianów. Strategia jest następująca. Najpierw łańcuch podzielimy funkcją tokenize względem znaku '+', następnie każdy z tak otrzymanych kawałków podzielimy wgledem znaku '*' a potem każdy z nich względem znaku '^'. Stosownie do tego co otrzymamy w ostatniej fazie podziału spróbujemy odbudować wielomian odpowiednie interpretując otrzmane kawałki jako wielomiany i kombinując je w wielomian funkcją foldl, kumulując je już to funkcją ~* już to funkcją ~+ stosownie do tego reprezentację jakich fragmentów scalamy.
Z nowych elementów wystąpiły tu fukcje z załadowanego na początku modułu Char, tj. isDigit (mówiąca czy znak odpowiada cyfrze) i digitToInt (zamieniająca znak odpwiadający cyfrze na odpowiadającą tej cyfrze liczbę).
Przetestujmy:
Test 11:
Jako ostatnią póki co zaimplementujmy jeszcze jedną operację - operację podstawiania. Pozwoli nam ona w prosty sposób zadawać nawet dość trudne wielomiany. Operacja podstawiania polega na tym, że za pewną zmienną w zadanym wielomianie podstawiamy inny wielomian, dokonujemy na tak otrzymanym wyrażeniu operacji algebraicznych by w efekcie otrzymać wielomian. Poniżej fukcja przyjmująca w argumencie zmienną za którą podstawiamy, wielomian do którego podstawiamy i wielomian podstawiany. Dotychczasowa wiedza powinna wystarczyć do samodzielnej jej analizy.
Sprawdżmy w działaniu.
Test 12:
Znowu dwumian Newtona - ale tym razem poszalejmy:
Hmmm... Ręcznie sprawdzić będzie ciężko.
Jak widać Haskell mógłby sobie jakoś poradzić z prostą szkolną algebrą
Na dziś kończymy zabawę. Wkrótce postaram się ulepszyć i rozbudować (nieco) tę zabawkę i poigrać trochę z takimi tematami jak wielomiany symetryczne, wyróżnik, a może i dalej : eliminacja kwantyfikatorów i twierdzenie Tarskiego.
Na razie: wszystkim uczniom i nauczycielom (szczególnie matematyki) życzę powodzenia i cierpliwości w zaczynającym się roku szkolnym.
1
Operacja ujawnienia postaci listy jest z natury podobna do matematycznego zapisu zbiory (bądź klasy) w postaci { : }, gdzie po lewej stronie znaku ':' pojawia się funkcja (być może identyczność) dla argumentów spełniajacych warunek po stronie prawej logiczny warunek opisujący wybrane elementy. Pamiętajmy jednak - listy to nie zbiory!
Z dedykacją dla nich, dziś wpis przynależący do cyklu rekreacji matematyczno-informatycznych. Skoro szkoła, zatem i matematyka, skoro matematyka to algebra, skoro algebra to wielomiany, wzory skróconego mnożenia i inne tego typu przyjemności. Spróbujmy więc zobaczyć jak sobie poradzi z takimi zabawkami maszyna. Napiszemy ni mniej ni więcej tylko miniaturowy i prościutki system do obliczeń symbolicznych w języku Haskell.
Małe zastrzeżenia: nie będę używał tu całego potencjału języka, jak np. klas żeby jeszcze bardziej nie komplikować pojęciowo programu. Tematy jakie poruszę: algebra elementarna, wielomiany, typy danych, rekurencja, mapowanie list, składanie list, list comprehension (proponuję termin: ujawnianie postaci listy - nie wiem jak to przetłumaczyć dosłownie), odrobinę programowania generycznego.
Zaczynamy:
Ukłon w kierunku standardowej biblioteki, z której skorzystamy wkrótce:
import Char
Na poczatek, skoro algebra i wielomiany, to i zmienne, które będą dowolnymi łańcuchami znaków. Oczywiście to niebezpieczne założenie, bo może prowadzić do mylących nazw zmiennych, jak np taka: ", " ale nasz system będzie prościutki więc zaryzykujemy spychając konieczność pilnowania się na użytkownika. Zatem:
type Var = String
Zmienne w wielomianie występują w potęgach, a zapis potęgi danej zmiennej składa się z nazwy tej zmiennej i liczby całkowitej - potęgi w której występuje. W naszym systemie zareprezentujemy to jako parę (zmienna, liczba całkowita):
type Power = (Var, Integer)
Teraz jednomian (ale bez współczynnika jeszcze) czyli lista potęg zmiennych
type Monomial = [Power]
Jednomian ze współczynnikiem całkowitym (nazwany przeze mnie dla wygory PTerm-em) reprezentujemy przez parę:
type PTerm = (Integer, Monomial)
I w końcu wielomian, który jest listą PTermów:
type Polynomial = [PTerm]
Poćwiczmy rozumienie tych reprezentacji.
Przykład 1:
Wielomian x reprezentujemy jako jednoelementowa listę PTerm-ów, której jedynym elementem jest jednomian x^1 ze współczynnikiem 1. Zatem reprezentacja będzie wyglądać: [(1,[("x",1)])]
Przykład 2:
Wielomian x*y reprezentujemy jako jednoelementowa listę PTerm-ów, której
jedynyjm elementem jest jednomian x^1*y^1 ze współczynnikiem 1. Zatem
reprezentacja będzie wyglądać: [(1,[("x",1),("y",1)])]
Przykład 3:
Wielomian x^3*y+4*y^2*z+1 reprezentujemy jako trójelementową listę:
[ (reprezentacja PTermu x^3*y), (reprezentacja PTermu 4*y^2*z), (reprezentacja PTermu 1)] =
[(1, reprezentacja jednomianu x^3*y), (4,reprezentacja jednomianu y^2*z),
(1, reprezentacja jednomianu pustego)] =
[(1,[reprezentacja potęgi x^3, reprezentacja potęgi y^1]), (4, [reprezentacja ptęgi y^2, reprezentacja ptęgi z^1]), (1,[])] =
[(1,[("x",3),("y",1)]), (4,[("y",2),("z",1)]), (1,[])]
OK. Uznaję, że zrozumieliśmy jak reprezentujemy wielomian i przy okazji przy tych rachunkach na palcach trochę polizaliśmy metody "schodzenia w głąb struktury" którą będziemy konsekwetnie stosować.
Na moment porzućmy wielomian i przejdźmy do użytecznej funkcji, której użyję wkrótce. Do sortowania. Oto prosty kod generycznej implementacji algorytmu quicksort, którego użyjemy:
Deklaracja:
sort :: (x -> x -> Bool) -> [x] -> [x]
i implementacja:
sort _ [] = []
sort f (a:rs) = (sort f [x|x<-rs, f x a]) ++ [a] ++ (sort f [x|x<-rs, f a x])
Deklaracja mówi nam, że jako argumenty funkcja sort przyjmie:
- funkcję przyjmującą dwa argumenty pewnego nieokreślonego typu i zwracającą dla nich jedną z wartości typu Bool (True lub False)
- listę elementów owego typu
Jako wynik działania otrzymamy znowu listę elementów tego typu.
Po cichu zakładamy, że argumenty są dobre, tzn. owa funkcja będąca pierwszym argumentem dla sort jest operacją mniejszości (z wszystkimi konsekwencjami takimi jak antysymetria i przechodniość wyznaczonej przez nią relacji).
Implementacja sort intensywnie korzysta z rekurencyjnej natury quicksorta. Zasadą algorytmu quicksort, która pozwala zrozumieć go bez trudu, a którą ujawnia wprost niniejszy kod jest taka: Weźmy pierwszy element z listy, którą chcemy posortować, potem wrzućmy do pewnej listy wszystkie elementy mniejsze od niego i posortujmy (znowu quicksortem), do drugiej listy wrzućmy wszystkie elementy większe od niego i też posortujmy. Wyliczmy następnie listę wynikową przez sklejenie rezultatów sortowania listy pierwszej, elementu wziętego na początku i rezultatów sortowania listy drugiej. W ramach ćwiczenia można spróbować indukcyjnie udowodnić sobie poprawność tego algorytmu (tzn. że rzeczywiście sortuje).
Zapis (a:rs) jest wzorcem do którego intepreter dopasuje listę z argumentu. Po dopasowaniu w zmiennej a znajdzie sie element stanowiący jej głowę, w zmiennej rs lista (być może pusta) bedąca jej ogonem.
Operacja ++ jest operacją konkatenacji czyli złączenia list, natomiast konstrukcja [ x|x<-rs, f a x ] jest operacją "list comprehension", co ja nazywam operacją "ujawnienia postaci listy" 1.
Oznacza ona, w tym wariancie, stworzenie listy tych elementów x listy rs, które spełniają f a x, gdzie f jest stosowną funkcją a a jest ustalone w danym kroku rekurencji.
Wykonajmy:
Test 1:
Wgrywamy plik w dotychczasowej postaci
Hugs> :load "C:\\Users\\Artur\\Documents\\tar.hs"i wywołujemy:
Main> sort (<) [1,2,4,3,2,6,9,0] [0,1,2,3,4,6,9]
Nasza funkcja sort rzeczywiście czasami działa. Oczywiście warto pobawić się i przekonać że działa rzeczywiście często :) i w różnych przypadkach.
Kolejną funkcją usługową, z której w różnych kontekstach skorzystamy, będzie funkcja simplify (uprość). Próbuję w niej zawrzeć pewien szczególny sposób upraszczania wyrażeń.
Deklaracja funkcji:
simplify :: (x -> x -> Bool) -> (x -> x -> x) -> [x] -> [x]
i implementacja:
Funkcja simplify bierze jako argument dwie funkcje dwuargumentowe działające na nieznanym apriori typie danych oraz listę elementów tego typu, zwraca zaś listę elementów tego typu.
simplify _ _ [] = []
simplify eq gr (h:t) = simplify_step h $ simplify eq gr t where
simplify_step f lst =
(foldl gr f [x | x <- lst, eq f x]) :
[x | x <- lst, not $ eq f x ]
Pierwsza z funkcji wziętych w argumencie przyjmuje dwa argumenty i zwraca wartość typu Bool (tzn. True lub False). Będzie pełniła rolę operatora porównania. Druga, dla dwu argumentów danego typu produkuje element tego typu i będzie pełniła rolę funkcji kumulacji.
simplify, działa tak, że przebiega listę wyszukuje wszystkie elementy listy równe ze względu na funkcję eq (pierwszy argument) i zastępuje je wszystkie elementem będacym ich kumulacją. Jak to działa w konkretnych przypadkach i dlaczego ma, jak wspomniałem, uchwycić pewną formę upraszczania zobaczymy za chwilę.
Z punktu widzenia języka, implementacja funkcji wprowadza sporo nowych konstrukcji poza znanym już dopasowaniem wzorca. Mamy więc operator $ oznaczajacy, że Haskell wyliczy wartość tego co po prawej stronie i użyje wyliczonej wartości w miejscu $.
Druga konstrukcja to wywołanie rekurencyjne nie zadeklarowanej ani nie zdefiniowanej wcześniej funkcji simplify_step. Funkcja ta jest zdefiniowana lokalnie po słowie where które oznacza własnie, że zdefiniowane zostaną lokalne funkcje. Typ funkcji simlify_step Haskell wydedukuje samodzielnie natomiast jej działanie jest następujące: funkcja bierze jako argument element typu takiego jaki użyty jest w argumentach wołającej ją funkcji simplify i listę elementów tego typu. Następnie wybiera te elementy listy lst którym argument f jest równy względem funkcji eq. Potem składa a właściwie kumuluje używając funkcji foldl wartości tej listy używając funkcji gr i wartości początkowej f. Ostatecznie dostaje pewien element typu takiego jak f. Następnie element ten użyty będzie jako głowa listy której ogonem bedzie lista tych elementów listy lst które nie będą równe f według relacji zadanej przez eq. Złożenie tej listy z głowy i ogona dokonuje się za pośrednictwem konstruktora listy : .
Nieco tajemnicza operacja foldl (której dokładną implementację warto podglądnąć w standardowym module Haskella Prelude) działa w taki sposób, że przyjmuje jako argumenty dwuargomentową funkcję typu (x ->x->x), czyli funkcję biorącą dwa argumenty pewnego typu x i zwracającą element typu x, wartość początkową typu x zgodnego z typem użytym w funkcji i listę elementów typu x . Następnie, jeżeli lista jest niepusta, oblicza wartość funkcji podanej jako argument na dwóch argumentach: zadanej wartości początkowej i głowie listy. Rezultat traktuje jako wartość początkową w rekurencyjnym wywołaniu samej siebie z tą samą funkcją jako argumentemi ogonem listy jako listą. Efektywnie, powoduje to zwijanie listy od lewej strony i kumulowanie wyniku.
Popatrzmy na przykład:
Przykład 4:
Jako funkcji w argumencie foldl użyjemy operatora + działąjącego na argumentach typu Int, jako wartości początkowej 1 a jako listy dwuelementowej listy zawierającej 2 i 3. Kto chce się sprawdzić niech spróbuje bazując na tym co napisane powyżej przewidzieć wynik. A oto rezultat Haskella
Hugs> foldl (+) 1 [2, 3]
Wracamy do wielomianów. Wysiłek jaki włożyliśmy w ogólność funkcji simplify zwróci się teraz przy upraszczaniu jednomianów. Ponieważ jednomian jest listą potęg i na liście tej potęgi tej samej zmiennej moga znaleźć się więcej niż raz, wprowadźmy funkcję upraszczającą eliminującą ową patologię. Oto jej deklaracja i definicja będąca specjalizacją zdefiniowanej powyżej funkcji simplify w której jako funkcja porównująca użyte będzie porównanie pierwszych elementów pary (a więc zmiennych), a jako funkcja kumulująca dodawanie wykładników (co odpowiada mnożeniu potęg):
simplify_mon :: Monomial -> Monomial
simplify_mon = simplify (\x y->fst x == fst y)
(\x y -> (fst x, snd x + snd y))
Mamy tu dwie nowe i ciekawe konstrukcje. Po pierwsze funkcje porównującą i kumulującą zdefiniowaliśmy jako funkcje anonimowe używając tzw lambda-abstrakcji. Przy takiej definicji po lewej stronie operatora -> deklarujemy argumenty funkcji poprzedzając je backslashem (będącym w tym kontekście daleko idącą stylizacją greckiej litery lambda), po prawej umieszczamy zaś stronie definicję działanie funkcji na argumentach.
Drugi interesujący element: nie wyspecyfikowaliśmy argumentu dla simplify_mon. Nie jest to jednak konieczne. Funkcja simplify jest trójargumentowa a w definicji simplify_mon ustalone zostały pierwsze dwa argumenty trzeci z nich pozostaje zmienny. Zatem ustalenie argumentów uczyniło z funkcji simplify funkcję jednoargumentową simplify_mon, przyjmującą jako argument argument ospowiadający trzeciemu argument funkcji simplify.
Kolejnym nowym elementem są dwie standardowe funkcje z modułu Prelude, mianowice fst i snd. Służą one do wybrania pierwszego (fst) i drugiego (snd) elementu pary.
Sprawdźmy teraz działanie simplify_mon. Musimy nasz jednomian zadać wprost
Test 4:
Hugs> :load "C:\\Users\\Artur\\Documents\\tar.hs"
Main> simplify_mon [("x",1), ("x",1)]
[("x",2)]
Uff. Coś działa.
Teraz jednomian sprowadzimy do postaci kanonicznej, co będzie oznaczało, że oprócz uproszczenia posortujemy jeszcze listę go reprezentującą względem porządku alfabetycznego zmiennych. Oto funkcja:
canonize_mon :: Monomial -> Monomial
canonize_mon mon = sort (<) $ simplify_mon mon
Inteligentny Haskell, dzięki modułowi Prelude wie jak porzenieść porządki zdefiniowane dla elementów pary leksykograficznie na porządek par. Funkcję sort już znamy. Zobaczmy canonize_mon w działaniu:
Test 5:
Main> canonize_mon [("x",1), ("x",1), ("a",5)]
[("a",5),("x",2)]
Zgodnie z oczekiwaniami.
Teraz sprowadźmy do postaci kanonicznej cały wielomian. Załatwimy sprawę jedną funkcją używając definicji lokalnych:
canonize_poly :: Polynomial -> Polynomial
canonize_poly p = sort (>) $
simplify (\x y -> snd x == snd y)
(\x y -> (fst x + fst y, snd x)) $
map (\x -> (fst x, canonize_mon $ snd x) ) p
Nowym elementem tu jest interesująca funkcja map zdefiniowana w standardowym module Haskella Prelude, która przenosi działanie fukcji którą dostaje w argumencie na działanie na listach. Innymi słowy podając fukcję pewnego typu (x->y) jako argument do fukcji map otrzymujemy fukcję typu [x]->[y], która działa na liście w ten sposób, że tworzy nową listę każdy element której jest obrazem elementu fukcji wejściowej przez fukcję podaną jako argument do map.
Przykład 5:
Prelude> map (4*) [1,2,3]
[4,8,12]
Prelude> map (\x -> [x]) ["a", "b", "c"]
[["a"],["b"]["c"]]
Sprawdźmy w działaniu funkcję canonize_poly (póki co wielomian zadawać będziemy explicite - jeszcze tylko króciótko się tak pomęczymy)
Test 6:
Main> canonize_poly [(3,[("x",1),("x",1)]), (2,[("x",2)]), (5,[("x",2),("a",4)])]
[(5,[("x",2)]),(5,[("a",4),("x",2)])]
Teraz zajmiemy się przedstawieniem naszych wielomianów w czytelnej dla nas formie, jako łancuchów znakowych. Zapisywać wielomiany będę oczywiście w sposób internetowy używając ASCII jedynie. Pedantycznie przepisywać bedę '*' w miejsce mnożenia i '^' przy potęgowaniu, jako ustępstwo na rzecz ładnego stylu dbając jedynie o unikanie gdzie nie potrzeba potęg pierwszych i mnożenia explicite przez 1. Przedstawię cały kod a potem omówię nowe elementy:
tostring_mon :: Monomial -> String
tostring_mon [] = ""
tostring_mon [(x,y)] | y == 1 = x
| otherwise = x++"^"++ (show y)
tostring_mon (a:rest) = (tostring_mon [a] ) ++ "*" ++ (tostring_mon rest)
tostring_pterm (c, []) = show c
tostring_pterm (1, m) = tostring_mon m
tostring_pterm (c, m) = (show c) ++ "*" ++ tostring_mon m
tostring_poly :: Polynomial -> String
tostring_poly [] = ""
tostring_poly [f] = tostring_pterm f
tostring_poly (f:tl) = foldl (++) (tostring_pterm f) $
map (("+"++).tostring_pterm) tl
W funkcji tostring_mon użyłem wariantowej definicji funkcji, przypominającej mocno zapis matematyczny w postaci tak zwanej klamry, z drugiej zaś trony konstrukcję if...elsif.....else albo bardziej zaawansowany (bo nie oparty o typ numeryczny switch() .. case znany z C, C++ i Javy. Po znaku '|' mamy kolejne warunki spełnieni których przez argumenty oznacza, że wartością funkcji będzie to co po znaku równości.
Kolejna nowość tam to funkcja show stosująca się do pewnych typów przynależnych do klasy Show. Zamienia ona elementy tych typów (w naszym przypadku Integer jest takim typem) na łańcuchy znaków (typ String).
Przy okazji wyszło szydło z worka - String jest po prostu listą znaków (typ Char) i można wobec niego stosować te same operacje co wobec innych list.
Teraz pierwsza radość - zamienimy na napisy pierwsze wielomiany. Zacznijmy od wielomianów z testu 6:
Test 7:
Main> tostring_poly [(3,[("x",1),("x",1)]), (2,[("x",2)]), (5,[("x",2),("a",4)])]
"3*x*x+2*x^2+5*x^2*a^4"
Main> tostring_poly $ canonize_poly [(3,[("x",1),("x",1)]),
(2,[("x",2)]), (5,[("x",2),("a",4)])]
"5*x^2+5*a^4*x^2"
Teraz mam nadzieję, że lepiej widać na czym polega kanonizacja.
Po mału doszliśmy do miejsca w którym możemy zdefiniować operacje na wielomianach. Zacznijmy od dodawania, które będziemy oznaczać fantazyjnym operatorem ~+, a które zdefiniujemy w zaskakująco prosty sposób.
infix 1 ~+
(~+) :: Polynomial -> Polynomial -> Polynomial
x ~+ y = canonize_poly $ x ++ y
Dodawanie jest więc jak widać konkatenacją list reprezentujących wielomiany. My, dla porządku jeszcze dodakowo od razu wynik konkatenacji skanonizujemy.
Ciekawy element to operator, który deklarujemy jako infix, czyli że argumenty dostawał będzie nie jak funkcja po swojej prawej stronie, ale jak porządny operator po obu swoich stronach. Dla potrzeb deklaracji jednak, musimy zaminieć go na chwilę na normalną funkcję (zdjąć z niego niejako "infiksowość") przez obłożenie go nawiasami.
Podobnie prosto zdefiniujemy mnożenie:
infix 2 ~*
(~*) :: Polynomial -> Polynomial -> Polynomial
p1 ~* p2 = canonize_poly [(c1*c2, m1++m2) | (c1, m1) <- p1 , (c2, m2) <- p2]
Tym razem korzystamy z faktu, że mnożenie wielomianów (będących sumą jednomianów) jest sumą wszystkich możliwych iloczynów par jednomianów, z których jeden pochodzi od pierwszego a drugi od drugiego wielomianu. Plus oczywiście kanonizacja dla porządku. Załatwiamy to jedną operacją ujawnienia postaci listy.
Czas na:
Test 8:
Spróbujemy pomnożyć x*(x+y+z*x^2):
Main> tostring_poly $ x ~* (x ~+ (y ~+ z ~* (x ~* x))) where (x,y,z) =
([(1,[("x",1)])],[(1,[("y",1)])],[(1,[("z",1)])])
"x^3*z+x^2+x*y"
Cały wielomian zrealizowany został jako wynik operacji na trywialnych wielomianach x, y, i z które zdefiniowane są po słówku where, wszystkie na raz w jedej krotce.
Wynik znowu zgodnie z oczekiwaniami.
Mając już takie narzędzia, zajmijmy się na chwilę klasyką, tj. tadam... dwumian Newtona. Policzmy go dla potęgi 5 dajmy na to:
Test 9:
Main> tostring_poly $ ((((a ~* a) ~* a) ~* a) ~*a) where a = [(1,[("x", 1)]),(1,[("y", 1)])]
"10*x^3*y^2+10*x^2*y^3+5*x^4*y+5*x*y^4+y^5+x^5"
Cóż, w nieco nieortodoksyjnym porządku, ale to czego należało się spodziewać.
Jak czytelnik pewnie zauważył zadawanie wielomianów w naszej surowej postaci nie jest wygodne, z tego względu pokusimy się o bardzo prosty parser, zamieniający reprezentację wielomianu jako zrozumiałego dla człowieka łańcucha znaków na reprezentację wewnętrzną. Ogólnie pisanie parsera wymaga sporo delikatności i uwagi, ale my napiszemy coś naprawdę bardzo prostego cedując na użytkownika staranność w zadawaniu wejścia dla parsera.
By zrealizować nasz parser, potrzebować będę tokenizera, tj funkcji zaminiającej łańcuch znaków na listę łańcuchów znaków będących rezultatem podzielenia listy oryginalnej na fragmenty rozdzielone z góry zadanym znakiem. Np napis "Ala ma kota" po "tokenizacji" względem znaku ' ' (spacja) stanie się listą ["Ala","ma","kota"]
Oto nasza funkcja tokenize, bioraca jako argument znak i łańcuch znaków a zwracającą stosowną listę łańcuchów:
tokenize :: Char -> String -> [String]
tokenize v "" = []
tokenize v x = tokenize_raw v x [] [] where
tokenize_raw v [] [] rv = rv
tokenize_raw v [] cs rv = (rv++[cs])
tokenize_raw v (f:r) cs rv | f == v = tokenize_raw v r [] (rv++[cs])
| otherwise = tokenize_raw v r (cs ++ [f]) rv
Sprawdźmy działanie naszego tokenizera:
Test 10:
Main> tokenize ' ' "Ala ma kota"
["Ala","ma","kota"]
Dokładnie jak się spodziewaliśmy.
Wykorzystamy teraz funkcję tokenize do parsowania wielomianów. Strategia jest następująca. Najpierw łańcuch podzielimy funkcją tokenize względem znaku '+', następnie każdy z tak otrzymanych kawałków podzielimy wgledem znaku '*' a potem każdy z nich względem znaku '^'. Stosownie do tego co otrzymamy w ostatniej fazie podziału spróbujemy odbudować wielomian odpowiednie interpretując otrzmane kawałki jako wielomiany i kombinując je w wielomian funkcją foldl, kumulując je już to funkcją ~* już to funkcją ~+ stosownie do tego reprezentację jakich fragmentów scalamy.
parse_poly :: String -> Polynomial
parse_poly = foldl (~+) [] $ map parse_coeff $ tokenize '+' s where
parse_coeff r = foldl (~*) [(1,[])] $ map parse_mono $ tokenize '*' r where
parse_mono x = parse_raw $ tokenize '^' x where
isNumber l = and $ map isDigit l
convertToInt l = toInteger $ foldl (\x y -> 10*x + y) 0 $ map digitToInt l
parse_raw [] = []
parse_raw [a,b] = [(1,[(a, convertToInt b)])]
parse_raw [a] | isNumber a = [(convertToInt a,[])]
| otherwise = [(1,[(a,1)])]
Z nowych elementów wystąpiły tu fukcje z załadowanego na początku modułu Char, tj. isDigit (mówiąca czy znak odpowiada cyfrze) i digitToInt (zamieniająca znak odpwiadający cyfrze na odpowiadającą tej cyfrze liczbę).
Przetestujmy:
Test 11:
Main> parse_poly "x+y"
[(1,[("y",1)]),(1,[("x",1)])]
Main> parse_poly "x+2*y*z^2+123"
[(123,[]),(2,[("y",1),("z",2)]),(1,[("x",1)])]
Main> tostring_poly $ parse_poly "x+2*y*z^2+123"
"123+2*y*z^2+x"
Jako ostatnią póki co zaimplementujmy jeszcze jedną operację - operację podstawiania. Pozwoli nam ona w prosty sposób zadawać nawet dość trudne wielomiany. Operacja podstawiania polega na tym, że za pewną zmienną w zadanym wielomianie podstawiamy inny wielomian, dokonujemy na tak otrzymanym wyrażeniu operacji algebraicznych by w efekcie otrzymać wielomian. Poniżej fukcja przyjmująca w argumencie zmienną za którą podstawiamy, wielomian do którego podstawiamy i wielomian podstawiany. Dotychczasowa wiedza powinna wystarczyć do samodzielnej jej analizy.
subst :: Var -> Polynomial -> Polynomial -> Polynomial
subst v bs with = foldl (~+) [] $
map (\(c, p)-> tms c $ subst_mono v p with) bs where
tms c = map (\(x,y)->(c*x, y))
subst_mono lv m w = foldl (~*) [(1,[])] $
map (\(x,n)-> if x==lv then foldl (~*) [(1,[])] $ [w|i<-[1..n]]
else [(1,[(x,n)])]) m
Sprawdżmy w działaniu.
Test 12:
Znowu dwumian Newtona - ale tym razem poszalejmy:
Main> tostring_poly $ subst "a" (parse_poly "a^15") (parse_poly "x+y")
"6435*x^8*y^7+6435*x^7*y^8+5005*x^9*y^6+5005*x^6*y^9+3003*x^10*y^5+3003*x^5*y^10+1365*x^11*y^4+1365*x^4*y^11+455*x^12*y^3+455*x^3*y^12+105*x^13*y^2+10
5*x^2*y^13+15*x^14*y+15*x*y^14+y^15+x^15"
Hmmm... Ręcznie sprawdzić będzie ciężko.
Jak widać Haskell mógłby sobie jakoś poradzić z prostą szkolną algebrą
Na dziś kończymy zabawę. Wkrótce postaram się ulepszyć i rozbudować (nieco) tę zabawkę i poigrać trochę z takimi tematami jak wielomiany symetryczne, wyróżnik, a może i dalej : eliminacja kwantyfikatorów i twierdzenie Tarskiego.
Na razie: wszystkim uczniom i nauczycielom (szczególnie matematyki) życzę powodzenia i cierpliwości w zaczynającym się roku szkolnym.
1
Operacja ujawnienia postaci listy jest z natury podobna do matematycznego zapisu zbiory (bądź klasy) w postaci { : }, gdzie po lewej stronie znaku ':' pojawia się funkcja (być może identyczność) dla argumentów spełniajacych warunek po stronie prawej logiczny warunek opisujący wybrane elementy. Pamiętajmy jednak - listy to nie zbiory!
Subskrybuj:
Posty (Atom)
Posty
