Podstawowe funkcje języka Standard ML

W tym artykule pokażę kilka podstawowych funkcjonalności języka Standard Meta Language (SML).

Każdy program kończymy średnikiem: ;

Operacje arytmetyczne:
Dodawanie:
Input: 5 + 2;
Output: 7

Odejmowanie:
Input: 5 - 2;
Output: 3

Mnożenie:
Input: 5 * 2;
Output: 10

Dzielenie:
Input: 5 div 2;
Output: 2

Modulo (reszta z dzielenia)
Input: 5 mod 2;
Output: 1

Listy i operacje na listach:

Możemy sprawdzić czy lista jest pusta:
null(x) --sprawdzenie czy lista x jest listą pustą

hd(x) - zwraca głowę listy x (pierwszy element z listy x)

Input: hd([1,2,3,4,5]);
Output: 1

tl(x) - zwraca ogon listy (wszystkie poza pierwszym elementy z listy x)
Input: tl([1,2,3,4,5]);
Output: [2,3,4,5]

Przyjmowanie list jako argumenty funkcji:
f([1,2,3,4,5]); - funkcja przyjmuje jedną listę zawierającą pięć elementów: 1, 2, 3, 4, 5
f([[1],[2],[3],[4],[5]]); - funkcja przyjmuje pięć jedno-elementowych list które mają wartości: 1, 2, 3, 4, 5 jednak każdy z tych elementów jest oddzielną listą.

Paradygmat funkcyjny - jak zacząć?

Pisanie programów funkcyjnych w językach czysto funkcyjnych nie jest dobrym pomysłem jeżeli dopiero zaczynasz z programowaniem.

Do zaczęcia nauki paradygmatu funkcyjnego potrzebujesz:
• Wiedzieć i rozumieć jak działa rekurencja.
• Warunkiem (bardzo) mocno zalecanym jest poznanie paradygmatu obiektowego oraz (zalecanym) strukturalnego.
• Umieć pisać funkcję oraz programy składające się z kilku funkcji aby umieć posługiwać się funkcjami.

Kilka artykułów o programowaniu funkcyjnym:
•https://4programmers.net/Inżynieria_oprogramowania/Wstęp_do_programowania_funkcyjnego#paradygmat-programowania-funkcyjnego
•http://wazniak.mimuw.edu.pl/index.php?title=Programowanie_funkcyjne/Wstęp
•https://pl.wikibooks.org/wiki/Programowanie/Programowanie_funkcyjne
•http://www.python.rk.edu.pl/w/p/funkcje-i-programowanie-funkcyjne/

Paradygmat funkcyjny - co to jest?

Paradygmat funkcyjny obok kilku inny (obiektowego, strukturalnego, aspektowego, w logice) to jeden z bardziej popularnych paradygmatów programowania. W porównaniu do programowania obiektowego i strukturalnego w paradygmacie funkcyjnym nie ma pojęcia czasu jeżeli chodzi o stan pamięci w programie.

W podejściu obiektowym i strukturalnym program operuje na zmiennych jako miejscach w pamięci i zmienia je w czasie. W paradygmacie funkcyjnym bardzo unika się podejścia tego typu a program jest wynikiem funkcji z przyjętymi argumentami.

Teoretycznie każdy problem da się rozwiązać w paradygmacie funkcyjnym.

Jeżeli każdy program można zapisać funkcyjnie to dlaczego znacząca większość programów jest pisana obiektowo?
     Główny powód to fakt że część programów dużo łatwiej zapisać obiektowo a część dużo łatwiej funkcyjnie. Jednak tych które łatwiej zapisać obiektowo jest znacząco więcej niż tych które można zapisać funkcyjnie.

Jakie są główne trudności pisania programów funkcyjnych?
     Wielokrotnie zagnieżdżona rekurencja można powodować łatwe wejście w samo-zapętlenie się programu, dodatkowo funkcja będąca dowołaniem do funkcja która jest funkcją będącą efektem wywołania kilku kolejnych funkcji sprawia że kod w ten sposób zapisany jest mało czytelny i przy większych zespołach trudniej przekazać informacje o sposobie działania kodu. Kod pisany funkcyjnie jest często dużo trudniejszy w zrozumieniu niż kod napisany obiektowo przez co przy większych projektach wydłuża się czas na zrozumienie istniejącego kodu.

Więcej o paradygmacie funkcyjnym: https://pl.wikipedia.org/wiki/Programowanie_funkcyjne

Standard Metal Language - jak zacząć?

Do pisania programów w Standard Meta Langauge (SML) potrzebujesz:
• komputera z systemem Windows / Unix / MacOS
• edytora tekstu
• kompilatora języka
• przeglądarki internetowej

