Scala/Coursera/Функції

Інструменти

Потрібно встановити IDE (Eclipse), та Scala Build Tool (sbt).

Парадигми програмування

Парадигма - це особливі концепти чи шаблони мислення в певній дисципліні.

Парадигма імперативного програмування - набір інструкцій для комп’ютера в фон-нейманівській архітектурі (процесор та пам’ять, в якій пам’ять даних та пам’ять інструкцій не відмежовуються архітектурно), які змінюють пам’ять (стан).

Парадигма функціонального програмування - це обчислення результатів виконання функцій над даними.

Теорія в математиці це:

Один чи більше тип даних
Операції над цими типами даних
Закони що пов’язують операції та результати цих операцій.

Теорії не описують зміну стану, тому що зміни стану знешкоджують дію корисних законів в математичній теорії.

Функціональне програмування має такі переваги:

Простіше виводити теореми (і будувати теорії) про програми
Краща модульність
Легше працювати з конкурентним кодом

Елементи програмування

REPL в Scala викликається командою scala. Далі вона може працювати як звичайний калькулятор.

Можна також писати означення:

def radius = 10

Імена обчислюються за допомогою їх заміни на означення. Оператори з операндами замінюються на результат застосування операторів до операндів.

В Scala всі імена і аргументи функцій мають тип. Приклад примітивних типів - Int, Double, Boolean

Функції означаються так:

def square(x: Double) = x * x
def power(x: Double, n: Int) = ...

Модель обчислень, при яких вирази замінюються їх значеннями називається моделлю заміщень (Substitution model). Ця модель описується в лямбда-численні.

Побічні ефекти (типовий приклад - вираз c++ ) неможливо описати моделлю заміщень.

Не кожен вираз заміщеннями можна обчислити за скінченний час, наприклад: def loop: Int = loop

При обчисленні функції перед заміщенням її імені означенням, всі аргументи обчислюються. Такий підхід називається call-by-value. Інший підхід - call-by-name, не вимагає обчислення значень аргументів перед застосуванням до них функції. Виклик за іменем має більше кроків ніж виклик за значенням, але не обчислюється, наприклад, коли аргумент не використовують.

Умовні вирази

def abs(x: Int) = if (x >= 0) x else -x

Булева логіка містить такі вирази: true, false, !b, b && b, b || b, і порівняння як у звичайних мовах програмування. Бінарні оператори не завжди потребують правого операнду щоб знайти значення.

def - означення за іменем, виконується при виклику. def x = loop - просто інше ім’я для loop. val - означення за значенням, виконується зразу. val x = loop - не закінчить виконання.

def and(x: Boolean, y: => Boolean) // приклад передачі параметру y за іменем.

Блок - це кілька виразів у фігурних дужках. Значення блоку дорівнює значенню останнього виразу. Наприклад:

{
  val x = f(3)
  x * x
}

Означення ззовні блоку видимі всередині. Але затіняються внутрішніми.

Крапка з комою використовується якщо кілька виразів знаходяться на одному рядку. Проте краще, якщо вираз багаторядковий, або писати його в дужках, або писати оператор в кінці рядка, щоб парсер Scala бачив що рядок ще не закінчений.

Хвостова рекурсія

Якщо функція останнє що виконує - це сама себе, то вона може оптимізуватись.

def factorial(n: Int) =
  if (n == 0) 1 else n * factorial(n - 1)

Не оптимізується, бо остання дія - множення.

Позначити функцію як хвостово-рекурсивну можна анотацією (декоратором):

import scala.annotation.tailrec

@tailrec
def factorial ...

Частково-рекурсивний факторіал:

def factorial(n: Int): Int = {
  def loop(acc: Int, n: Int) : Int =
    if (n == 0) acc
    else loop(acc * n, n - 1)
  loop(1, n)
}

Функції вищого порядку

Кожна функція має тип, який записується як A => B, що означає що функція приймає тип A, і повертає B. Або (A, B) => C - якщо функція двох аргументів. Для більшого числа аргументів - аналогічно.

Приклад функції що приймає функції:

map(l: List[Int], f: Int => Int): List[Int] 
// приймає список цілих, і функцію що приймає ціле і повертає інше ціле, 
// та повертає інший список такої ж довжини в якому всі значення 
// це результати виклику функцій до значень вхідного списку.

Анонімна функція: (x: Int, y: Int) => x + y, чи наприклад x => x * x, а тип виведеться.

(x, y) => x + y також можна записати як _ + _.

Каррінг

def sum(f: Int => Int)(a: Int, b: Int): Int = 
  if (a > b) 0 else f(a) + sum(f)(a + 1, b)

це синтаксичний цукор для

def sum(f: Int => Int): ((a: Int, b: Int) => Int) = {
  def sumF(a: Int, b: Int): Int = 
     if (a > b) 0
     else f(a) + sumF(a + 1, b)
  sumF
}