Tajny Skrypt Lab SML^{1} v 0.33

Marcin Benke^{2}

benke@mimuw.edu.pl

redakcja i rozdział 7 Grzegorz Grudziński^{2}

                     gsg@mimuw.edu.pl

rozdział 8

Mikołaj Konarski^{2}

        mikon@mimuw.edu.pl

pozostałe rozdziały

10 października 2000

1Nazwa jest historyczna. 2Instytut Informatyki, Uniwersytet Warszawski.

Spis rzeczy

1 Wyrażenia 3 2 Listy & stuff 5 3 Rekursja ogonowa, akumulatory i różne takie 8 4 Definiowanie typów 11 5 Funkcje wyższych rz_{}edów 14 6 Funkcje jeszcze wyższych rz_{}edów 16 7 Operacje na tekstach 19 8 Leniwość 21 9 Moduły: struktury i sygnatury 22 10 Moduły: funktory 26 A Jak zaliczyć laboratorium 28 B Rozwi _{}azania niektórych zadań 30 C Jak pracować z kompilatorem SML-a 36

Ostrzeżenie

#include <std/disclaimer.h> ;-)

Ten dokument, zgodnie ze swym tytułem, nie tylko nie jest oficjalnym skryptem, ale co wi_{}ecej — jest tajny.

Ponadto nie s _{}a to notatki do wykładu, tylko do pracowni. Wiedza podawana jest tu wyrywkowo i skrótowo, a nacisk położony jast na zadania.

Tajne Kolegium Redakcyjne

Rozdział 1

Wyrażenia

Program w j_{}ezyku funkcyjnym to wyrażenie, a wykonanie programu to obliczenie wartości wyrażenia. Przykłady wyrażeń:

3;   (* Comment: semicolon ";" tells the interpreter *)
(1 + 2) * 1;   (* to evaluate expressions. *)
("Hi! I'm the first element of this tuple", 3, false);
if ((2.3 > 5.4) orelse true) then "yes" else "no";
(fn n => 2 * n) 3;
fn x => x;

Wielkie i skomplikowane wyrażenia zapisuje si_{}e wygodniej używaj _{}ac konstrukcji let...in...end oraz deklaracji:

let
   val text = "I'm a string"
in
   text^". Yes, "^text^". Sure, "^text^"!"
end;
val twice = (fn n => 2 * n);
twice;
twice (twice 3);
fun twice' n = 2 * n;
twice 3 = twice' 3 andalso twice' 4 = twice 4;

Przykład z pi pokazuje pewn _{}a istotn _{}a ceche deklaracji. Jaka jest wartość wyrażenia area 5.0 z ostatniej linii tego przykładu?

val pi = 3.14;
fun area r = pi * r * r;
area 5.0;
val pi = 1.0;
area 5.0;

Pot_{}eżnym narz_{}edziem programowania funkcjnego jest rekurencja:

fun fact n = if n <= 1 then 1 else n * (fact (n - 1));
fun fib n = if n <= 1 then 1 else (fib (n - 1)) + (fib (n - 2));
fact (fib 4);
fib;

Zadanie

Zadanie 1.1 Oto definicja funkcji fib':

fun fib' n =
    let
        fun fib_pair n =
            if n <= 1 then (1, 1)
                      else let
                               val (j, k) = fib_pair (n - 1)
                           in
                               (j + k, j)
                           end
    in
        #1 (fib_pair n)
    end

(#1 oznacza wzi_{}ecie pierwszego elementu tupla).

Udowodnij przy pomocy indukcji, że dla każdego n

fib n = fib’ n.

Koszt czasowy fib n jest wykładniczy wzgl_{}edem n. Jaki jest koszt fib’ n?

Listy & stuff

Poznaliśmy tuple:

(2, "errr", 3.14);

Listy to coś zupełnie innego:

[2, 55, 15346];
["This", "is", "a", "list", ", yeah."];
[];

Te nawiasy kwadratowe to skrótowy sposób zapisu list. Tak naprawd_{}e listy konstruuje si_{}e w ten sposób:

2::(55::(15346::nil));

lub bez niepotrzebnych nawiasów:

2::55::15346::nil;
"This"::"is"::"a"::"list"::", yeah."::nil;
nil;

Mówi _{}ac ściśle: infiksowy konstruktor :: dostaje jako argumenty wartość x i list_{}e l, której elementy s _{}a tego samego typu co x, i daje w wyniku l z doklejonym na pocz _{}atku elementem x. Na przykład (używaj _{}ac mieszanej notacji) 1::[2, 3, 4] reprezentuje t_{}e sam _{}a list_{}e co [1, 2, 3, 4]

Kilka przykładów:

val mylist = [1, 2, 3];
fun null l = (l = []);
null mylist;
null [];
fun interval (n, m) = if n > m then [] else n::interval (n+1, m);
interval (~31, 72);

Jest troche wbudowanych funkcji na listach, w szczególności hd oddaj _{}aca pierwszy element listy i tl, oddaj _{}aca list_{}e bez pierwszego elementu.

val head = hd mylist
val tail = tl mylist
val what = head :: tail

Funkcje na listach można definiowac za pomoca pattern matchingu

fun null [] = true
 | null (head::tail) = false

a tu b_{}edzie potrzebny wyj _{}atek (exception):

exception Empty
fun hd [] = raise Empty
 | hd (head::tail) = head

Dalej już łatwo :-)

Zadania

Zadanie 2.1 Przy pomocy pattern matchingu napisz funkcj_{}e tl.

Zadanie 2.2 Używaj _{}ac funkcji null, hd, tl, napisz funkcj_{}e sum, która dodaje do kupy wszystkie elementy danej listy liczb całkowitych. Zrób to samo przy pomocy pattern matchingu.

Zadanie 2.3 Używaj _{}ac funkcji null, hd, tl, napisz funkcj_{}e length, która oblicza długość listy. Zrób to samo przy pomocy pattern matchingu.

Zadanie 2.4 Używaj _{}ac funkcji null, hd, tl, napisz funkcj_{}e last, która daje w wyniku ostatni element listy. Zrób to samo przy pomocy pattern matchingu.

Zadanie 2.5 Napisz funkcj_{}e append, która ł _{}aczy dwie listy. Na przykład:

append ([1, 2], [3, 4, 6]) = [1, 2, 3, 4, 6]

Zadanie 2.6 Napisz funkcje take i drop, z parametrem (l,n), które odpowiednio bior _{}a lub odrzucaj _{}a pierwsze n elementów listy l. Upewnij si_{}e, że dla każdego (l, n)

append (take (l, n), drop (l, n)) = l