Kompilator jest oprogramowaniem darmowym na licencji open-source.

Wersja z której osobiście korzystałem to Standard ML of New Jersey.
Strona domowa języka: https://www.smlnj.org
Strona z gotowymi paczkami: https://www.smlnj.org/dist/working/110.82/index.html

Wystarczy pobrać plik .msi oraz go zainstalować.
Wersja z której korzystałem: http://smlnj.cs.uchicago.edu/dist/working/110.82/smlnj-110.82.msi

Do edytowania programów używałem NotePad++ a pliki zapisywałem z rozszerzeniem .sml
https://notepad-plus-plus.org

Przydatne linki:
• Instalacja na windows: https://www.smlnj.org/dist/working/110.82/WININSTALL
• Instalacja na innych systemach: https://www.smlnj.org/dist/working/110.82/WININSTALL
• Lista książek do języka Standard ML: https://www.smlnj.org/doc/literature.html#books
• Lista kilku tutoriali: https://www.smlnj.org/doc/literature.html#tutorials
• Najczęściej zadawane pytania: https://www.smlnj.org/doc/FAQ/index.html
• Dokumentacja języka Standard ML: https://www.smlnj.org/doc/index.html

Po instalacji i uruchomieniu otrzymujemy konsolę do której możemy wklejać nasze programy:

Sortowanie - Standard ML

Treść zadania:

Napisz dwie funkcje:
Pierwsza przyjmie za argument listę i posortuje jej elementy od najmniejszego do największego.
Druga przyjmie za argument listę i posortuje jej elementy od największego do najmniejszego.

Przykład:
sorting_low_first([10,3,7,2,9,4,5,1,8,6]) = [1,2,3,4,5,6,7,8,9,10]
sorting_hight_first([10,3,7,2,9,4,5,1,8,6]) = [10,9,8,7,6,5,4,3,2,1]

Kod źródłowy:

fun insert_low_first(a,x) = if null(x) then a::[] else if a<hd(x) then a::x else hd(x)::insert_low_first(a,tl(x))
fun sorting_low_first(x:int list) = if null(x) then [] else insert_low_first(hd(x),sorting_low_first(tl(x)));

fun insert_hight_first(a,x) = if null(x) then a::[] else if a>hd(x) then a::x else hd(x)::insert_hight_first(a,tl(x))
fun sorting_hight_first(x:int list) = if null(x) then [] else insert_hight_first(hd(x),sorting_hight_first(tl(x)));

Dane testowe:

sorting_low_first([10,3,7,2,9,4,5,1,8,6]);
sorting_hight_first([10,3,7,2,9,4,5,1,8,6]);

Suma liczb z listy - Standard ML

Treść zadania:

Napisz funkcję która przyjmie jako argument listę i wypiszę sumę jej elementów.

Przykład:
f([1,2,3,4,5]) = 15
f([5,5,5,5,5]) = 25
f([1,1,1,1,1]) = 5
f([2,2,2,2,2]) = 10
f([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]) = 120

Kod źródłowy:

fun f(x) = if null(x) then 0 else hd(x)+f(tl(x));

Dane testowe:

f([1,2,3,4,5]);
f([5,5,5,5,5]);
f([1,1,1,1,1]);
f([2,2,2,2,2]);
f([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]);

Parzyste nieparzyste - Standard ML

Treść zadania:

Zadeklarować funkcję f: int list → int list określoną następująco:

f(x) = lista otrzymana z listy x poprzez następujące przestawienie:
najpierw liczby parzyste występujące w x,
potrem liczby nieparzyste występujące w x

Na przykład:
f([4,7,2,1,2,3,7,5,2]) = [4,2,2,2,7,1,3,7,5]

Kod źródłowy:

fun append(x, y) = if null(x) then y else hd(x) :: append(tl(x), y)
fun even(x) = if null(x) then x else if hd(x) mod 2 = 0 then append([hd(x)],even(tl(x))) else even(tl(x))
fun odd(x) = if null(x) then x else if hd(x) mod 2 = 1 then append([hd(x)],odd(tl(x))) else odd(tl(x))
fun f(x) = append(even(x),odd(x));

Dane testowe:

f([4,7,2,1,2,3,7,5,2]);

Suma liczb podzielnych przez trzy - Standard ML

Treść zadania:

Zadeklarować funkcję f:int → int określoną następująco:
f(n) = suma liczb podzielnych przez 3 i mniejszych równych od n

Na przykład:
f(1) = 0
f(2) = 0
f(3) = 3
f(4) = 3
f(5) = 3
f(6) = 9 /* 3+6 */
f(7) = 9 /* 3+6 */
f(8) = 9 /* 3+6 */
f(9) = 18 /* 3+6+9 */

