В своем первом посте я хотел сделать что-то необычное. Я не хочу утомлять вас сверхсерьезными фактами или прикрывать что-то практическое в этом отношении. Вместо этого мы займемся своего рода упражнением по программированию. Идеи в этом посте взяты из математической темы под названием Церковные кодировки и вдохновлены другой статьей Список без лямбды.

Сегодняшняя цель - восстановить функциональность языка с помощью ОЧЕНЬ ограниченного набора инструментов. Что-то вроде головоломки «много строи с малого». Мы будем создавать структуру данных списка Javascript, используя ничего, кроме функций.

Часть 1: Закрытие

Важная предпосылка для понимания содержания этого поста - немного знать о функциях Javascript. В частности, вам нужно будет понять, как работают замыкания. Если вы чувствуете себя комфортно с закрытием, переходите к Части 2! Если нет, не беспокойтесь! Мы расскажем о них подробно, и если вас все еще смущает конец объяснения, я свяжу вас с ресурсами, которые объясняют вещи лучше, чем я. Я больше не буду ходить вокруг да около. Ответим на вопрос: что такое закрытие?

Говоря языком разработчика, замыкание - это комбинация функции и лексической среды, в которой эта функция была объявлена. Вы можете думать об этом так; все функции Javascript закрываются. Все функции Javascript содержат ссылку на свою внешнюю среду.

Например:

В этом фрагменте кода у нас есть функция foo, которая выдает некоторое значение bar. Поскольку функции в Javascript имеют ссылку на их внешнюю область видимости, мы можем получить доступ к переменной bar изнутри нашей функции foo.

Хотя эта функциональность довольно стандартна, не так ли? Функции, имеющие доступ к глобальной области видимости, поддерживаются почти на всех языках программирования. Замыкания становятся намного интереснее, когда наш язык поддерживает первоклассные функции. Первоклассный означает, что наши функции можно рассматривать как обычные значения. Это дает нам несколько новых возможностей.

  • Назначение функций переменным
  • Передача функций в качестве аргументов другим функциям
  • Возврат функций из других функций

Рассмотрим случай, когда функция возвращает функцию. Как мы уже говорили, все функции Javascript закрываются. Это означает, что наша возвращенная функция имеет доступ ко всей среде, в которой она была объявлена. Итак, наша возвращенная функция имеет доступ ко всему, что объявлено внутри внешней функции!

Вот пример, который может помочь:

Возвращая функцию изнутри функции, вы не только получаете возвращаемую функцию при вызове, но и возвращаемая функция также получает доступ к своей внешней среде во время ее создания. Функция «закрывается» во внешней среде, следовательно, закрывается :)

На всякий случай рассмотрим еще один пример.

Здесь мы написали функцию под названием idGenerator. Он принимает в качестве аргумента некоторую строку префикса и возвращает функцию. Возвращенная функция возвращает нам увеличенный идентификатор при каждом вызове. Давайте рассмотрим его подробнее. Мы назначаем getCatId функции, возвращаемой idGenerator("cat"). Когда я вызываю функцию getCatId, она генерирует новый идентификатор, добавляя idPrefix с suffix, назначенным внутри функции idGenerator. После того, как он сгенерирует новый код, мы увеличили счетчик suffix, поэтому в следующий раз, когда мы вызовем функцию getCatId, мы получим другой идентификатор кошки.

Этот пример демонстрирует еще одну интересную особенность замыканий. Вы можете не только читать данные из внешней среды возвращаемой функции, но и изменять ее. Если вы имеете опыт объектно-ориентированного программирования, вы можете думать о suffix как о частной переменной. Я не могу получить доступ к suffix вне idGenerator функции напрямую, но я смог вернуть функцию, которая может!

Я получил этот вопрос на собеседовании пару лет назад. Очень легко решить, если вы понимаете замыкания - довольно сложно, если вы полагаетесь на глобальное общее состояние.

Если этих примеров достаточно и вы чувствуете себя комфортно с закрытием в Javascript, давайте продолжим! Если нет, не стесняйтесь взглянуть на ресурсы ниже. Стоит потратить время на изучение этого вопроса, особенно если вы регулярно используете Javascript.

Https://developer.mozilla.org/en-US/docs/Web/Javascript/Closures

Https://blog.bitsrc.io/a-beginners-guide-to-closures-in-Javascript-97d372284dda

Https://www.youtube.com/watch?v=F3EsDDp4VXg

Часть 2. Давайте составим список

Что, если бы Javascript не предоставил нам структуру в виде списка? Ни массивов, ни объектов. Можно ли построить собственное?

Во-первых, давайте создадим некоторые критерии того, что должна обеспечивать эта структура списка.

