Заметки на полях

Небольшая ФП справочка по функциям

На самом деле есть всего с десяток функций, с помощью которых можно сделать всё что угодно, а всё остальное - в той или иной мере комбинация этих функций. Эти функции отлично работают для “обёрточных типов” Optional (оно же Maybe), List (и прочие “коллекции”), Either, Result и т.д.

Примеры реализованы в виде отдельных функций, а не методов.

Основная идея: показать максимально language-agnostic реализации функций, которые встречаются во многих языках, особенно с доминированием функционального подхода к написанию кода.

Нижеописанные примеры с List (или Array не суть в данном случае) - в принципе может быть любой тип последовательностей (Seq).

Для начала напишем функции, которые позволяют работать со списком удобно. Здесь мы постараемся “спрятать” всю языковую специфику, чтобы в дальнейшем её не касаться.

Прежде, чем продолжить: в js нет такой структуры как связный список. Её можно сделать достаточно легко. Давайте представим, что сущности, участвующие в функциях и есть связные списки, для которых нельзя просто так обратиться к элементу по индексу.

is_list (list?)

is_list - определяет, является ли что-то списком. Обычно эта функция реализована нативно или использует специфические для яп или платформы фишки. Для простоты будем считать списком результат el instanceof Array.

function is_list(el) {
   return el instanceof Array
}

is_list([]) // true
is_lils([1,2,3]) //true
is_list(42) // false

head (first, hd), tail(rest, tl)

head или hd или first - функция, которая возвращает первый элемент списка.

function head(list) {
  if (! is_list(list)) {return null}
  let [head] = list // или list[0] зная, что это массив  
  return head
}

head([1,2,3]) // 1

В ФП языках не всегда есть аналог массива, последовательно расположенного в памяти (Array в js или ArrayList из java), однако есть связный список. Отрубить “голову” связному списку занимает константное время - связный список представлен ссылкой на “головной” элемент. А вот забрать последний ненулевой элемент - для этого нужно пробежаться по всему списку, и то же самое при добавлении элемента в конец. Для решения этой проблемы существует такая структура как двусвязный список. Последним элементом связного списка является либо нулевое значение (null, nil и т.д.) или пустой список.

tail или tl или rest - “обратная” функция для head возвращает всё, кроме первого элемента.

function tail(list) {
  if (!is_list(list)) {return null}
  let [head, ...rest] = list
  return rest
}

tail([1,2,3]) // [2,3]

• Попробуйте самостоятельно реализовать функцию second используя head и tail
• Если вы справились с second можете взяться за функцию nth, которая возвращает n-ный элемент из списка

is_empty

is_empty - проверяет: является ли список пустым. Список является НЕпустым, если у него есть головной элемент отличный от нулевого значения (или в зависимости от реализации яп - отличного от пустого списка):

function is_empty(list) {
    return head(list) == [] || head(list) == null
}

reduce

reduce - делает некоторое действие для каждого элемента внутри обёртки, по итогу получается некоторое “аккумулированное” значение.

Виды встречающиеся в дикой природе:

list.reduce(func, initValue) 
reduce(list, func, initValue) 
reduce(func, init, list)

Простейшая наивная реализация выглядит так:

function reduceSimple(list, reduceF, init) {
  if (list.lenght == 0) {
      return init  // для упрощения 
  }
  let [head, ...tail] = list
  
  if (init == undefined) {
      init = head;
      list = tail;
  }
  let acc = init;
  for (const elem of list) {
      acc = reduceF(acc, elem)
  }     
  return acc;
}

Но что делать, если ваш любимый ЯП настолько прекрасен, что в нём нет оператора for:

function reduce(list, reduceF, seed) {

  function recReduce(seq, func, acc) {
   if (is_empty(seq)) {return acc }    
   return reduce(tail(seq), func, func(acc, head(seq)))    
  }

  if (is_empty(list)) { return seed }
  let [new_accum, new_seq] = seed == undefined ? [head(list), tail(list)] : [seed, list]
  return recReduce(new_seq, reduceF, new_accum)
}