Zadanie 2.7 Napisz, korzystaj _{}ac z funkcji drop i hd, funkcj_{}e nth, która daje nty element listy. Czy funkcja działałaby szybciej, gdyby skorzystać z take

i last?

Zadanie 2.8 Napisz funkcj_{}e flatten, która dostaje list_{}e list, a daje w wyniku list_{}e wszystkich elementów tych list (nie martw si_{}e powtórzeniami czy kolejności _{}a).

Zadanie 2.9 Napisz quicksort.

Zadanie 2.10 Przy pomocy list napisz funkcje realizuj _{}ace arytmetyk_{}e na DU-ŻYCH liczbach całkowitych. Użyj ich do policzenia 500! albo lepiej 1000!. Jaka jest złożoność liczenia n! w ten sposób?

Zadanie 2.11 Napisz to samo w C lub Pascalu. Porównaj czas zużyty na pisanie i wykonanie programu.

Poza tym można zrobić mergesort albo funkcje obliczaj _{}ace wszystkie permutacje, kombinacje, etc. danej listy albo par_{}e funkcji: zip i split; zip dostaje dwie listy liczb całkowitych a oddaje list_{}e par: para pierwszych elementów obu list, potem drugich, itd, split jest funkcj _{}a (prawie) odwrotn _{}a.

Wszystkie napisane programy warto przetestować — jest to łatwe i przyjemne, bo używamy interpretera.

Zach_{}ecamy do wszelakich eksperymentów!

Rekursja ogonowa, akumulatory i różne takie

Cz_{}esto funkcj_{}e można zdefiniować na kilka istotnie rożnych sposobów. Sztandarowym przykładem jest funkcja daj _{}aca n–t _{}a liczb_{}e Fibonacciego, wśród której najprostszych definicji istniej _{}a drastyczne rożnice złożoności czasowej. Duż _{}a rodzin_{}e innych przykładów stanowi _{}a funkcje przy których definiowaniu można ale nie trzeba używać akumulatora tzn. dodatkowego parametru który kumuluje składowe wyniku.

Oto definicja silni bez akumulatora:

fun fact n = if n <= 1 then 1 else n * fact (n - 1)

i z akumulatorem:

fun fact_tr n =
    let
        fun fact_acc (acc, k) = if k <= 0 then acc
                                else fact_acc (acc * k, k - 1)
    in
        fact_acc (1, n)
    end

przy czym widać, że dla każdego n mamy

fact n = fact tr n = n!.

Jak wygl _{}ada obliczanie fact 4? Funkcja fact 4 wywołuje fact 3, zapami_{}etuj _{}ac, że wynik tego wywołania powinna pomnożyć przez 4, nim odda go jako swój wynik. Funkcja fact 3 wywołuje fact 2, zapami_{}etuj _{}ac, że wynik tego wywołania powinna pomnożyć przez 3. Funkcja fact 2 wywołuje fact 1, zapami_{}etuj _{}ac, że wynik tego wywołania powinna pomnożyć przez 2. Teraz fact 1 oddaje 1. Nast_{}epnie fact 2 mnoży to przez 2 i oddaje rezultat tego mnożenia, czyli 2. Potem fact 3 mnoży to przez 3 i daje 6. Potem fact 4 mnoży to przez 4 i oddaje 24. A wi_{}ec kolejność mnożeń była nast_{}epuj _{}aca: ((1 ∗ 2) ∗ 3) ∗ 4.

Twierdz_{}e, że kolejność mnożeń przy obliczaniu fact_tr 4 jest odwrotna, czyli ((4 ∗ 3) ∗ 2) ∗ 1. Zobaczmy: fact_tr 4 wywołuje fact_acc (1, 4), który po wykonaniu jednego mnożenia na rozruch wywołuje fact_acc (4, 3). Nast_{}epnie fact_acc (4, 3) mnoży 4 przez 3 i wywołuje fact_acc (12, 2). Nast_{}epnie fact_acc (12, 2) mnoży 12 przez 2 i wywołuje fact_acc (24, 1). Nast_{}epnie fact_acc (24, 1) mnoży 24 przez 1 i wywołuje fact_acc (24, 0).

(*) A teraz fact_acc (24, 0) oddaje 24 i wynik ten zwracany jest już bez

     zmian przez kolejno fact_acc (24, 1), fact_acc (12, 2), fact_acc (4, 3),
     fact_acc (1, 4) i fact_tr 4.

Skoro kolejność mnożeń jest odwrotna, fact i fact_tr rzeczywiście istotnie si_{}e od siebie różni _{}a. Różnic jest wi_{}ecej. Na przykład definicja fact jest niew _{}atpliwie bardziej czytelna od fact_tr. A z drugiej strony w fact_tr wyst_{}epuje wył _{}acznie tzw. rekursja ogonowa (tail recursion), przez co fact_tr wykonuje si_{}e nieco szybciej i zużywa nieco mniej pami_{}eci niż fact, w którym rekursja nie jest ogonowa.

Kiedy funkcja zawiera rekursj_{}e ogonow _{}a? Wtedy, kiedy w definicji funkcji wołanie rekurencyjne nie jest podwyrażeniem żadnego innego wyrażenia (z wyj _{}atkiem drugiej lub trzeciej gałezi wyrażenia warunkowego). Jeśli rekursja jest ogonowa, wynik wykonania każdej funkcji wołanej jest przekazywany bez modyfikacji jako wynik funkcji wołaj _{}acej, tak jak w miejscu oznaczonym (*).

Każdy przywoity kompilator zast_{}epuje sekwencj_{}e powrotów tak _{}a jak (*) jedn _{}a instrukcj _{}a skoku, a także używa jednego rekordu aktywacji dla wszystkich rekurencyjnych wcieleń funkcji. W ten sposób rekurencja jest automatycznie zast_{}epowana iteracj _{}a.

Zadania

Zadanie 3.1 Napisz wersj_{}e funkcji length z rekursj _{}a ogonow _{}a.

Zadanie 3.2 Napisz funkcj_{}e decimal, która dostaje list_{}e cyfr i odaje liczb_{}e jaka powstaje z tych cyfr, jeśli je ustawić za sob _{}a (or something). np.

     decimal [1, 9, 9, 5] ma dać 1995.

Zadanie 3.3 Napisz dwie wersje funkcji reverse odwracaj _{}acej list_{}e. Jedna z tych wersji ma działać w czasie liniowym.

Zadanie 3.4 Czy można napisać ogonow _{}a wersj_{}e funkcji take? Jeśli tak, to czy warto jej używać? Odpowiedź uzasadnij pełnymi zdaniami.