Список желаний (каламбур):

  1. Нам нужна концепция пустого списка.
    isEmpty([]) // true
  2. Нам нужно иметь возможность добавлять элементы к существующему списку.
    prepend(1, [2, 3]) // [1, 2, 3]
  3. Нам нужно получить начало и конец списка. (Head является первым элементом списка, а хвост - списком всего, кроме первого элемента)
    head([1, 2, 3]) //1
    tail([1, 2, 3]) // [2, 3]

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

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

Начнем с основ: с пустого списка. Как мы определим пустой список? null пока кажется подходящим. Имея это в виду, мы можем реализовать пару наших TODO s

Теперь давайте реализуем prepend. Это самая сложная функция для понимания. Найдите минутку, чтобы прочитать prepend реализацию ниже, и подумайте, как вы могли бы написать head и tail. Цель prepend - добавить элемент в начало существующего списка и вернуть его. Если вы застряли, пытаясь понять prepend, переходите к следующей части - она ​​дает дополнительный контекст того, как используется prepend.

Ключевой вывод из этого заключается в том, что prepend возвращает функцию. Ранее я сказал, что prepend должен возвращать список. Так где же список? Функция вернула ЕСТЬ наш список. На самом деле prepend на самом деле не создает список. Вместо этого он просто склеивает две вещи и хранит их в укупорке. НО, мы все еще можем рассматривать это как список.

Давайте вернемся к критериям для нашего списка - единственные операции, которые нам действительно нужны, - это захват головы, хвоста и добавление нового элемента к нашему списку. Мы можем сделать это с помощью этой возвращенной функции!

Хочешь увидеть как?

Немного запутались? Помните, что наша функция prepend возвращает функцию. Возвращенная функция принимает аргумент option, равный либо "head", либо "tail", и возвращает head или tail, как они были указаны в аргументах внешней prepend функции. Это простая идея, но очень незнакомая и трудная для понимания, поэтому не волнуйтесь, если она еще не совсем ясна.

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

На данный момент нас не волнуют случаи ошибок (вызовы head и tail в пустом списке). Итак, предполагая, что наши функции head и tail получают список безработных, давайте вернем голову и хвост соответственно.

Вот и все! Мы просто вызываем функцию списка с "head" и "tail". У нас есть все функции, которые мы намеревались создать! Мы назовем это нашей реализацией списка версии 1.

Итак, у нас есть список, но где хранятся данные? Значения фактически хранятся внутри вложенных замыканий. Каждый вызов функции prepend возвращает замыкание, в области действия которого зафиксированы значения head и tail.

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

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

Хорошо, вернемся к вспомогательным функциям…

Реализации:

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

Список предложений помощников:

printList - берет список и распечатывает каждый элемент

sum - берет список чисел и возвращает их сумму

reverse - берет список и возвращает перевернутую версию списка

Часть 3: Удаление струн

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

Текущая панель инструментов:

  • функции
  • струны
  • логические значения / выражения равенства
  • операторы if / else

Давайте начнем с исключения использования строк в нашей реализации списка.

Были сделаны! Больше никаких струн!

Это изменение кода не было слишком большим, но заслуживает пояснения. Все, что требуется функциям head и tail, - это доступ к фактическому началу и концу списка. В нашем случае списки - это просто функции, поэтому мы можем дать нашему списку функцию выбора, которую мы можем вызывать со значениями head и tail.

Если в этом нет никакого смысла, я предлагаю просмотреть пример, чтобы увидеть, как это работает. Очень полезно записать это на бумаге для себя, но я постараюсь изо всех сил показать пример шаг за шагом.

const tear_worthy_movies = prepend("Cast Away", empty)                       head(tear_worthy_movies)                       
// => "Cast Away"

Пошаговое руководство:
(отдельные шаги разделяются линией)

// Line 1
const myList = prepend("Cast Away", empty)
____________________________________________________________________
// Reduction of the prepend call in Line 1
const myList = function(op) {       
  return op("Cast Away", empty)
}
____________________________________________________________________
// Line 2
head(myList)
____________________________________________________________________
// Expanding the head function from Line 2
(function(list){
  return list(function(head, tail) {
    return head;
  })
})(myList)
____________________________________________________________________
// Reduction of Step 4
myList(function(head, tail) {
   return head
})
____________________________________________________________________
// Expanding the myList function 
(function(op) {
  return op("Cast Away", empty)
})(function(head, tail) {
   return head
})
____________________________________________________________________
// Reduction of Step 6
 (function(head, tail) { return head })("Cast Away", empty)
____________________________________________________________________
// Final Reduction
 "Cast Away"

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