НА САМОМ ДЕЛЕ существуют 2 формы reduce:

• reduceLeft (чаще всего это и есть reduce)
• reduceRight (присутствует в кстати в js).

Чем они отличаются? Название намекает на то, как данные будут редюиться - слева направо или справа налево.

Вышеописанный reduce - выполняется слева направо - то есть от первого элемента до последнего. Если при реализации reduceRight используем цикл, то проблем не возникает - мы просто итерируемся не с первого до последнего, а с последнего до первого, то как быть если с вашим любимым языком? Ну ….

function reduceRight(list, reduceF, seed) {
  function recReduceRight(seq, func, acc) {
    if (is_empty(seq)) { return acc }    
    return func(recReduceRight(tail(seq), func, acc), head(seq))    
   }

  if (is_empty(list)) { return seed }
  let [new_accum, new_seq] = seed == undefined ? [head(list), tail(list)] : [seed, list] 
  return recReduceRight(new_seq, reduceF, new_accum)
}

По мере разбора list мы наращиваем в стек вызова элементы, когда доходим до конца - закидываем изначальное значение seed, тем самым запускаем “разматывание” стека.

Если при сложении чисел в качестве элементов списка с заданным initValue или seed разницы не будет никакой - т.к. без разницы с какой стороны начинать сложение - то со сложением строк будет видна разница:

reduceRight("123", (acc, el) => acc + el, "") // "321"
reduce("123", (acc, el) => acc + el, "") // "123"
reduceSimple("123", (acc, el) => acc + el, "") // "123"

reduceRight - не может нивелироваться оптимизацией хвостовой рекурсии

Так же встречаются такие функции как fold, foldLeft, foldRight, которые про то же самое что и reduce. Иногда reduce даже базируется на fold, foldLeft, foldRight, иногда одно подменяется другим. см. про Fold

Итак, у нас есть функция reduce…

len

len - вычисляет длину списка. Для массивов эта информация может содержаться в поле length или с учётом последовательного расположения элементов в памяти легко вычисляться, как например в языке си: sizeof(array) / sizeof(array[0]). Но у нас же связные списки верно?

function len(list) {
   if (!is_list(list)) {return null} // не умеем вычислять длину для несписков
   return reduce(list,(count, el) => ++count, 0)
}

len([1,2,3]) // 3

take and skip

take - функция, которая берёт с начала некоторого списка n элементов и возвращает их.

function take(list , n) {

    function take_rec(seq, count_down, acc) {
        if(is_empty(seq) || count_down == 0) {return acc}
        return take_rec(tail(seq), --count_down, [...acc, head(seq)]) 
    }

    if(is_empty(list) || n <= 0) {return []}
    return take_rec(list, n, [])
}

take([1,2,3], 2) // [1,2]

skip - функция, которая пропускает n элементов сначала списка, и возвращает оставшиеся.

function skip(list, n) {
    function skip_rec(seq, count_down) {
        if(is_empty(seq) == 0 || count_down == 0) {return seq}
        return skip_rec(tail(seq), --count_down)
    }

    if(n < 0) {return []}
    return skip_rec(list, n, [])
}

skip([1,2,3], 2) // [3]

reverse

reverse - инвертирует последовательность элементов

function reverse(list) {
    function rec_reverse(seq, acc) {
        if (is_empty(seq)) {return acc}
        return rec_reverse(tail(seq), [head(seq), ... acc])
    }
    if(!is_list(list)) {return null}
    return rec_reverse(list, [])
}

reverse([1,2,3]) // [3,2,1]

reverse часто используется при работе со связными списками: эффективнее развернуть связный список, проделать некоторые операции с головными элементами и развернуть обратно, чем работать с последними элементами.

map

map - делает преобразование одного в другое для каждого элемента внутри обёртки, т.е. сколько элементов прошло через map - столько получили на выходе 1:1.

