Funkcje vs Metody w Scali¶

Metoda to część klasy, opisana sygnaturą, zawierająca kod. Funkcja to kompletny obiekt.

def method(arg: Int) = arg + 1
method: (arg: Int)Int

val function = (arg: Int) => arg + 1
function: Int => Int = <function1>

Możemy używać metod jak funkcji i vice versa (konwersja wykoanana przez interpreter).

Składnia¶

Funkcje:

val f = (x: Int) => x + 1
val g = (x: Int, y: Int) => x + y
val h = () => x
val i = () = { System.out.println("Hello World!") }

Typy:

Int => Int
(Int, Int) => Int
() => ()

Funkcje wyższego rzędu i pierwszej klasy¶

Funkcja pierwszej klasy to funkcja która może być traktowana jak wartość: przypisywana do zmiennej, przekazywana przez argumenty.

Funkcja wyższego rzędu to funkcja która przyjmuje funkcję jako argument, lub zwraca funkcję.

val fahrToCels = (temp: Double) => (temp - 32) * 5/9    // function
def celsToFahr(temp: Double) = 32 + temp * 9/5          // method

fahrToCels(100)
celsToFahr(30)

val celsOfFahr = fahrToCels
val fahrOfCels = celsToFahr _                          // because: celsToFahr <==> celsToFahr();

celsOfFahr(100)
fahrOfCels(30)

def convert(f: Double => Double, temp: Double) = f(temp)

convert(fahrToCels, 100)
convert(celsToFahr, 30)

Zwracanie funkcji:

val f = (x:Int) => (y: Int) => x + y
val g = (x:Int) => { val z = x + 1; (y: Int) => z + y }

Kompozycja funkcji¶

val f = (x:Int) => x * x
val g = (x:Int) => x + 1

f(g(1))                 // (x + 1) * (x + 1) = 4
(f compose g)(1)        // (x + 1) * (x + 1) = 4

g(f(1))                 // (x * x) + 1 = 2
(f andThen g)(1)        // (x * x) + 1 = 2

Funkcje anonimowe¶

(x: Int) => x + 1

Funkcja fold¶

Standardowe rekurencyjne przejście po liście:

def recursiveSum(l: List[Int], acc: Int = 0): Int =
    l match {
        case Nil => acc
        case head::tail => recursiveSum(tail, acc + head)
    }
recursiveSum(List(1,1,1,1))

Szablon:

def recursiveOp[T](op: (T, T) => T, l: List[T], acc: T): T =
    l match {
        case Nil => acc
        case head::tail => recursiveOp(op, tail, op(acc, head))
    }
recursiveOp((acc:Int, elem:Int) => acc + elem, List(1,1,1,1), 0)

Funkcja fold:

def fold[A1 >: A](z: A1)(op: (A1, A1) => A1): A1

val l = List(1, 1, 1 ,1 ,1)
l.fold(0)((acc: Int, elem: Int) => acc + elem)

val ll = List(List(1, 1, 1), List(2, 2, 2))
ll.fold(List[Int]())((acc: List[Int], elem: List[Int]) => acc ::: elem)

Optymalizacja do wykonania równoległego. Ograniczenie wg typów:

val l = List(1, 1, 1 ,1 ,1)
l.fold(List[Int]())((acc: List[Int], elem: Int) => elem :: acc)
<console>:3: error: type mismatch;

Wykonanie sekwencyjne z wyróżnieniem kierunku wywoływania:

def foldLeft[B](z: B)(op: (B, A) => B): B
def foldRight[B](z: B)(f: (A, B) => B): B

val l = List(1, 2, 3 ,4 ,5)
l.foldLeft(0)((acc: Int, elem: Int) => {println(acc+"+"+elem); acc + elem})
l.foldRight(0)((elem: Int, acc: Int) => {println(acc+"+"+elem); acc + elem})

l.foldLeft(List[Int]())((acc: List[Int], elem: Int) => elem :: acc)
l.foldRight(List[Int]())((elem: Int, acc: List[Int]) => elem :: acc)

Redukcja bez wartości początkowej. (Ograniczenie typów.)

val l = List(1, 2, 3 ,4 ,5)
l.reduce((acc: Int, elem: Int) => acc + elem)
l.reduceLeft((acc: Int, elem: Int) => {acc + elem})
l.reduceRight((elem: Int, acc: Int) => {acc + elem})

Wyniki pośrednie:

val l = List(1, 2, 3 ,4 ,5)

l.scan(0)((acc: Int, elem: Int) => acc + elem)
l.scanLeft(0)((acc: Int, elem: Int) => {acc + elem})
l.scanRight(0)((elem: Int, acc: Int) => {acc + elem})

l.scanLeft(List[Int]())((acc: List[Int], elem: Int) => elem :: acc)
l.scanRight(List[Int]())((elem: Int, acc: List[Int]) => elem :: acc)

Mapowanie wartości:

val l = List(1, 2, 3 ,4 ,5)

l.map((x: Int) => x + 1)
l.map((x: Int) => x.toString())

Mapowanie na n wartości

val l = List(1, 2, 3, 4, 5)

l.flatMap((x: Int) => if (x==0) List(x) else List(x, -x))

Filtrowanie wartości:

val l = List(1, 2, 3, 4, 5)

l.filter((x:Int) => x % 2 == 0)
l.filterNot((x:Int) => x % 2 == 0)

Podział listy:

val l = List(1, 2, 3, 4, 5)

l.parition((x:Int) => x % 2 == 0)

Ankieta

Ćwiczenia¶

#. Problem: Zaimplementuj funkcję cenzury. Funkcja przyjmuje listę słów zabronionych i listę słów stanowiącą jakąś treść. Każde słowo w treści, które znajduje się na liście słów zabronionych jest zastąpione napisem [OCENZURWANO] w wynikowej liście słów.

1. Problem: Zaimplementuj funkcję łączącą dwie listy.
2. Problem: Przygotuj własną implementacji funkcji reduce, map, filter, scan, partition używając funkcji foldLeft.
3. Problem: Napisz program wyszukujący w podanym katalogu wszystkich plików które mają powtarzającą się treść. Porównanie pliku wykonaj w dwóch krokach: do wstepnego porównania przygotuj dla każdego pliku skrót (hash); drugi krok porównania to dokładne porównanie treści.
4. Problem: Przygotuj wielowątkową implementację funkcji sortującej w modelu MapReduce (np. Bucket sort).

Zadanie [Scala2]¶

Zaimplementuj w Scali program znajdujący najbardziej punktowane możliwe do ułożenia legalne słowo w Scrabble.

Dany jest alfabet znaków A. Dany jest wektor P(c) który określa wartość punktową każdego znaku c w alfabecie. Dany jest też wektor C(c) która dla każdego znaku w alfabecie określa jego liczność. Słowo to dowolna sekwencja znaków. Mając dane słowo w jego punktacja P(w) to suma P(c) dla wszystkich c zawartych w w. Dany jest słownik D zawierający legalne słowa.

Gracz posiada multizbiór R zawierający znaki z A. Znak c występuje w R nie więcej niż C(c) razy.

Napisz funkcję losującą R. Napisz funkcję znajdującą w R takie legalne słowo w którego P(w) jest największe spośród legalnych słów możliwych do utworzenia z R.

Standardowe punkty znaków (i liczności):

0 pt: blank (2)
1 pt: E (12), A (9), I (9), O (8), N (6), R (6), T (6), L (4), S (4), U (4)
2 pt: D (4), G (3)
3 pt: B (2), C (2), M (2), P (2)
4 pt: F (2), H (2), V (2), W (2), Y (2)
5 pt: K (1)
8 pt: J (1), X (1)
10 pt: Q (1), Z (1)

Słowniki: np. /usr/share/dict/

Luźne uwagi: |w| ≤ |R|, sugeruje tylko małe/wielkie litery, można wczytać słownik z pliku

Zadanie [Scala2] (deprecated)¶

Zaimplementuj w Scali system parowania uczestników turnieju wg systemu szwajcarskiego.

Turniej trwa r rund i bierze w nim udział p uczestników (p > r) przy czym każdy uczestnik g pochodzi z kraju N(g). W pierwszej rundzie turnieju uczestnicy są parowani losowo, przy czym uczestnicy z tego samego kraju nie są parowani ze sobą nawzajem. W każdej kolejnej rundzie parowanie następuje wg następujących zasad:

1. Dwaj uczestnicy nie spotykają się więcej niż raz.
2. Uczestnicy spotykają się w kolejnej rundzie z uczestnikami o podobnej sumie punktów. T.j. jeśli posortować uczesntików wg sumy uzyskanych dotychczas punktów uczestnicy o pozycjach 1 i 2, 3 i 4, 5 i 6, etc. spotykają się w następnej rundzie (z uwzględnieniem wyjątku z pt 1.)
3. W miarę możliwości uczestnicy nie spotykają się z innymi uczestnikami z tego samego kraju.

Punktowanie spotkań.

1. Zwycięstwo w spotkaniu = 3pt, remis 1pt, przegrana 0pt.
2. Jeśli licza uczestników jest nieparzysta, uczestnik który w danej rundzie nie ma przeciwnika dostaje punkty jak za zwycięsto (tzw. bye).

Symulowanie wyników spotkań wg schematu:

val random = new scala.util.Random
val winner = (g1: Any, g2: Any) => {
    random.nextInt(3) match {
        case 0 => g1
        case 1 => g2
        case 2 => None
    }
}

Materiały¶

• Jim McBeath. Scala Functions vs Methods.
• Joseph Moniz. Reduce vs Fold in Scala.
• Mathew Jason Malone. Scala Code Review: foldLeft and foldRight.