Часть 4: Удаление If / Else

Обновленный набор инструментов:

  • функции
  • логические значения / выражения равенства
  • операторы if / else

Перейдем к удалению операторов if / else. В настоящее время операторы if / else используются только для проверки того, пуст ли список. Один из способов избежать этого - пометить каждый список как пустой или непустой. Для этого нам нужно внести пару изменений. Во-первых, нам нужно добавить новый параметр в нашу функцию selector, которая определяет, пуст список или нет. Далее, значение пустого списка больше не может быть просто null. Нам нужно будет присвоить нашему значению empty функцию списка, которая помечает список как пустой.

Часть 5: Удаление логических значений

Мы прошли довольно долгий путь с версии 1, но еще предстоит проделать большую работу. Нам нужно удалить эти логические значения. Но как мы можем это сделать? В конечном итоге нам нужен способ определить, пуст ли список, а это значит, что нам нужен способ выполнения условных выражений. Давайте попробуем переписать условные выражения с помощью функций. Звучит немного устрашающе, но это выполнимо.

Еще раз, здесь нам нужно думать о вещах очень абстрактно. Какая основная функциональность НЕОБХОДИМА для работы наших условных выражений?

1.) Необходимо предоставить константы как для true, так и для false.

2.) Необходимо использовать эти константы для выбора между двумя вещами (по сути, if/else операторов)

Мы собираемся записать наши истинные и ложные значения как функции, которые выбирают между двумя вещами.

Наша функция truthy принимает две вещи и всегда возвращает первое, а наша функция falsey принимает две вещи и всегда возвращает последнее. Как они будут использоваться как истинные и ложные значения? Без особого контекста это не имеет большого смысла, но реализация ifelse должна пролить свет на ответ.

Условное выражение, передаваемое в ifelse, всегда будет либо truthy, либо falsey.

Пример:

Мы просто написали функциональность if / else, не используя ничего, кроме функций Javascript!

Отлично, но как это применить к нашим спискам? Мы просто должны иметь возможность заменить использование истинного и ложного на truthy и falsey.

Однако возникает вопрос: почему мы написали ifelse?

Это не очень очевидно, но нам нужно, чтобы isEmpty можно было использовать в других наших вспомогательных функциях списков. Наши старые реализации таких вещей, как length, map и filter, опирались на нашу старую реализацию isEmpty. Эта реализация больше не работает, потому что встроенные в Javascript операторы if / else не будут работать с нашими значениями truthy и falsey.

Пришло время рефакторинга!

Давайте снова реализуем длину, используя наши недавно сформированные списки.

Вроде разумное и простое решение. К сожалению, есть проблема. Этой проблемы мы не можем избежать, потому что она укоренилась на уровне языка Javascript.

Чтобы найти проблему, представьте, что мы назвали length в пустом списке.

length(empty)

Вышеупомянутая строка выдаст следующее:

ifelse(isEmpty(list),
         0,                                
         1 + length(tail(list)))

Несмотря на то, что наш список пуст и единственная ветвь, которая должна выполняться, - это 0, 1 + length(tail(list)) все равно будет запущена, потому что ifelse - это просто функция, а 1 + length(tail(list)) - аргумент, который мы дали этой функции. Короче говоря, 1 + length(tail(list)) будет оцениваться независимо от результата isEmpty(list), и когда это произойдет, мы попытаемся получить конец пустого списка, что невозможно.

Итак, как мы можем избежать этой проблемы? Как нам отложить выполнение до тех пор, пока мы не должны выполнить конкретную ветвь функции ifelse? Ответ на этот вопрос такой же, как и почти на все заданные до сих пор вопросы: функции!

Это также требует, чтобы мы изменили наши исходные логические значения:

к этому:

Остается последняя реализация наших функциональных списков:

Наконец-то мы достигли своей конечной цели! Это структура данных списка, использующая только функции Javascript. Поиграйте с этим больше и посмотрите, какие еще функциональные возможности языка вы можете создать с помощью функций (let-выражения, циклы, числа и т. Д.). Ниже приведена ссылка на репозиторий, содержащий весь код, который я показал здесь, а также некоторые дополнительные помощники по спискам и рефакторинг ES6, если вам интересно.

Надеюсь, это упражнение заставило вас думать немного по-другому и не вызвало особого разочарования. Попытки создать что-то с очень ограниченным набором инструментов часто приводят к очень креативным решениям, которые вы бы не использовали в повседневном программировании.

Спасибо за чтение!

Реализация функционального списка: https://github.com/claytn/Playground/tree/master/LineXLine/ListOutOfLambda

Подписывайтесь на меня на Github