Напишем имплементацию map через имеющийся у нас reduce. Так же как и с reduce можно это делать через цикл и через рекурсию…, но зачем у нас уже есть reduce =)

 function map(list, func) {
 
// Сделаем оговорку, что используется reduceLeft, 
// поэтому el кладём в конец, так как в противном случае итоговый список будет в обратном порядке

 const reducer = (acc, el) => [...acc, func(el)]
 return reduce(list, reducer, [])
}

Кажется тут всё понятно? =)

map([1,2,3] (a, b) => a + b) // 6

concat

concat - соединяет два списка

function concat(l1, l2) {
   return reduce(l2, (base, el) => [...base, el], l1) 
}

concat([1,2,3], [4,5,6]) // [1,2,3,4,5,6]

В качестве базы (initValue) используется l1 и к нему по одному добавляются элементы из l2

В случае со связными списками такой способ был бы крайне неэффективен. Почему?

Сможете сделать его более эффективным при работе со связными списками сохраняя порядок следования элементов (сначала все из l1 затем все из l2), используя уже написанные функции?

filter

filter - исключает элемент из последовательности, если он не соответствует условию переданному в filter и оставляет те, которые соответствуют. pred - от predicate, это функция, которая возвращает true/false; выражение в if например тоже предикат.

function filter(list, pred) {
  const reducer = (acc, el) => pred(el) ? [..acc, el] : acc
  return reduce(list, reducer, []) 
}

filter([1,2,3], (el) => el >= 2) // [2,3]

Если посмотреть повнимательнее, то видно, что единственное различие между map и filter умещается в одну строчку :-)

flatten

flatten - убирает уровень вложенности у списка. Делает из списка списков просто список.

function flatten(list) {
    return reduce(list, (acc, el) => is_list(el) ? concat(acc, el) : [...acc, el], [])
}

flatten([[1,2], 3, [4,5,6]]) // [1,2,3,4,5,6]

Что здесь происходит: в списке list могут встречаться в качестве элемента как списки, так и “простые” элементы. Если мы встречаем список мы складываем acc и el в один список; если el не список - просто добавляем его.

Сможете сделать flatten, который убирает ВСЕ уровни вложенности ?

Ответ

 
function flatten(list) {
    return reduce(list, (acc, el) => is_list(el) ? concat(acc, flatten(el)) : [...acc, el], [])
}

flatmap или fmap

flatmap - подобно map применяет, переданную в качестве аргумента функцию к некоторой последовательности, “но есть нюансы”(с). flatmap ожидает, что результатом работы переданной функции будет структура такого же типа, как и та, над которой применяется функция. Для списка - результатом будет список, для Optional - Optional и т.п. для того, чтобы “развернуть” эту обёртку и сделать итоговый результат без вложенности, т.е. “плоским” (flat). Лучше всего будет показать на примере:

Пример

Предположим, мы идём в магазин со списком продуктов. В магазине продукты разложены по отделам с соответствующими категориями:

• market - ассоциативный массив вида категория продукта -> список с продуктами в количестве, которое имеется в магазине. Например, для fruits, если есть три киви и две груши, то будет 'fruits' : ['🍐', '🥝', '🍐', '🥝', '🥝']

// Наполняем полки в пределах 5 штук
const fillRandomCount = (el) => Array(Math.floor(Math.random() * 5 + 1))
                                .fill(el)

const market = {
    "fruits" : map(['🍌', '🍍', '🥭', '🍐', '🥝'],fillRandomCount),
    "drinks" : map(['🥛', '🍷', '🧋', '🧉'], fillRandomCount),
    "vegetables": map(['🥗', '🥦', '🥒', '🫑', '🥕', '🍅'], fillRandomCount),
    "berries": map(['🫐', '🍓', '🍒', '🍇'], fillRandomCount)
}

Так же у нас есть список покупок:

const shopList = {
"fruits" : {
    '🍌': 3,
    '🍐': 2
    },
"drinks": {
    '🥛': 1
    },
"vegetables" : {
    '🥦': 3,
    '🫑': 4,
    '🥕': 2
    }
} 

