// autor: Pawel Schmidt // Listy i sortowanie // Przypomnijmy definicje funkcji usuwajacej pierwsze wystapienie elementu z danej listy let rec removeElement (lst : int list) (e : int) : int list = match lst with | [] -> [] | h::t -> if h = e then t else h :: removeElement t e // Funkcja realizujaca sortowanie przez wybor. // Jest ona nam potrzebna tylko po to, by poczuc roznice pomiedzy rozwiazaniem kwadratowym a nlogn let rec selectionSort (lst:int list) : int list = if List.isEmpty lst then lst else let m = List.min lst let newList = removeElement lst m m :: selectionSort newList // Czesc druga: sortowanie szybkie // Przekazywanie funkcji jako argument innej funkcji // Na poprzednich zajeciach zobaczylismy, ze funkcje definiujemy niemalze // tak samo jak "zwykle" zmienne // Co wiecej, tak jak zwykle przekazujemy parametry do funkcji, // mozemy tez robic z funkcjami // Funkcja map wywolana z funkcja f oraz lista [ x1; x2; x3; ... ; xn] // zwraca liste [ f(x1); f(x2); f(x3); ...; f(xn) ] // Funkcja w bibliotece standardowej odpowiadajaca map to List.map let rec map (f: 'a -> 'b) (lst: 'a list) : 'b list = match lst with | [] -> [] | x :: xs -> let xsMapped = map f xs (f x) :: xsMapped // Na przyklad lista kwadratow liczb od 1 do n mozemy stworzyc nastepujaco: let square n = n * n let squaresList n = // na kazdy element listy [1..n] nakladamy funkcje square podnoszaco swoj argument do kwadratu map square [1..n] // Zadanie 3: // Zdefiniuj funkcje filter tak, by dla funkcji f i listy lst zwracala nowa liste // utworzona z elementow dla ktorych funkcja f zwraca wartosc true // Funkcja w bibliotece standardowej odpowiadajaca filter to List.filter let rec filter (f: int -> bool) (lst: int list) : int list = raise (System.NotImplementedException()) let filterTest1() = let isEven n = n % 2 = 0 filter isEven [1..10] = [2; 4; 6; 8; 10] let filterTest2() = let alwaysTrue n = true filter alwaysTrue [2;8;12] = [2;8;12] let filterTest3() = let alwaysFalse n = false filter alwaysFalse [2;8;12] = [] let filterTest4() = let neq7 n = n <> 7 filter neq7 [1..10] = removeElement [1..10] 7 // Zadanie 4: // Zdefiniuj funkcje append, ktorej wynikiem bedzie lista zawierajaca wszystkie elementy z obu argumentow // Funkcja w bibliotece standardowej odpowiadajaca append to List.append let rec append (left: int list) (right: int list) : int list = match left with | [] -> right // ... let appendTest1() = append [] [1;2;3] = [1;2;3] let appendTest2() = append [7] [1;2;3] = [7; 1;2;3] let appendTest3() = append [7;-12] [1;2;3] = [7; -12; 1;2;3] let appendTest4() = append [7; -12] [] = [7; -12] // Zadanie 5 // Zdefiniuj funkcje quickSort, implementujaca algorytm sortowania szybkiego // Algorytm sortowania szybkiego wyglada nastepujaco: // 1. Wez pierwszy element listy (nazwijmy go pivot) // 2. Stworz liste l1 zawierajaca elementy listy lst mniejsze od pivota // 3. Stworz liste l2 zawierajaca elementy listy lst wieksze od pivota // 4. Posortuj liste l1 (wywolaj siebie rekurencyjnie na l1) // 5. Posortuj liste l2 // 6. Polacz listy l1, l2 oraz pivot tak, by otrzymac posortowana liste // Wskazowka: wykorzystaj funkcje filter oraz append let rec quickSort (lst: int list) : int list = raise (System.NotImplementedException()) // Czesc trzecia: sortowanie przez scalanie // Zadanie 6 // Zdefiniuj funkcje merge, ktora jako argumenty przyjmie dwie posortowane listy left i right // (nie sprawdzamy tego warunku!) oraz zwroci posortowana lista zawierajaca wszystkie elementy // list left oraz right // Wskazowka: porownaj pierwsze elementy obu list let rec merge (left: int list) (right: int list) : int list = raise (System.NotImplementedException()) let mergeTest1() = merge [] [1;2;3] = [1;2;3] let mergeTest2() = merge [1;6] [2;7] = [1;2;6;7] let mergeTest3() = merge [5] [1;2;3] = [1;2;3;5] let mergeTest4() = merge [6] [1;2;9] = [1;2;6;9] // Zadanie 7 // Zdefiniuj funkcje mergeSort implementujaca algorytm sortowania przez scalanie // Algorytm sortowania przez scalanie dziala nastepujaco // 1. Oblicz n - dlugosc listy lst // 2. Podziel liste na dwie podlisty: left o dlugosci n / 2 i right zlozona z pozostalych elementow // takich ze append left right = lst // 3. Posortuj (wywolujac sie rekurencyjnie) listy left oraz right // 4. Scal je otrzymujac posortowana liste lst // Wskazowka: uzyj funkcji merge zdefiniowanej w poprzednim zadaniu oraz funkcji // List.length, List.take i List.skip z biblioteki standardowej let rec mergeSort (lst: int list) : int list = raise (System.NotImplementedException()) // Testowanie wydajnosci // wygeneruj liste zlozona z n losowych elementow let randomList n = let r = System.Random() [1..n] // wez liste [1..n] |> List.map (fun i -> r.Next(), i) // kazdemu jej elementowi przyporzadkuj losowa liczbe |> List.sort // posortuj (wzgledem losowych liczb) |> List.map snd // usun losowe liczby i zwroc liste let test sort n = let input = randomList n // stworz liste dlugosci n let stopWatch = System.Diagnostics.Stopwatch.StartNew() // zacznij mierzyc czas let sorted = sort input // posortuj liste stopWatch.Stop() // zatrzymaj pomiar czasu if sorted = [1..n] then printfn "%d elements sorted, total time: %f" n stopWatch.Elapsed.TotalSeconds else printfn "list was not sorted: should be [1..n], but the result was %A" sorted // Ponizsze wywolania powinny zakonczyc sie w przyzwoitym czasie // test selectionSort 10 // test selectionSort 10000 // test quickSort 40000 // test mergeSort 40000 // Czesc trzecia: przekazywanie stanu obliczen jako argument funkcji (obliczenia z akumulatorem) // Na poprzednich zajeciach dlugosc listy obliczalismy nastepujaco: let rec length lst = match lst with | [] -> 0 | head :: tail -> 1 + length tail // Funkcja ta jest malo wydajna (potrzebuje liniowo wiele pamieci wzgledem dlugosci listy). // Mozemy jednak napisac to nieco lepiej wykorzystujac funkcje pomocnicza (lenacc). // funkcja ta przyjmuje dodatkowy argument (akumulator), // ktory odpowiada pewnym obliczeniom na prefiksie listy, ktory juz wczytalismy // (w tym wypadku to jest liczba juz przeczytanych elementow) let rec lenacc acc lst = match lst with | [] -> acc // jesli lista jest pusta, zwroc wartosc akumulatora | head :: tail -> lenacc (acc + 1) tail // w przeciwnym wypadku policz dlugosc ogona, dodajac 1 do akumulatora // dlugosc listy obliczamy wywolujac funkcje z akumulatorem rownym 0 (dlugosc pustej listy) let length2 lst = lenacc 0 lst // Zadanie 8: // Zdefiniuj funkcje prod, ktora policzy iloczyn wszystkich elementow listy // Uzyj funkcji pomocniczej z akumulatorem tak, by mozliwe bylo obliczenie iloczynu elementow listy [1..1000000] // Zadanie 9: // Zdefiniuj funkcje rev, ktora odwroci liste bedaca jej argumentem. // Wykorzystaj funkcje pomocnicza z akumulatorem.