✎ pl:dydaktyka:pp:haskell:lab-intro [aiWiki]

Ta strona jest tylko do odczytu. Możesz wyświetlić źródła tej strony ale nie możesz ich zmienić.
====== Lab: Wprowadzenie do Haskella ======

Tematyka:
  * podstawy GHCi: obsługa, ładowanie modułów, wbudowane funkcje, trace
  * podstawy Haskella: arytmetyka, wyrażenia logiczne, definiowanie prostych funkcji

===== GHCi =====

**ghci** jest interaktywnym środowiskiem, które pozwala na wykonywanie wyrażeń Haskella w trybie interaktywnym.\\
**ghc** jest natomiast kompilatorem języka Haskell.  

<code>
:help    		    wyświetla pomoc wewnątrz GHCi                               (:h,:?)
:quit                       wyjście z GHCi
:load [*]<module> ...       załaduj moduły/skrypty <module>... do GHCi                  (:l)
                            np. można załadować nasz kod:
                            $Prelude>:l hello.hs
:reload                     przeładuj załadowane moduły (pomocne przy zmianie źródeł	(:r)
:			    powtórz ostatnie polecenie GHCi
:browse [<module>]          przeglądnij zawartość modułu <module>
:module [+/-] [*]<mod> ...  zmień kontekst wykonywania poleceń GHCi (efektywnie         (:m)
                            ładuje funkcje z innego modułu do aktualnej przestrzeni nazw np. 
                            $Prelude>:m Data.List
                            $Prelude Data.List>
:info [<name> ...] 	    wyświetl informacje o danej nazwie                          (:i)
:type <expr>                pokaż typ wyrażenia <expr>			                (:t)  
</code>

===== Proste wyrażenia =====

W GHCi można wykonywać funkcje Haskella i wyniki są wyświetlane po ich wykonaniu, proszę przetestować:

  * arytmetyka: <code>
$Prelude> 13 + 90
$Prelude> 9 - 17
$Prelude> 6 * 5
$Prelude> 9 / 2
</code>
  * algebra Boola: <code>
$Prelude> True && False
$Prelude> True || False
$Prelude> not False
</code>
  * porównania: <code>
$Prelude> 2 == 3
$Prelude> 4.5 /= 6.7
$Prelude> "abc" == "abc"
</code>
  * wywołania funkcji wbudowanych: <code>
$Prelude> min 2 3
$Prelude> succ 8
$Prelude> max 9 7
</code>
    * W jaki sposób można sprawdzić jakie mamy funkcje do dyspozycji w standardowym module Prelude :?: 
    * Proszę też sprawdzić jakie typy mają następujące i powyższe wyrażenia<code>
$Prelude> 1
$Prelude> True
$Prelude> 7.2
</code>
  * priorytety operatorów: <code>
$Prelude> succ 3 + max 8 0 * 2
$Prelude> succ 1/10
$Prelude> succ 1/10 == succ 0.1
</code>
    * Co zwróciły powyższe wyrażenia? 
    * Dlaczego ostatnie wyrażenie zwróciło False?
  * Każda funkcja przyjmująca dwa argumenty, może zostać wywołana w postaci infixowej, przez zawarcie jej nazwy pomiędzy znakami %%``%%, tak samo dowolny operator może zostać wywołany w postaci prefixowej z użyciem nawiasów %%()%%<code>
$Prelude> 2 `max` 3
$Prelude> (+) 2 3
</code>
  * W Haskellu " " (spacja) ma najwyższy priorytet i ma znaczenie aplikacji argumentu do funkcji, ponadto pozostałe operatory zdefiniowane w Prelude mają następujące priorytety:

^ Precedence ^ Left associative op. ^ Non-associative op. ^ Right associative op. ^
|  9|''!!''| |''.''|
|  8| | |''%%^%%'', ''%%^^%%'', ''%%**%%''|
|  7|''*'', ''/'', ''`div`'',| | |
|:::|''`mod`'', ''`rem`'', ''`quot`''| | |
|  6|''+'', ''-''| | |
|  5| | |'':'', ''%%++%%''|
|  4| |''%%==%%'', ''/='', ''<'', ''%%<=%%'', ''>'', ''>='',| |
|:::| |''`elem`'', ''`notElem`''| |
|  3| | |''&&''|
|  2| | |''%%||%%''|
|  1|''%%>>%%'', ''%%>>=%%''| | |

W ramach ćwiczenia proszę pododawać nawiasy do poniższych wyrażeń korzystając z informacji do tej pory zdobytych. Nawiasy należy wstawiać tak, żeby znaczenie wyrażenia nie uległo zmianie i każde podwyrażenie było otoczone nawiasem:
<code>
$Prelude> True == False && True || False
$Prelude> max 1 20
$Prelude> succ 1/10
$Prelude> 12 + 4 * 7 `div` 4 ^ 3
$Prelude> elem 2 [1,2,3] : []
$Prelude> (+) 2 3 * 4
$Prelude> length [1,2,3] : 1+7:[]
$Prelude> 2:[]++[1,2,3]
$Prelude> True == False == False
</code>

===== Listy =====

Listy w Haskellu są podstawowym typem danych złożonych i jednym z najbardziej eksploatowanych przez algorytmy.
  * definiowanie listy:<code>
$Prelude> [1,2,3,89]
$Prelude> [1..100]
$Prelude> ['a'..'z']
$Prelude> [1,6..100]
$Prelude> ['a','f'..'z']
$Prelude> [1.0,1.1..5.0] -- uwaga na precyzję, raczej nie używać zmiennoprzecinkowych liczb, można to zrobić lepiej
</code>
  * operacje na listach:<code>
$Prelude> 1:[] -- wstawianie na początek listy
$Prelude> 1:[1,23,4] -- wstawianie na początek listy
$Prelude> head [1,4,5] -- pierwszy element listy
$Prelude> tail [1,4,5] -- wszystko poza pierwszym
$Prelude> last [1,4,5] -- ostatni element
$Prelude> init [1,4,5] -- wszystko poza ostatnim
$Prelude> length [1,4,5] -- długość listy
$Prelude> take 2 [1,4,5] -- wybierz dwa elementy z listy
$Prelude> elem 4 [1,4,5] -- czy 4 należy do listy
$Prelude> 4 `elem` [1,4,5] -- to samo tylko w postaci infixowej
$Prelude> [1,7,0] ++ [1,4,5] -- złączenie list
</code> Trzeba pamiętać jednak, że implementacja opiera się o listę jednokierunkową, dlatego operacja length ma złożoność obliczeniową O(n) i złączenie list %%++%% musi przeglądnąć całą listę po lewej stronie, żeby znaleźć koniec listy. Najwydajniejsze algorytmy to te, które działają od lewej do prawej na liście.
  * Haskell cechuje się leniwym wykonywaniem kodu (ang. lazy evaluation), czyli wykonuje kod dopiero jak jest to niezbędne, w przeciwnym wypadku odkłada obliczenia na później<code>
$Prelude> head [1..] -- pobierz pierwszy element z nieskończonej(!) listy
$Prelude> take 20 ([1,2..78]++[(Debug.Trace.trace "Hej ja" 100)])</code> pobierz 20 pierwszych elementów z listy, utworzenie drugiej listy nie będzie potrzebne, bo pierwsza lista ma więcej elementów, nie zostanie wypisany komunikat, bo kod się nigdy nie wykona, funkcja **trace** z modułu **Debug.Trace** wypisuje łańcuch znaków podany jako pierwszy argument i zwraca drugi argument<code>
$Prelude> take 79 ([1,2..78]++[(Debug.Trace.trace "Hej ja" 100)]) -- tym razem pierwsza lista nie wystarczyła
</code>
  * Jak wygenerować dokładnie 17 pierwszych liczb nieparzystych większych od zera :?: a 19, 23 :?: (wykorzystaj leniwą ewaluację)
  * Wyrażenia listowe<code>
$Prelude> [2*x+1| x <- [0..10]] --tworzy listę elementów postaci 2*x+1, gdzie x są kolejnymi wartościami z listy [0..10]
$Prelude> [x| x <- [0..21],x `mod` 2 == 1] -- tworzy listę elementów postaci x, gdzie x są kolejnymi wartościami z listy [0..21] i dodatkowo spełniony jest warunek, że x jest nieparzysty
$Prelude> [x| x <- [0..21],odd x] -- jak wyżej tylko z gotową funkcją z Prelude
$Prelude> [if odd x then 'a' else 'b'| x <- [1..5]]
$Prelude> [x+y*z| x <- [1..5], y<-[7..10], z<-[14,17],2*x/=y]
</code>

===== Krotki =====

Listy mogą przechowywać tylko elementy tego samego typu, natomiast elementy różnych typów można grupować w krotki (które mogą być np. elementami listy)
  * Krotki definiujemy<code>
$Prelude> (2,"String")
$Prelude> (1,'a',9.1,87)
</code>
  * Proszę sprawdzić typ powższych wyrażeń i np. [1,2,3], [1,0], krotki nie są jednak bardzo elastyczne, jednak istnieje kilka funkcji operujących na nich:<code>
$Prelude> fst (2,"String")
$Prelude> snd (2,"String")
$Prelude> zip ["Maciek","Damian","Wojtek","Anna"] [203009,203017,203002,203081]
$Prelude> zip [1..] ["Intelx86","Intel64","ARM","Sparc32"] -- listy nie muszą być równej długości
$Prelude> fst (unzip [(1,"a"),(2,"b"),(3,"c")])
</code>
  * Proszę wypisać listę zawierającą krotki reprezentujące poprawne trójkąty o bokach o długości x takich, że 3<x<17 :?:
  * Proszę z tych trójkątów wybrać trójkąty prostokątne :?:

===== Funkcje =====

Haskell jest językiem funkcyjnym, czyli zorientowanym na funkcje, ponadto funkcje są pozbawione "efektów ubocznych" i są funkcjami w matematycznym sensie, czyli dla ustalonego parametru funkcja zwaraca zawsze tą samą wartość. Np. w C funkcja wczytająca pojedynczy znak: <code c> int getchar(void)</code> nie jest funkcją w matematycznym sensie, kolejne jej wywołania mogą zwrócić inne wartości mimo wciąż tego samego argumentu. Funkcje mogą być obiektami zwracanymi przez inne funkcje. Właściwie w Haskellu istnieją tylko funkcje jednoargumentowe, a możliwość przyjmowania więcej niż jednego argumentu realizuje się przez zwrócenie dla konkretnego argumentu innej funkcji. Np.<code>
$Prelude> (2 *) 3   --aplikuje 2 do funkcji (*), a następnie do zwróconej funkcji aplikowany jest argument 3
$Prelude> (3 *) -- dostajemy komunikat o błędzie, bo GHCi nie wie jak wyświetlić rezultat, czyli funkcję przyjmującą jeden argument
$Prelude> ((2 *).(+ 3)) 1 -- kolejne funkcje można składać (tak jak w matematycznym sensie składanie funkcji) przy pomocy operatora .
$Prelude>  ((take 3).(:[4..9])) 7 -- co robi ta funkcja :?:
</code>

Zdefiniujemy teraz własne funkcje. W tym celu proszę utworzyć nowy plik z rozszerzeniem .hs. Proszę w nim utworzyć następującą funkcje:<code>
incAndTriple v = ( v + 1 ) * 3

specialCases 1 = "Hello"
specialCases 2 = " "
specialCases 3 = "World"
specialCases 4 = "!"
specialCases x = "???"
</code>
Proszę załadować kod do GHCi, (jak to zrobić:?:) i wykonać np. <code>
$Prelude> incAndTriple 3
$Predlue> map specialCases [1..4]
$Predlue> concat (map specialCases [1..4])
$Predlue> concat (map specialCases [1..6])
</code>
**map** to specjalna funkcja wbudowana, która aplikuje jednoargumentową funkcję podaną jako pierwszy argument do każdego elementu listy podanej jako drugi argument i zwraca listę. Można też korzystać z <code>
$Predlue> map (3*) [1..10]
</code>
**concat** natomiast spłaszcza listę, **String** w Haskellu to w rzeczywistości synonim listy znaków, dlatego spłaszczenie listy Stringów, daje listę znaków, czyli **String**.

  * Proszę zdefiniować własne wersje funkcji: 
    * **head**,
    * **length**, 
    * **take**, 
    * **map**,  
    * **%%++%%**
  * PODPOWIEDZI:
    * w Haskellu można stosować pattern matching, ale tylko z użyciem konstruktorów typów Haskellowych:
      * : jest konstruktorem listy np. <code>getSecondElement (_:x:_) = x</code>
      * (,) jest konstruktorem krotki dwuelementowej <code>snd (_,x) = x</code>
      * (,,) jest konstruktorem krotki trójelementowej itd. <code>trd (_,_,x) = x</code>
      * Nazwa jest konstrukotrem typu Nazwa (z wielkiej litery), konstruktory mogą być sparametryzowane np. <code>getJust (Just x) = x</code>
    * _ (podkreślenie) nie interesuje nas dopasowanie tego argumentu
    * raz utworzone dane są już niezmienne (ang. immutable, tak jak np. obiekt klasy String w Javie), żeby zwrócić fragment listy, trzeba utworzyć jej odpowiednią kopię.
    * rekurencja rozwiązuje większość problemów :!:
    * ' (pojedynczy apostrof) jest zwykłym znakiem i może tworzyć w Haskelu ważną nazwę identyfikatora, można np. zdefiniować funkcje length'
    * w Haskellu można zdefiniować dowolny operator, przy definicji należy wykorzystać skłądnię prefixową<code>(+++) x y = x+y</code>

===== Debugger =====

Informacje o poziomie debug można sygnalizować wspomnianą już funkcją Debug.Trace.trace, pomocna też będzie funkcja **show**, która pokazuje reprezentację wartości w postaci łańcucha znaków.

Poza tym w GHCi jest wbudowany mechanizm do debuggowania kodu. 
<code>
   :break [<mod>] <l> [<col>]  ustawia breakpoint w wzynaczonej lokalizacji <mod> moduł, <l> linia kodu, <col> kolumna
   :break <name>               lub na funkcji o nazwie <name>
   :step                       wykonanie następnego kroku po zatrzymaniu się na breakpoincie
   :list                       pokaż kod na którym się zatrzyał debugger
   :print [<name> ...]         pokaż wartości zmiennych <name> ...
   :continue                   wznów wykonanie do następnego breakpointu
   :trace [<expr>]             zacznij śledzić wykonanie od tego breakpointu, albo całego wyrażenia <expr>
   :history                    pokaż śledzone wywołania
</code>

Jako przykład rozważmy algorytm quicksort (który w Haskellu nie najlepiej się sprawuje ze względu na listy):
<code>
import Debug.Trace                                                    -- importuje wszystkie funkcje z modułu Debug.Trace
quicksort [] = []                                                     -- definiuje zachowanie na pustej liście 
quicksort xx@(x:xs)                                                   -- @ inforumuje żeby zmienna xx była widoczna jako całość i jako poszczególne części x i xs
                | trace ("qs: "++ show x ++ " " ++show xx) False = [] -- zastosowano tu składnie | case = execute | case2 = execute2, ponieważ trace zwróci False ta gałąź się nigdy nie wykona, ale zostanie wypisana wiadomość na stderr
                | otherwise = quicksort low ++ x : quicksort high     -- otherwise to nic innego jak True, można nawet sprawdzić True == otherwise w GHCi ta gałąź się wykona w pozostałych przypadkach (w tym wypadku zawsze), następuje konkatenacja listy posortowanej quicksortem z listą składającą się z elementu rodzielającego i listy posortowanej quicksortem
                              where low = [e | e <- xs, e < x]        -- w bloku where następują definicje zmiennych lokalnych low to podlista xs z wartościami mniejszymi od strażnika x
                                    high = [e | e <- xs, e >= x]      -- natomiast high to lista w z wartościami większymi lub równymi strażnikowi 
</code>
trace został użyty tylko w celu ukazania leniwego podejścia Haskella i zaprezentowania możliwości śledzenia wartości w kodzie:
proszę przetestować powyższy kod dla wejść:
<code>
$Prelude> quicksort [3,56,90,23,1,2,5,7,23,89,67]
$Prelude> take 4 (quicksort [1,8,3,5,7,90,34,21,45,9,17])
</code>
Proszę też przetestować kombinację poleceń GHCi:
<code>
:break Main 5 31
:trace quicksort [1..20]
:line
:step
</code>