Пробуем набрать товаров в соответствии со списком. Если какого-то продукта нет в нужном количестве берём всё что есть =)

Object.entries - превращает объект или ассоциативный массив в последовательность пар [<key> <value>].

Здесь потребуется “широкий взгляд” на код

let res = map(Object.entries(shopList), (category_products_to_buy) => {
    // для каждой категории в нашем шоп листе
    let [category, products_with_counts_to_buy] = category_products_to_buy
    // находим продукты из нужной нам категории в магазине
    let market_products = market[category]
    // если нужной категории нет - вернём пустой массив
    if (market_products == undefined) {return []}
    return map(Object.entries(products_with_counts_to_buy), (products_and_counts) => {
        // для каждого продукта в этой категории и его количества
        let [product_to_buy, count] = products_and_counts
        // выбираем нужные нам продукты.
        let found_products = filter(market_products, (market_product) => market_product == product_to_buy)
        // Игнорируем тот факт, что количество продуктов в магазине должно уменьшаться по мере забора =)
        // Забираем нужное нам количество
        
        // TODO: написать логику, по которой в магазине уменьшается забранное количество продуктов.
        return take(found_products, count)})
        })

console.log(res)

По итогу получится что-то вроде:

[
  [ [ '🍌', '🍌' ], [ '🍐', '🍐' ] ],
  [ [ '🥛' ] ],
  [ [ '🥦' ], [ '🫑', '🫑', '🫑' ], [ '🥕', '🥕' ] ]
]

Хмм вроде всё правильно, но кассиру явно будет неудобно пробивать товары в таком виде. Вот здесь и пригодится flatMap:

function flatMap(list, func) {
    return reduce(list, (acc, el) => concat(acc, func(el)), [])
}

Теперь заменим map в нашем примере на flatMap

let res = flatMap(Object.entries(shopList), (category_products_to_buy) => {
    //     ☝🏼 здесь заменим `map` на `flatMap`
    
    // для каждой категории в нашем шоп листе
    let [category, products_with_counts_to_buy] = category_products_to_buy

    // находим продукты из нужной нам категории в магазине
    let market_products = market[category]

    // если нужной категории нет - вернём пустой массив
    if (market_products == undefined) {return []}

    return flatMap(Object.entries(products_with_counts_to_buy), (products_and_counts) => {
        //   ☝🏼 здесь заменим `map` на `flatMap`
        
        // для каждого продукта в этой категории и его количества
        let [product_to_buy, count] = products_and_counts

        // выбираем нужные нам продукты
        let found_products = filter(market_products, (market_product) => market_product == product_to_buy)
        // Игнорируем тот факт, что количество продуктов в магазине должно уменьшаться по мере забора =)
        // Забираем нужное нам количество

        // TODO: написать логику, по которой в магазине уменьшается забранное количество продуктов.
        return take(found_products, count)})
    })

в результате мы получим:

[
  '🍌', '🍌', '🍌', '🍐',
  '🍐', '🥛', '🥦', '🥦',
  '🥦', '🫑', '🫑', '🫑',
  '🫑', '🥕', '🥕'
]

👍🏻

Как вы могли заметить - логика внутри функций, которые были нами созданы умещается в несколько строчек. Несмотря на то, что функции похожи - каждая из них предназначена для разных задач.

Подытожим

Были реализованы важные функции, которые встречаются пожалуй во всех ЯП, поддерживающих функциональный стиль. Реализации их крайне наивны и могут отличаться от языка к языку.

Тем не менее основная идея будет повторяться так или иначе, и даже наивная реализация обладает всей полнотой функционала и предоставляет инструмент для решения внушительного круга задач.

Отмечу, что наивная реализация почти не затрагивает специфичных для какого-то конкретного языка фич (а если и затрагивает, то уверен их можно легко заместить), и поэтому могут быть перенесены на ваш любимый ЯП или любой другой. Например, деструктуризация массива let [head, ...tail] = list всего лишь получение первого элемента и оставшейся части последовательности.

▶▶

Нашли ошибку?