Kod źródłowy:

fun f(x:int) = if x=0 then 0 else if x mod 3 = 0 then x+f(x-1) else f(x-1);

Dane testowe:

f(1);
f(2);
f(3);
f(4);
f(5);
f(6);
f(7);
f(8);
f(9);

Funkcja na liście - Standard ML

Treść zadania:

Zadeklarować funkcję nest: (int → int) * int list → int określoną następująco:

nest(f, []) = 0
nest(f,[a]) = f(a,0)
nest(f,[a₁,a₂, ... ,a_n]) = f(a₁,f(a₂(...(a_n,0)...)

Przykład:
nest(f,[])=0
nest(f,[a])=f(a,0)
nest(f,[a,b])=f(a,f(b,0)
nest(f,[a,b,c])=f(a,f(b,(f(c,0)))

Kod źródłowy:

fun nest(f:int*int -> int ,x) = if null(x) then 0 else f(hd(x),nest(f,tl(x)));

Dla potrzeb testów deklaruję funkcję f która przyjmuje dwa argumenty i zwraca ich sumę

fun f(x,y) = x+y;

Przypadki testowe:

nest(f,[]);
nest(f,[1]);
nest(f,[1,2]);
nest(f,[1,2,3]);
nest(f,[1,2,3,4]);
nest(f,[1,2,3,4,5]);

Przeplot dwóch list - Standard ML

Treść zadania:

Napisać deklarację funkcji g:int list * int list → int list, g(x, y) = przeplot list x, y liczb całkowitych

Na przykład:
g([1,4,2,5],[1,3,5,7,9,11]) = [1,1,4,3,2,5,5,7,9,11]
g([1,2,3],[4,5,6]) = [1,4,2,5,3,6]
g([1,2,3,4,5],[6,7,8]) = [1,6,2,7,3,8,4,5]
g([],[1,2,3]) = [1,2,3]
g([1,2,3],[]) = [1,2,3]

Kod źródłowy:

fun append(x, y) = if null(x) then y else hd(x) :: append(tl(x), y)
 fun g(x, y) = if null(x) then y else if null(y) then x else append(append([hd(x)],[hd(y)]),g(tl(x),tl(y)));

Przypadki testowe:

g([1,4,2,5],[1,3,4,5,7,9,11]);
g([1,2,3],[4,5,6]);
g([1,2,3,4,5],[6,7,8]);
g([],[1,2,3]);
g([1,2,3],[]);

Funkcja listy - Standard ML

Treść zadania:
Napisać deklarację funkcji f : int list → int list określonej następująco:

f(x) = lista otrzymana z listy x przez podzielenie wszystkich liczb parzystych w x przez 2 i powiększenie wszystkich liczb nieparzystych na liście x o 2.

Przykład:
f([1,2,3,4,5,6]) = [3,1,5,2,7,3]

Kod źródłowy:

fun append(x, y) = if null(x) then y else hd(x) :: append(tl(x), y)
 fun pn(x:int) = if x mod 2 = 0 then x div 2 else x+2
  fun f(x) =  if null(x) then x else append([pn(hd(x))],f(tl(x)));

Przypadek testowy:

f([1, 2, 3, 4, 5, 6]);

Prosta funkcja - Standard ML

Napisz program który zrobi prostą funkcję w SML

f(1) = 2 = 2¹
f(2) = 4 = 2²
f(3) = 16 = 2⁴
f(4) = 256 = 2⁸
f(5) = 65536 = 2¹⁶

Kod źródłowy:

fun f(x:int) = if x=1 then 2 else f(x-1)*f(x-1);

Wywołania funkcji:

f(1);
f(2);
f(3);
f(4);
f(5);

Odwracanie listy - Standard ML

Funkcja przyjmuje za argument listę i odwraca ją (zmienia kolejność elementów)

Kod programu:

fun append(x, y) = if null(x) then y else hd(x) :: append(tl(x), y)
 fun reverse(x) = if null(x) then x else append(reverse(tl(x)), hd(x) :: [ ]);

Wywołanie funkcji dla listy: 1, 2, 3, 4, 5

reverse ([[1],[2],[3],[4],[5]]);

Wynikiem jest:

val it = [[5],[4],[3],[2],[1]] : int list list

Funkcja McCarthy’ego - Standard ML

Implementacja funkcji McCarthy'ego w języku Standard ML

fun  f(x) = if x>100 then x-10 else f(f(x+11));

Dla danych wejściowych:

f(100+11);

Wynikiem będzie:

val it = 101 : int