Функциональное программирование для школьников

Руслан Хуснетдинов

Функциональное программирование
для
школьников

Функция

Функция — это фрагмент программного кода, который описывает связь между одними данными и другими.

Пример

			
const makeHappy = (x) => { x + 🍦 }
			
		

Пример

			
const makeHappy = (x) => { x + 🍦 }
			
		
			
const x0 = 😐
const x1 = 🤔
const x2 = 😬
const x3 = 🤢
			
		

Пример для 11-го класса

			
const makeHappy = (x) => { x + 🍺 }
			
		
			
const x0 = 😐
const x1 = 🤔
const x2 = 😬
const x3 = 🤢
			
		

Пример для 11-го класса

			
const makeHappy = (x) => { x + 🍺 }
			
		
			
const x0 = 😐
const x1 = 🤔
const x2 = 😬
const x3 = 🤢
			
		
			
const y0 = makeHappy(x0) // 😆
const y1 = makeHappy(x1) // 😎
const y2 = makeHappy(x2) // 🤠
const y3 = makeHappy(x3) // 🤡
			
		

Пример для 11-го класса

			
const makeHappy = (x) => { x + 🍺 }

const data1 = [😐, 🤔, 😬, 🤢]
const data2 = data1.map(makeHappy)

data2      // [😆, 😎, 🤠, 🤡]
			
		

Объект первого класса

В JavaScript функции являются объектами первого класса (First Class Citizen). То есть мы можем создавать их в любом месте, передавать в качетсве аргументов в другие функции и т.д.

Функция есть значение.

Чистая функция

Чистая функция (pure function) — функция, которая не имеет побочных эффектов и является детерминированной.

Побочный эффект (side effect) — возможность функции читать и модифицировать значения глобальных переменных и осуществлять операции ввода-вывода.

Детерминированная функция — функция, которая всегда возвращают одно и то же значение для одних и тех же аргументов.

Пример

			
// Нечистая функция
const sum = (x) => num + x

let num = 5
let result = sum(💩) // 💩

num = result // 💩
result = sum(result)

			
		
			
result // 🐘
			
		

Пример

			
// Чистая функция
const sum = (a, b) => a + b

const num = 5
const result = sum(num, 2) // 7

const newNum = result // 7
const newResult = sum(newNum, result) // 14
			
		
Pure function

Неизменяемость

Неизменяемые данные (immutable) — данные, которые нельзя изменить.

Thinking

Пример

			
// Изменяемые данные
const arr = [1, 2, 3]
arr.push(💩)
arr // [1, 2, 3, 💩]

			
		
			
/* 🙌 */

			
		
			
arr // [1, 2, 3, 💩, 💩, 💩]
			
		

Пример

			
// Изменяемые данные (плохой пример)
const arr = [1, 2, 3]
const poo = (array) => array.push(💩)
arr // [1, 2, 3]

const newArr = poo(poo(poo(arr)))
newArr // [1, 2, 3, 💩, 💩, 💩]
			
		
			
arr // [1, 2, 3, 💩, 💩, 💩]
			
		
Thinking

Пример

			
// Изменяемые данные, которые не изменяют
const arr = [1, 2, 3]
const newArr = [...arr, 💩]

arr // [1, 2, 3]
newArr // [1, 2, 3, 💩]
			
		

Пример

			
// Неизменяемые данные
const arr = Object.freeze([1, 2, 3])
const newArr = Object.freeze([...arr, 💩])

arr // [1, 2, 3]
newArr // [1, 2, 3, 💩]
			
		

Пример

			
// Неизменяемые данные (Immutable.js)
const arr = Immutable.List([1, 2, 3])
const newArr = array.push(💩)

arr // [1, 2, 3]
newArr // [1, 2, 3, 💩]
			
		
Immutable

Функция высшего порядка

Функция высшего порядка (higher-order function) — функция, которая принимает в качестве аргументов или возвращает другие фунции.

Пример

			
const apply = (f) => (x) => f(x)

const dubble = (x) => 2 * x
const number = ☝️
const newNumber = apply(dubble)(number)

newNumber // 🤘
			
		

Рекурсия