Zadanie 3.5 Napisz wersj_{}e funkcji interval (z poprzedniego rozdziału) z rekursj _{}a ogonow _{}a. Nie używaj reverse ;-).

Zadanie 3.6 Napisz funkcj_{}e real_max, która dostaje list_{}e liczb rzeczywistych i oddaje najwi_{}eksz _{}a z nich. Napisz dwie istotnie różne wersje. Która wersja bardziej Ci si_{}e podoba ?

Zadanie 3.7 To inna wersja funkcji quicksort:

fun quicksort [] = [] : int list
  | quicksort [x] = [x]
  | quicksort (a::rest) =
    let fun split(left,right,[]) =
            quicksort left @ (a::quicksort right)
          | split(left,right,x::l) =
            if x < a then split(x::left,right,l)
            else split(left,x::right,l)
    in split([],[],rest)
    end

Porównaj j _{}a z wersj _{}a podan _{}a w rozwi _{}azaniu zadania z pracowni 2. Czytelność, ogonowość, akumulatorowość, etc.

Jak zwykle eksperymenty surowo wskazane!

Definiowanie typów

Można definiować typy:

datatype friend = PAT | SUSIE | JOE
datatype gift = BOTTLES_OF_BEER of int | BOOK

a przy pomocy pattern matchingu na tych typach tworzyć funkcje:

fun give PAT = BOTTLES_OF_BEER(10)
  | give SUSIE = BOOK
  | give JOE = BOTTLES_OF_BEER(3)
fun like (BOTTLES_OF_BEER(n)) = n > 7
  | like BOOK = true

Typy mog _{}a być rekurencyjne:

datatype int_list = INT_NIL | INT_CONS of int * int_list
fun sum INT_NIL = 0
  | sum (INT_CONS(i, rest)) = i + sum rest

wzajemnie rekurencyjne:

datatype friend_rec = PAT | SUSIE | ANYONE_WHO_GIVES_ME of gift_rec
and gift_rec = BOTTLES_OF_BEER of int | PHOTO of friend_rec
fun love PAT = false
  | love SUSIE = true
  | love (ANYONE_WHO_GIVES_ME(a_gift)) = like a_gift
and like (BOTTLES_OF_BEER(n)) = n > 7
  | like (PHOTO(my_friend)) = love my_friend

polimorficzne :

datatype 'a option = SOME of 'a | NONE
val int_some_list = [SOME(5), NONE, SOME(10), SOME(3), NONE]
val bool_some_list = [SOME(true), SOME(true), NONE, SOME(true)]
fun divide (NONE, _) = NONE
  | divide (_, NONE) = NONE
  | divide (SOME(x), SOME(y)) = if y = 0.0 then NONE else SOME(x / y)

fun pair_some (SOME(x), SOME(y)) = SOME(x, y)
 | pair_some _= NONE
fun divide2 (r, s) =
   case (pair_some (r, s))
     of NONE => NONE
      | (SOME(x, y)) => if y = 0.0 then NONE else SOME(x / y)

Znany nam wbudowany typ list jest rekurencyjny i polimorficzny i ma nast_{}epuj _{}ac _{}a definicj_{}e:

infixr 5 ::
datatype 'a list = nil | :: of ('a * 'a list)

A drzewo można zdefiniować na przykład tak:

datatype 'a tree = EMPTY | NODE of 'a tree * 'a * 'a tree

Zadania

Zadanie 4.1 Napisz wielkie mnóstwo funkcji na drzewach. Możesz napisać odpowiedniki wszystkich znanych Ci funkcji na listach. Możesz znaleźć jakieś funkcje specyficzne dla drzew, na przykład: obchodz _{}ace drzewo, zamieniaj _{}ace prawe poddrzewa z lewymi, etc. Możesz napisać funkcje z drzew w listy i z list w drzewa.

Zadanie 4.2 Zaimplementuj sortowanie drzewowe (treesort).

Wskazówka: W uporz _{}adkowanym drzewie binarnym liczba wyst_{}epuj _{}aca w w_{}eźle jest wi_{}eksza od wszystkich w lewym poddrzewie i mniejsza od wszyskich w prawym. Należy zdefiniować dwie główne funkcje. Jedn _{}a, która dostaje list_{}e liczb naturalnych, zaś oddaje uporz _{}adkowane drzewo binarne zawieraj _{}ace elementy tej listy. Drug _{}a, która dostaje uporz _{}adkowane drzewo binarne, a oddaje posortowan _{}a list_{}e jego elementów. Treesort to złożenie tych funkcji.

Zadanie 4.3 To jest bardzo ładna (i odrobink_{}e nieefektywna) definicja liczb naturalnych:

    datatype nat = ZERO | SUCC of nat

SUCC od successor - nast_{}epnik. Napisz kilka podstawowych funkcji i relacji (czyli funkcji typu nat->bool) na tych liczbach naturalnych.

Zadanie 4.4 Oto drzewo składni abstrakcyjnej (gramatyka) pewnego j_{}ezyka wyrażeń

    datatype expression =
        NUM of int
      | TIMES of expression * expression
      | PLUS of expression * expression

Napisz funkcj_{}e wyliczaj _{}ac _{}a wartość wyrażenia. Napisz wersj_{}e LL1 powyższej gramatyki. Napisz funkcj_{}e przekształcaj _{}ac _{}a wyrażenie w gramatyce LL1 w wyrażenie w podanej wyżej gramatyce. Napisz parser (używaj _{}ac gramatyki LL1) i lekser.

Wskazówka:

<1st_atom>   -> <numeral>
<2nd_atom>   -> <1st_atom> <2nd_atom'>
<2nd_atom'>  -> epsilon | * <1st_atom> <2nd_atom'>
<3rd_atom>   -> <2nd_atom> <3rd_atom'>
<3rd_atom'>  -> epsilon | + <2nd_atom> <3rd_atom'>
<expression> -> <3rd_atom>

Zadanie 4.5 Zdefiniuj typ drzew, w których każdy wierzchołek może mieć dowolnie wielu synów. Napisz troch_{}e funkcji na tych drzewach.

Funkcje wyższych rz_{}edów

Oto definicja funkcji sum:

    fun sum [] = 0
      | sum (a::rest) = a + sum rest

Oto definicja funkcji prod:

    fun prod [] = 1
      | prod (a::rest) = a * prod rest

Te funkcje s _{}a podejrzanie podobne.

Różni _{}a si_{}e tylko nazw _{}a i tym, że w deficji sum w pierwszym równaniu wyst_{}epuje 0 a w drugim +, podczas gdy w definicji prod, w tych samym miejscu w pierwszym równaniu jest 1 a w drugim *. Chciałoby si_{}e napisać funkcj_{}e foldr tak _{}a, żeby sum = foldr (+, 0) i prod = foldr (∗, 1). Nic prostszego:

    fun foldr (f, x) [] = x
      | foldr (f, x) (a::rest) = f(a, foldr (f, x) rest)

i tak powstała pierwsza funkcja wyższego rz_{}edu ;-).

Teraz można napisać:

    val sum = foldr (op +, 0)    (* op, because + is an infix identifier *)
    val prod = foldr (op *, 1)

Zauważmy, że foldr tak jak go zapisaliśmy jest polimorficzny:

    val sum_reals = foldr (op +, 0.0)
    fun and_pair (b, c) = b andalso c
    val and_list = foldr (and_pair, true)
    val list_identity = foldr (op ::, nil)
    val add_sizes = foldr (fn (s, rest_size) => (size s) + rest_size, 0)

(fn x => E, gdzie E to jakieś wyrażenie (być może zawieraj _{}ace x), oznacza funkcj_{}e która x przyporz _{}adkowuje E, jest to tak zwana anonimowa funkcja zapisana w tak zwanej lambda notacji).

Dla wygody przyj_{}eto, że wyrażenie w rodzaju (f a) b (aplikacja funkcji (f a) do argumentu b) można zapisywać bez nawiasów: f a b. Przykład:

(foldr (op +, 0)) [2, 44, 5] można zapisać jako: foldr (op +, 0) [2, 44, 5].

Na zakończenie obrazowe podsumowanie działania foldr:

foldr (f, x)[a_{1}, a_{2}, a_{3}, a_{4}] = f(a_{1}, f(a_{2}, f(a_{3}, f(a_{4}, x))))

lub w nieco czytelniejszym, infiksowym zapisie:

foldr (+, x)[a_{1}, a_{2}, a_{3}, a_{4}] = a_{1} + (a_{2} + (a_{3} + (a_{4} + x)))

Zadania

Zadanie 5.1 Przy pomocy foldr napisz append.

Zadanie 5.2 Przy pomocy foldr napisz length.

Zadanie 5.3 Przy pomocy foldr napisz funkcj_{}e good_max, która dostawszy n : int oraz l : int list daje najwi_{}eksz _{}a liczb_{}e z listy l wi_{}eksz _{}a od n, lub n jeśli w l nie ma żadnej liczby wi_{}ekszej od n.

Zadanie 5.4 Napisz funkcj_{}e map, która dostaje funkcj_{}e f i list_{}e l, a daje list_{}e wyników aplikacji funkcji f do kolejnych elementów l. Pisz _{}ac prosto:

map f [a_{1}, a_{2}, a_{3}, a_{4}] = [f a_{1}, f a_{2}, f a_{3}, f a_{4}].

Ten sam map zapisz przy pomocy foldr.

Zadanie 5.5 Przy pomocy map napisz funkcj_{}e first_cut, która dostaje list_{}e list a daje list_{}e pierwszych elementów tych list. Napisz first_cut nie używaj _{}ac map. Czy ta wersja nie przypomina Ci definicji map?

Zadanie 5.6 Napisz funkcj_{}e filter, która dostaje predykat p : 'a -> bool i list_{}e l : 'a list i daje list_{}e składaj _{}ac _{}a si_{}e z tych elementów l, które spełniaj _{}a p.

Napisz filter korzystaj _{}ac z foldr. Czy ta definicja jest bardziej czytelna?

Zadanie 5.7 Przy pomocy filter napisz divis_list, która wyławia z listy te liczby które s _{}a podzielne przez zadan _{}a liczb_{}e. Prawda, że ładnie?

Zadanie 5.8 Napisz foldl, czyli funkcj_{}e która zachowuje si_{}e w ten sposób

foldl (f, x)[a_{1}, a_{2}, a_{3}, a_{4}] = f(f(f(f(x, a_{1}), a_{2}), a_{3}), a_{4})

lub w infiksowym zapisie:

foldl (+, x)[a_{1}, a_{2}, a_{3}, a_{4}] = ((((x + a_{1}) + a_{2}) + a_{3}) + a_{4})

Zadanie 5.9 Używaj _{}ac mi_{}edzy innymi foldl napisz append. Zwykły append.

Zadanie 5.10 Używaj _{}ac mi_{}edzy innymi foldl napisz foldr. Korzystaj z doświadczeń z poprzedniego zadania.

Zadanie 5.11 Napisz odpowiedniki foldr, map i filter dla drzew.

Funkcje jeszcze wyższych rz_{}edów

Funkcje wyższych rz_{}edów spotyka si_{}e wsz_{}edzie. Weźmy choćby aplikacj_{}e funkcji do argumentu. Toć to twór wyższego rz_{}edu! Możemy go nazwać:

fun apply (f, a) = f a

i od tej pory zawsze pisać apply (g, b) tam gdzie dot _{}ad pisaliśmy g b :-].

Operacja składania dwóch funkcji jest oczywiście funkcj _{}a wyższego rz_{}edu. Pewna jej wersja jest nazwana i zdefiniowana w standardowej bazie SML-a:

infix 3 o
fun (f o g) x = f (g x)

i czasem si_{}e przydaje, np.:

val treesort = bst2list o list2bst

Nawet pospolite operacje arytmetyczne można zapisać jako funkcje wyższego rz_{}edu:

fun divide_by x y = y / x;
divide_by 2.0 4.0;
val divide_by_two = divide_by 2.0;
divide_by_two 10000000.0;
divide_by_two 342423423452345.0;
map (divide_by 3.0) [333.0, 12.0, 55.0, 5.0];

Definiuj _{}ac divide_by na podstawie funkcji / dokonaliśmy pewnych myślowych operacji wyższego rz_{}edu (jakżeby inaczej). Te operacje można zapisać w SML-u:

fun curry f a b = f (a, b)
fun C f x y = f y x

Definicj_{}e divide_by można teraz przedstawić tak:

val divide_by = C (curry (op /))

Tak na marginesie: dla dowolnego f : 'a * 'b -> 'c istnieje dokładnie jedna funkcja g : 'a -> 'b -> 'c taka, że dla każdego (x, y) : 'a * 'b f (x, y) = g x y. Tym g jest curry f. Sk _{}ad wynika na przykład, że każd _{}a operacj_{}e arytmetyczn _{}a można przerobić na funkcj_{}e wyższego rz_{}edu tylko na dwa sposoby.