Рекурсия (recursion) — процесс вызова функции самой себя.

При рекурсивном процессе программа откладывает вычисления до возвращения функцией её значения, сохраняя на каждом шаге эти вычисления в памяти.

При итеративном процессе (хвостовая рекурсия) программа производит все вычисления сразу и передает их дальше, незаписывая их в память.

Recursion

Пример 1

			
// Рекурсивный процесс
const factorial = (n) => {
  if (n === 1) {
    return 1
  }

  return n * factorial(n - 1)
}

const num = factorial(50) // Stack overflow (нет)
			
		

Пример 2

			
// Итеративный процесс
const factorial = (n, acc = 1) => {
  if (n === 1) {
    return acc
  }
  const newAcc = acc ? acc * n : n
  return factorial(n - 1, newAcc)
}

const num = factorial(50) // 3.0414093201713376e+64
			
		

Цикл

Цикл – это жёсткая управляющая конструкция, которую нелегко использовать повторно и сложно состыковать с другими операциями. Кроме того, использование циклов означает появление кода, который меняется с каждой итерацией.

Луис Атенцио. Функциональное программирование в JavaScript.

Функции map, filter и reduce

Функции map, filter и reduce — функции высшего порядка, которые являются альтернативой циклам.

Функция map

Map — функция высшего порядка, которая применяет передаваемую ей функцию ко всем элементам передаваемого ей массива и возвращает новый массив, состоящий из результатов этого применения.

Это функция трансформации.

Пример с циклами

			
// Цикл
const arr = [1, 2, 3]
const dubble = (x) => 2 * x
const newArr = []

for (let i = 0 i < arr.length i++) {
  newArr.push(dubble(arr[i]))
}

			
		
			
newArr // [2, 4, 6, 💩]
			
		

Пример с функцией

			
// Map
const arr = [1, 2, 3]
const dubble = (x) => 2 * x
const newArr = arr.map(dubble)

newArr // [2, 4, 6]
			
		

Пример реализации

			
// Реализация map
const map = (arr, f, acc = []) => {
  if (!arr.length) {
    return acc
  }
  const [head, ...tail] = arr
  const newAcc = [...acc, f(head)]

  return map(tail, f, newAcc)
}
			
		

Функция filter

Filter — функция высшего порядка, которая применяет передаваемую ей функцию ко всем элементам передаваемого ей массива и возвращает новый массив, состоящий из элементов первоначального массива, для которых передаваемая функция вернула истинное значение.

Это функция фильтрации.

Пример с циклом

			
// Цикл
const arr = [1, 2, 3]
const newArr = []

for (let i = 0 i < arr.length i++) {
  let value = arr[i]
  if (value % 2 === 0) {
    newArr.push(value)
  }
}

			
		
			
newArr // [💩]
			
		

Пример с функцией

			
// Filter
const arr = [1, 2, 3]
const newArr = arr.filter((value) => value % 2 === 0)

newArr // [2]
			
		

Пример реализации

			
// Реализация filter
const filter = (arr, f, acc = []) => {
  if (!arr.length) {
    return acc
  }
  const [head, ...tail] = arr
  const newAcc = f(head) ? [...acc, head] : acc

  return filter(tail, f, newAcc)
}
			
		

Функция reduce

Reduce — функция высшего порядка, которая применяет передаваемую ей функцию к передаваемому ей аккумулятору и ко всем элементам передаваемого ей массива и возвращает значение итогового аккумулятора.

Это функция свёртки.

Пример с циклом

			
// Цикл
const arr = [1, 2, 3]
let acc = 0

for (let i = 0 i < arr.length i++) {
  acc = acc + arr[i]
}

			
		
			
acc // 6
			
		

Пример с функцией

			
// Reduce
const arr = [1, 2, 3]
const acc = arr.reduce((acc, value) => acc + value)

acc // 6
			
		

Пример реализации

			
// Реализация reduce
const reduce = (arr, f, acc) => {
  if (!arr.length) {
    if (acc) { return acc } else { throw new Error() }
  }
  const [head, ...tail] = arr
  const newAcc = acc ? f(acc, head) : head

  return reduce(tail, f, newAcc)
}
			
		

Конец