Jeszcze jedno — przy pomocy lambda notacji funkcje wyższych rz_{}edów zapisuje si_{}e zagnieżdżaj _{}ac fn, np.:

fun curry f = fn a => fn b => f (a, b)
val C = fn f => fn x => fn y => f y x

Zadania

Zadanie 6.1 Zdefiniuj funkcje odwrotne do curry (b_{}edzie si_{}e nazywała uncurry) i C (nazw_{}e wymyśl sama (sam)). Napisz funkcj_{}e repeat, która dostawszy pare (f, n) daje funkcj_{}e równ _{}a złożeniu n funkcji f. Czyli:

repeat (f, n) = f^{n}

Zadanie 6.2 Dla dowolnych dwóch typów 'a i 'b istnieje typ 'a * 'b, ich produkt. W naturalny sposób zwi _{}azane s _{}a z tym typem pewne funkcje — projekcje:

    fun pi1 (x, y) = x
    fun pi2 (x, y) = y
i funkcja pair typu ('c -> 'a) * ('c -> 'b) -> ('c -> 'a * 'b),

która dostawszy funkcje f :'c -> 'a oraz g : 'c -> 'b daje funkcj_{}e

h : 'c -> 'a * 'b, o tej własności, że pi1 o h = f i pi2 o h = g.

(Taka funkcja h jest dla każdego (f, g) tylko jedna.)

Napisz funkcj_{}e pair.

Zadanie 6.3 Zdefiniuj typ ('a, 'b) direct_sum, który jest sum _{}a rozł _{}aczn _{}a tyów 'a i 'b. Ten typ b_{}edzie w pewnym sensie dualny do typu 'a * 'b. Zdefiniuj włożenia (injekcje):

    inleft  : 'a -> ('a, 'b) direct_sum
    inright : 'b -> ('a, 'b) direct_sum

i funkcj_{}e cases analogiczn _{}a (tak naprawd_{}e dualn _{}a) do funkcji pair dla produktu.

Wskazówka 1: Funkcja cases jest typu

('a -> 'c) * ('b -> 'c) -> ('a, 'b) direct_sum -> 'c.

Wskazówka 2: Funkcja cases dostawszy funkcje f : 'a -> 'c oraz

 g : 'b -> 'c daje funkcj_{}e h : ('a, 'b) direct_sum -> 'c , o tej

własności, że h o inleft = f i h o inright = g . (Taka funkcja h jest dla każdego (f, g) tylko jedna.)

Zadanie 6.4 Napisz funkcj_{}e

    exists : ('a -> bool) -> 'a list -> bool

która bierze predykat p : ('a -> bool) i daje funkcj_{}e, która bierze list_{}e l i oddaje true gdy któryś z elementów listy spełnia predykat p, false w przeciwnym przypadku. Napisz funkcj_{}e

    non : ('a -> bool) -> ('a -> bool)

która neguje predykat. Napisz funcj_{}e forall, która tym si_{}e różni od exists, że w odpowiednim miejscu nie któryś, ale wszystkie elementy listy musz _{}a spełniać predykat. Nim zaczniesz pisać forall podobnie jak exists, pomyśl czy nie możnaby go napisać śmieszniej (nie, nie chodzi mi o to żeby użyc foldr).

Spoiler: W definicji forall korzystaj wyłacznie z exists, non, i o.

Zadanie 6.5 Zapisz insertionsort lub inny algorytm sortowania (moźe mergesort, jeśli jeszcze go nie napisałeś lub nie napisałaś) w takiej postaci, aby jako pierwszy argument brał funkcj_{}e le : 't * 't -> bool wyznaczj _{}ac _{}a pewien porz _{}adek i sortował list_{}e l : 't list według tego porz _{}adku. Na-

pisz le_int i le_string. Wypróbuj insertionsort le_int. Napisz też

jakiś

    le_int_to_int : (int -> int) * (int -> int) -> bool
Wypróbuj insertionsort le_int_to_int.

Operacje na tekstach

Operacje na tekstach w SML to w rzeczywistości operacje na listach znaków. Istnieje wbudowana funkcja explode, która dostaj _{}ac napis, daje w wyniku list_{}e znaków, z których si_{}e on składa. Np. explode "baba" daje

                      [#"b",#"a",#"b",#"a"]

lub

                        ["b","a","b","a"]

w zależnosci od implementacji.

Zadania

Zadanie 7.1 Używaj _{}ac funkcji explode zdefiniuj funkcj_{}e size, ktora oblicza długość napisu.

Zadanie 7.2 implode to funkcja odwrotna do explode. Napisz funkcj_{}e ł _{}acz _{}ac _{}a dwa napisy.

Zadanie 7.3 Napisz funkcj_{}e linesplit : string -> string list, przerabiaj _{}ac _{}a napis na list_{}e wierszy, z których si_{}e on składa.

Zadanie 7.4 Napisz funkcj_{}e wordsplit : string -> string list, przerabiaj _{}ac _{}a napis na list_{}e słów, z których si_{}e on składa.

Zadanie 7.5 Napisz funkcj_{}e

           generic_split : string -> string -> string list,

przerabiaj _{}ac _{}a napis na list_{}e pól, z których si_{}e on składa, przyjmuj _{}ac drugi argument funkcji za zbiór separatorów pól.

Zadanie 7.6 Napisz funkcj_{}e sortuj _{}ac _{}a leksykograficznie list_{}e słów (można, a nawet należy skorzystać z napisanej wcześniej funkcji sortuj _{}acej)

Zadanie 7.7 Napisz funkcj_{}e generuj _{}ac _{}a dla danego napisu liste n najcz_{}eściej w nim wyst_{}epuj _{}acych słów, wraz z liczb _{}a wyst _{}apień każdego z nich.

Zadanie 7.8 Napisz funkcj_{}e

             strchr : string * char -> int list

tak _{}a, że strchr(s,c) daje list_{}e pozycji, na których znak c wyst_{}epuje w napisie s.

Zadanie 7.9 Napisz funkcj_{}e

            strstr : string * string -> int list

tak _{}a, że strstr(s,p) daje list_{}e pozycji, na których zaczynaj _{}a si_{}e wyst _{}apienia napisu p w napisie s. Uwaga:

            strstr("ababababa", "babab") = [2,4].

Rozdział 8 Leniwość

21

Moduły: struktury i sygnatury

Każdy duży a dobry program w naturalny sposób dzieli si_{}e na szereg odr_{}ebnych, w sporym stopniu niezależnych od siebie podprogramów. (Cz_{}esto podział ten nast_{}epuje już w fazach projektowania i specyfikowania.) Każdy taki podprogram składa si_{}e z pewnej liczby typów, wartości, komentarzy, intuicji, itp. i wszystkie jego składniki s _{}a mocno ze sob _{}a logicznie powi _{}azane. Jeśli zamanifestujemy istnienie takiego podprogramu deklaruj _{}ac odpowiedni SML-owy moduł, to zarówno dla nas, jak i dla kompilatora stanie si_{}e lepiej widoczne, co dokładnie wchodzi w skład podprogramu, jakie s _{}a zależnosci mi_{}edzy jego komponentami, itd. Jeśli dodatkowo przyjrzymy si_{}e krytycznie powstałemu (lub projektowanemu) modułowi i ocenimy co w nim jest istotne z punktu widzenia reszty naszego programu, a co jest jedynie szczegółem implementacyjnym, to b_{}edziemy mogli opatrzyć go wzgl_{}ednie krótk _{}a, a mimo to dobr _{}a, sygnatur _{}a.

Przykład, który wiele wyjaśnia:

signature TOTAL_PREORDER =
sig
    type elem
    val leq : elem * elem -> bool
    (* and leq should be a total preorder *)
end;
signature PRIORITY_QUEUE =
sig
    structure Item : TOTAL_PREORDER
    type queue
    val empty : queue
    val insert : Item.elem * queue -> queue
    val join : queue * queue -> queue

datatype min = MIN of Item.elem * queue | EMPTY
val get_min : queue -> min
(* By seq(q) we denote the sequence of Item.elem elements
   produced by iterating get_min on queue q.
   By num(t, q) we denote the number of occurrences of t in seq(q).
   For all q, p - queues constructed using the above operations,
   and for all t, u - elements of type Item.elem:
   1. seq(q) should be finite and non-decreasing,
   2. num(t, empty) should be 0,
   3. num(t, insert(u, q)) should be num(t, q), if u <> t,
      or num(t, q) + 1, if u = t,
   4. num(t, join(q, p)) should be num(t, q) + num(t, p). *)
end;
signature INTEGER_LEQ =
sig
include TOTAL_PREORDER
sharing type elem = int
(* and leq should be the natural less-equal on int *)
end;
structure IntegerLeq : INTEGER_LEQ =
struct
type elem = int
fun leq (k, l) = ((k : int) <= l)
end;
signature INT_PRIORITY_QUEUE =
sig
include PRIORITY_QUEUE
sharing type Item.elem = int
(* and Item.leq should be the natural less-equal on int *)
end;
structure IntPQasList : INT_PRIORITY_QUEUE =
struct
structure Item = IntegerLeq (* type sharing and requirement *)
                            (* about Item.leq now satisfied *)
type queue = Item.elem list (* queues will be unordered lists *)

    val empty = nil
    val insert = op ::
    val join = op @
    datatype min = MIN of Item.elem * queue | EMPTY
    fun get_min nil = EMPTY
      | get_min (k::tail) =
        case get_min tail
          of EMPTY => MIN(k, nil)
           | MIN(n, rest) => if Item.leq (k, n) then MIN(k, n::rest)
                             else MIN(n, k::rest)
end;

Nazwijmy naszkicowany powyżej program IntP QasList. Jest on poprawny tzn. dobrze implementuje kolejk_{}e priorytetow _{}a liczb całkowitych. W szczególności IntPQasList pasuje do INT_PRIORITY_QUEUE, czyli zawiera wszystkie wymagane typy, wartości, itp., jak również spełnia wszystkie wymagania opisane w komentarzach (sprawdź).

Definicja (przez przykład) dobroci: Mówimy, ze sygnatura INTEGER_LEQ jest dobra dla struktury IntegerLeq w programie IntP QasList, gdyż:

  1. IntegerLeq pasuje do INTEGER_LEQ

2. jesli napiszemy dowoln _{}a struktur_{}e A pasuj _{}ac _{}a do INTEGER_LEQ, to program IntP QasList z IntegerLeq podmienionym na A pozostanie poprawny

Dobra sygnatura pozwala nam i kompilatorowi rozumować o module, jako całości, wył _{}acznie na podstawie jego sygnatury, bez zagl _{}adania do kodu. Wspomaga to abstrakcyjne myślenie o programie, bardzo ułatwia piel_{}egnacj_{}e i modyfikacj_{}e, pozwala na rozł _{}aczna kompilacj_{}e modułów, etc.

Gdyby w programie IntP QasList zamiast INTEGER_LEQ zdefiniować nast_{}epuj _{}ac _{}a sygnatur_{}e:

signature INTEGER_LEQ' =
sig
    include TOTAL_PREORDER
    sharing type elem = int
    (* and leq should additionally be antisymmetric *)
end;

to nie byłaby ona dobr _{}a sygnatur _{}a dla IntegerLeq. Oto dowód:

structure A : INTEGER_LEQ' =
struct
    type elem = int
    fun leq (k, l) = ((k : int) >= l) (* comment satisfied *)
end;

Widać, że A pasuje do INTEGER_LEQ'. Ale program IntP QasList z INTEGER_LEQ' zamiast INTEGER_LEQ, gdy podmienimy w nim IntegerLeq na A, przestaje być poprawny, gdyż porz _{}adek na Item.elem w module IntPQasList jest odwrotny niż wymagany w jego specyfikacji.

Pisz zawsze dobre sygnatury!

Zadania

Zadanie 9.1 Napisz moduły COMPLEX_LEQ (liczby zespolone uporz _{}adkowane

według ich modułów), COMPLEX_PRIORITY_QUEUE, ComplexLeq, ComplexPQasList.

Sprawdź poprawność i przetestuj.

Zadanie 9.2 Napisz program IntP QasOrderedList. Upewnij si_{}e, że moduł

IntPQasOrderedList pasuje do sygnatury INT_PRIORITY_QUEUE. Pomyśl

o złożoności czasowej IntP QasList oraz IntP QasOrderedList.

Zadanie 9.3 Napisz program sortuj _{}acy liczby całkowite przy użyciu kolejki priorytetowej. Wykorzystaj IntP QasList jako jego podprogram. Czy

INT_PRIORITY_QUEUE jest dobr _{}a sygnatur _{}a dla IntPQasList w tym pro-

gramie?

Zadanie 9.4 Zmodyfikuj program z poprzedniego zadania tak, aby korzystał z IntP QasOrderedList. Jaki algorytm sortowania wynika z użycia insert a jaki z użycia join przy tworzeniu kolejki?

Moduły: funktory

Przy pomocy funktora można wyraźnie opisać, jakie moduły s _{}a potrzebne by zaimplementować dany moduł. Gdy program jest napisany w całości przy pomocy funktorów, w naturalny sposób przybiera on hierarchiczn _{}a postać. Jest jeden moduł, który rz _{}adzi i którego sygnatura jest opisem naszych oczekiwań co do programu, s _{}a moduły spełniaj _{}ace specyfikacje argumentów tego rz _{}adz _{}acego funktora, s _{}a moduły spełniaj _{}ace specyfikacje argumentów tych modułów, itd. Dodatkowo, jeśli funktor ma dobr _{}a sygnatur_{}e i nie wymienia si_{}e w nim nazw żadnych zewn_{}etrznych modułów (element dobrego stylu), to można o nim rozumować lub zmieniać jego implementacj_{}e, abstrahuj _{}ac od własności czy istnienia jakichkolwiek innych modułów i nie psuje to poprawności programu.

Przykład funktora:

... (* <- TREE and Tree are defined here *)
functor PQasHeap
    ( structure TotalPreorder : TOTAL_PREORDER
      structure Tree : TREE ) :
sig
    include PRIORITY_QUEUE
    sharing Item = TotalPreorder
    (* queues should be constructed as trees  *)
    (* with value of every node less or equal *)
    (* to values of all the descendant nodes  *)
end =
struct
    structure Item = TotalPreorder (* sharing satisfied *)
    type queue = Item.elem Tree.tree
    ... (* still some work ;-) *)
end;

structure IntPQasHeap = PQasHeap (structure TotalPreorder = IntegerLeq
                             structure Tree = Tree);

Zadania

Zadanie 10.1 Napisz program P QasHeap według szkicu podanego powyżej. Sprawdź, czy sygnatury s _{}a dobre. Przetestuj w przypadku liczb całkowitych i zespolonych.

Zadanie 10.2 Zmień TREE i Tree tak, by Tree był funktorem, o argumencie Item, a tree nie było polimorficznym typem danych, tylko typem zależnym od argumentu funktora:

datatype tree = EMPTY | NODE of tree * Item.item * tree.

Użyj tego TREE i Tree do zrobienia innej wersji programu P QasHeap. To jest niezbyt ładne bez funktorów wyższego rz_{}edu, ale wykonalne.

Zadanie 10.3 Zmodyfikuj P QasHeap tak, by drzewa, jakimi s _{}a kolejki, były zawsze utrzymywane w postaci wyważonej. Postaraj si_{}e w jak najwi_{}ekszym fragmencie programu abstrahować od sposobu w jaki zapewniane jest wyważenie. Zamanifestuj t_{}e abstrakcj_{}e odpowiednio deklaruj _{}ac moduły.

Zadanie 10.4 Napisz funktor implementuj _{}acy sortowanie przy pomocy kolejek priorytetowych. Pomyśl o złożoności czasowej sortowania przy użyciu P QasHeap.

To już koniec :-[

Dodatek A

Jak zaliczyć laboratorium

Aby zaliczyć laboratorium SML należy napisać program. Powinien si_{}e on składać z kilku do kilkunastu małych modułów; dobrze wyspecyfikowanych, poł _{}aczonych w sensown _{}a całość jasnymi, wyraźnie opisanymi zależnościami.

Temat jest dowolny. Służymy rad _{}a i pomoc _{}a przy jego wyborze. Oto przykładowe (troch_{}e nudne i wykorzystywane już zbyt wiele razy) zadanie zaliczeniowe:

Napisać Kalkulator, czyli program, który wśród swoich modułów ma moduł pasuj _{}acy do sygnatury CALCULATOR, zdefiniowanej nast_{}epuj _{}aco:

signature CALCULATOR =
sig
    val eval : string -> string
    (* if s represents an arithmetic expression    *)
    (* (which means that s is a string of digits,  *)
    (* ~ (negation), +, -, * and parenthesis,      *)
    (* satisfying some well known properties),     *)
    (* then (eval s) should be equal to the string *)
    (* representing the value of s, or the string  *)
    (* "division by zero" if appropriate,          *)
    (* if s does not represent a valid arithmetic  *)
    (* expression, (eval s) should be equal to the *)
    (* string "syntax error"                       *)
end;

Wszelkie drobne niejasności tej specyfikacji należy interpretować na swoj _{}a korzyść. W razie problemów zwrócić si_{}e o pomoc.

Wydaje si_{}e, że wśród modułów składaj _{}acych si_{}e na Kalkulator powinny być

moduły Lexer, Parser, Evaluator i PrettyPrinter. Byłoby ładnie i chyba

wygodnie, gdyby Parser posługiwał si_{}e drzewem składni reprezentuj _{}acym gramatyk_{}e LL(1) wyrażeń, zaś Evaluator drzewem reprezentuj _{}acym prostsz _{}a gramatyk_{}e:

datatype expression =
  NUM of int
| NEGATION of expression
| TIMES of expression * expression
| PLUS of expression * expression
| ...

To zadanie nie powninno być zbyt trudne. To co można tu zrobić lepiej lub gorzej to podział programu na moduły, zdefiniowanie zależności mi_{}edzy modułami przy pomocy funktorów, opisanie własności modułów sygnaturami.

Powodzenia!

Dodatek B

Rozwi _{}azania niektórych zadań

Wszystkie te rzeczy przeszły przez kompilator (w wypadku programów w SML to bardzo dobry omen), ale nie były zbyt intensywnie testowane. Dzi_{}eki za wskazywanie bł_{}edów!

(* Exercise 2.1 *)
exception Empty
fun tl [] = raise Empty
  | tl (head::tail) = tail
(* Exercise 2.2 *)
fun sum l = if null l then 0 else hd l + sum (tl l)
(* or *)
fun sum [] = 0
  | sum (i::rest) = i + sum rest
(* Exercise 2.3 *)
fun length l = if null l then 0 else 1 + length (tl l)
(* or *)
fun length [] = 0
  | length (head::tail) = 1 + length tail
(* Exercise 2.4 *)
fun last l = if null l then hd l else last (tl l)

(* or *)
fun last [] = raise Empty
  | last [elem] = elem
  | last (head::tail) = last tail
(* Exercise 2.5 *)
fun append ([], l) = l
  | append (head::tail, l) = head :: (append (tail, l))
(* Exercise 2.6 *)
fun take (l, 0) = nil
  | take (head::tail, n) = head :: take (tail, n-1)
  | take (nil, n) = nil
fun drop (l, 0) = l
  | drop (head::tail, n) = drop (tail, n-1)
  | drop (nil, n) = nil
(* Check, that the required equality          *)
(* holds even if n < 0. This is an ugly hack, *)
(* I know, but I hate exceptions even more:P. *)
(* Exercise 2.7 *)
fun nth (l, n) = hd (drop (l, n-1))
(* And this version is slower. Why? *)
fun nth2 (l, n) = last (take (l, n))
(* Exercise 2.8 *)
fun flatten [] = []
  | flatten (l::rest) = append (l, flatten rest)
(* Exercise 2.9 *)
(* @ is the built in, infix version of append *)
fun quicksort [] = [] : int list
  | quicksort [x] = [x]
  | quicksort (a::rest) =
    let
        fun split (b, []) = ([], [])
          | split (b, x::l) = let
                                  val (left, right) = split (b, l)
                              in

                                  if x < b then (x::left, right)
                                  else (left,x::right)
                              end
    in
        let
            val (left, right) = split (a, rest)
        in
            quicksort left @ (a::quicksort right)
        end
    end
(* Exercise 3.1 *)
fun length l = let
                   fun len_acc (len, []) = len
                     | len_acc (len, head::tail) = len_acc (len + 1, tail)
               in
                   len_acc (0, l)
               end
(* Exercise 3.2 *)
fun decimal l =
  let fun diggy (acc, []) = acc
        | diggy (acc, digit::rest) = diggy (10*acc + digit, rest)
  in
      diggy(0, l)
  end
(* Definitions of decimal without an accumulator are absolutely hopeless *)
(* Exercise 3.3 *)
(* reverse2 is O(n^2) *)
fun reverse2 [] = []
  | reverse2 (head::tail) = (reverse2 tail) @ [head]
(* Thanks to the use of accumulator reverse is O(n) *)
(* and by chance there is tail recursion here *)
fun reverse l = let
                    fun rev_acc (rev, []) = rev
                      | rev_acc (rev, head::tail) = rev_acc (head::rev, tail)
                in
                    rev_acc ([], l)
                end

(* Exercise 3.4 *)
(* This works. Notice reverse.               *)
(* A similar thing could be done for append. *)
(* Not worth the effort, is it?              *)
exception Empty
fun take (l, n) =
    let
        fun take_acc (acc, (l, 0)) = reverse acc
          | take_acc (acc, (hd::tl, n)) = take_acc (hd :: acc, (tl, n-1))
          | take_acc (acc, (nil, n)) = raise Empty
    in
        take_acc ([], (l, n))
    end
(* Exercise 3.5 *)
fun interval (from, to) =
    let
        fun inter_acc (l, (n, m)) = if n > m then l
                                    else inter_acc (m::l, (n, m-1))
    in
        inter_acc ([], (from, to))
    end
(* Exercise 3.6 *)
val minus_infinity = ~10000000000000000000000000000000.0
fun real_max [] = minus_infinity
  | real_max (head::tail) =
    let fun maxx (r, []) = r
          | maxx (r, x::tl) = if r > x then maxx (r, tl)
                              else maxx (x, tl)
    in
        maxx (head, tail)
    end
fun real_max [] = minus_infinity
  | real_max (x::tail) = let
                        val y = real_max tail
                    in
                        if y > x then y
                        else x
                    end

(* Exercise 5.1 *)
fun foldr (f, x) [] = x
  | foldr (f, x) (a::rest) = f(a, foldr (f, x) rest)
fun append (l1, l2) = foldr (op ::, l2) l1
(* Exercise 5.2 *)
val length = foldr (fn (elem, rest_length) => 1 + rest_length, 0)
(* Exercise 5.3 *)
fun good_max n = foldr (max, n)
(* Exercise 5.4 *)
fun map f nil = nil
  | map f (head::tail) = (f head)::(map f tail)
fun map f = foldr (fn (a, result) => (f a):: result, nil)
(* Exercise 5.5 *)
val first_cut = map hd
fun first_cut nil = nil
  | first_cut (head::tail) = (hd head)::(first_cut tail)
(* Exercise 5.6 *)
fun filter p nil = nil
  | filter p (a::rest) = if p a then a::(filter p rest)
                         else (filter p rest)
fun filter p = foldr (fn (a, filtered_tail) =>
                      if p a then a::filtered_tail
                      else filtered_tail, nil)
(* No, this didn't turn out more readable (at least for me). *)
(* Exercise 5.7 *)
fun divisible_by k l = l mod k = 0
fun divis_list n = filter (divisible_by n)
(* Yeees. *)
(* Exercise 5.8 *)
fun foldl (f, x) nil = x
  | foldl (f, x) (head::tail) = foldl (f, (f (x, head))) tail

(* Exercise 5.9 *)
fun reversed_cons (tail, head) = head :: tail
fun append (l1, l2) = foldl (reversed_cons, l2) (rev l1)
(* Exercise 6.1 *)
fun uncurry f = fn (a, b) => f a b
fun id x = x
fun repeat (f, 0) = id
  | repeat (f, n) = f o (repeat (f, n - 1))
(* Exercise 6.2 *)
fun pair (f, g) x = (f x, g x)
(* Exercise 6.3 *)
datatype ('a, 'b) direct_sum = INL of 'a | INR of 'b
val inleft = INL
val inright = INR
fun cases (f, g) (INL(x)) = f x
  | cases (f, g) (INR(y)) = g y
(* Exercise 6.4 *)
fun exists p [] = false
  | exists p (a::rest) = if p a then true
                         else exists p rest
fun non p = not o p
val forall = non o exists o non

Dodatek C

Jak pracować z kompilatorem SML-a

• Interaktywnie:

1. uruchomić SML (mosml, new-sml, sml-0.93, sml)

2. po zach_{}ecie, któr _{}a na ogół jest myślnik, napisać program

3. zakończyć pisanie średnikiem i nacisn _{}ać RET

• Wsadowo:

1. napisać program jakimś edytorem

2. zapisać go w pliku smth.sml

3. uruchomić SML i napisac use "smth.sml";

• Przy pomocy EMACS-a i sml-mode:

1. uruchomić EMACS-a

2. C-x C-f smth.sml RET (ważne, żeby końcówk _{}a nazwy było .sml)

3. napisać bł_{}edny program (Tab automagicznie formatuje)

4. C-c C-l i b_{}edzie wiadomo co dalej

5. Zrobić C-c ` (ten ostatni znaczek to back-quote, wyst_{}epuje na klawiaturze na ogół pod tyld _{}a), wtedy on ustawi kursor tam gdzie w pliku jest bł _{}ad

6. Korzystać z innych dobrodziejstw sml-mode, np. sml-mode-info, czyli podr_{}ecznika do sml-mode