источник
Создал колесо, в соответствии с адресом проекта GitHub, создал дерево каталогов проекта, интуитивно отобразил структуру проекта, чтобы облегчить введение проекта. Добро пожаловать в Стар.
Стек технологий:
- ES6
- Vue.js
- Webpack
- Vuex
- lodash
- GitHub API
Приложение предполагает отображение дерева каталогов, а рекурсивный обход обязателен для метода реализации. который открыл мойlambda演算путешествие открытий.
путешествие открытий
Эта поездкаФибоначчикруизное судно, следующее будет включать в себя некоторыеJavaScriptНекоторые основные понятия функционального программирования. Если есть побочные реакции, такие как головокружение и тошнота (kan bu dong), для пассажиров совершенно нормально хотеть высадиться. Частые путешественники, пожалуйста, езжайте со спокойной душой.
Функции высшего порядка
В функциональном программировании часто называют функцию, которая принимает функцию в качестве аргумента или возвращает функцию в качестве результата.Функции высшего порядка.
map,filter,reduceВсе они являются функциями высшего порядка.Функции высшего порядка не являются таинственными и также используются в нашем повседневном программировании.
в ES6mapпример
const arr = [1, 2, 3, 4, 5, 6]
const powArr = arr.map(v => v * v)
console.log(powArr) // [ 1, 4, 9, 16, 25, 36 ]
хвостовой вызов
Хвостовой вызов — важная концепция функционального программирования, она сама по себе очень проста и относится кпоследний шагэто вызов другой функции. Хвостовой вызов — это функция более высокого порядка, которая выводит как возвращаемое значение.
Например:
function f(x) {
return g(x);
}
функцияf()функция была вызвана в концеg()
Важность хвостового вызова заключается в том, что он не добавляет новый фрейм стека в стек вызовов, а обновляет его, точно так же, как итерация.
хвостовая рекурсия
Мы все знакомы с рекурсией: функция вызывает сама себя, что называется рекурсией. Если хвост вызывает сам себя, это называется хвостовой рекурсией. Программа, которая часто используется для объяснения рекурсии, — это вычислениефакториал:
// ES5
function factorial(n) {
return n === 1 ? 1 : n * factorial(n - 1);
}
factorial(6) // => 720
// ES6
const factorial = n => n === 1 ? 1 : n * factorial(n - 1)
factorial(6) // => 720
Рекурсия очень требовательна к памяти, потому что ей нужно сохранять сотни записей вызовов одновременно, и она подвержена ошибкам "переполнения стека" (stack overflow). Но для хвостовой рекурсии, поскольку существует только одна запись вызова, ошибка «переполнение стека» никогда не возникнет. Для рекурсивных или взаимно рекурсивных функций, которые вызывают функции в хвостовой позиции, поскольку сама функция вызывается много раз, а уровень рекурсии очень глубокий, оптимизация хвостовой рекурсии делает исходное пространство стека вызовов O (n) только O (1)
Таким образом, хвостовая рекурсия имеет две характеристики:
- Вызов собственной функции (Self-call);
- Вычисления занимают только постоянное пространство стека.
Давайте посмотрим на факториальную функцию, оптимизированную с помощью хвостовой рекурсии:
// ES5
function factorial(n, total) {
return n === 1 ? total : factorial(n - 1, n * total);
}
factorial(6, 1) // => 720
// ES6
const factorial = (n, total) => n === 1 ? total : factorial(n - 1, n * total)
factorial(6, 1) // => 720
В ES6, пока используется хвостовая рекурсия, переполнения стека не произойдет, что относительно экономит память.
Факториальная функция вышеfactorial, используется факториальная функция после оптимизации хвостовой рекурсииtotalЭта промежуточная переменная для достижения рекурсивной реализации гарантирует, что последний шаг вызывает только саму себя и перезаписывает эту промежуточную переменную в параметр функции.Это имеет недостатки.Зачем вычислять факториал 6 и передавать две переменные 6 и 1 Шерстяная ткань? Решение柯里化.
карри
карри(Каррирование) — это метод преобразования функции, которая принимает несколько параметров, в функцию, которая принимает один параметр и возвращает новую функцию, которая принимает оставшиеся параметры и возвращает результат.
Объяснение в Википедии немного искажено, короче говоря,curryingФункция вызывается путем передачи только части аргументов в функцию, что позволяет ей возвращать замыкающую функцию для обработки остальных аргументов.
// 阶乘尾递归优化写法
function currying(fn, n) {
return function (m) {
return fn.call(this, m, n);
};
}
function tailFactorial(n, total) {
if (n === 1) return total;
return tailFactorial(n - 1, n * total);
}
const factorial = currying(tailFactorial, 1);
factorial(6) // => 720
Вот посмотрите на каррирование в ES6:
const fact = (n, total) => n === 1 ? total : fact(n - 1, n * total)
const currying = f => n => m => f(m, n)
const factorial = currying(fact)(1)
factorial(6) // => 720
Приведенный выше код каррируется, превращая хвостовую рекурсию в факториал, который принимает только один параметр и получает желаемое значение.factorial(6)функция с одним аргументом.
Думая 🤔, нет более простого способа реализовать описанный выше хвостовой рекурсивный каштан с одним параметром. Конечно, используя новые возможности функций ES6, значения функций по умолчанию.
Упрощенный вопрос:
const fact = (n, total = 1) => n === 1 ? total : fact(n - 1, n * total)
factorial(6) // => 720
Лямбда-выражения
существуетJavaScript, лямбда-выражения могут представлять анонимные функции.
Пример функции идентификации в JavaScript:
// ES5
var f = function (x) {
return x;
};
// ES6
const f = x => x
использоватьlambda表达式Напишите это так:λx.x
Теперь попробуйте использоватьlambda表达式写出递归(рекурсия анонимной функции), использовать рекурсивный эффектlambdaвыражение, воляlambdaВыражение проходит как один из параметров.
// ES5
function factorial(f, n) {
return n === 1 ? 1 : n * f(f, n - 1)
}
factorial(factorial, 6) // => 720
// ES6
const factorial = (f, n) => n === 1 ? 1 : n * f(f, n - 1)
factorial(factorial, 6) // => 720
Да, это все еще слишком некрасиво, чтобы делать это, никто не хочет писать факториальную функцию и передавать другие параметры. Решение все еще柯里化. Рекурсия лямбда-выражения, оптимизированная для хвостового вызова:
const fact = (f, n ,total = 1) => n === 1 ? total : f(f, n - 1, n * total)
const currying = f => n => m => f(f, m ,n)
const factorial = currying(fact)()
factorial(6) // => 720
В конце концов, цель достигнута, и получен факториал функции с одним аргументом.
Лямбда-исчисление
существуетЛямбда-исчислениеВсе функции в анонимны, у них нет имени, они принимают только одну входную переменную, функцию с одним аргументом.
Создайте функцию более высокого порядка, которая принимает функцию в качестве аргумента и имеет функцию, вызывающую саму себя в качестве аргумента:
const invokeWithSelf = f => f(f)
Напишите рекурсивный каштан, используя лямбда-исчисление:
const fact = f => (total = 1) => n => n === 1 ? total : f(f)(n * total)(n - 1)
const factorial = fact(fact)()
factorial(6) // => 720
Комбинатор черной магии Y
чтоКомбинатор Y?
Y = λf.(λx.f(xx))(λx.f(xx))
η-преобразованиеПосле написания:
Y = λf.(λx.f(λv.x(x)(v)))(λx.f(λv.x(x)(v)))
Напишите комбинатор лямбда-исчисления Y со стрелочными функциями ES6.
const Y = f =>
(x => f(v => x(x)(v)))
(x => f(v => x(x)(v)))
Вывод комбинатора Y
Начать рекурсивно с анонимной функцией
const fact = f => (total = 1) => n => n === 1 ? total : f(f)(n * total)(n - 1)
const factorial = fact(fact)()
factorial(6) // => 720
В приведенном выше коде шаблон повторяется три раза, f(f) дважды и факт(факт) один раз. Чтобы сделать код болееDRY, попробуй поставитьf(f)Развязка, переданная как параметр.
const fact = f =>
(g => (total = 1) => n => n === 1 ? total : g(n * total)(n - 1))(f(f))
const factorial = fact(fact)()
factorial(6) // => Maximum call stack size exceeded
Конечно, результат выполнения приведенного выше кода переполнит стек, потому что параметр в JavaScriptпередать по значению, формальные параметры должны быть сначала оценены, а затем переданы в функцию в качестве аргументов,f(f)При передаче в качестве параметра он будет вызывать себя бесконечно рекурсивно, вызывая переполнение стека. В это время вам нужно использовать лямбда-исчисление вη-变换. Принцип заключается в использованииленивая оценка.
η-преобразование
чтоη-преобразование? Две функции считаются равными, если они ведут себя одинаково (то есть возвращают один и тот же результат) для любых входных данных.
Эффективен в лямбда-исчисленииη-преобразование:f = λx.(fx)
в JavaScriptη-преобразование:f = x => f(x)
согласно сη-преобразование,f(f)Подставленный как функция, он эквивалентенx => f(f)(x)
const fact = x => (f => (total = 1) => n => n === 1 ? total : f(n * total)(n - 1))(v => x(x)(v))
const factorial = fact(fact)()
factorial(6) // => 720
Извлечение общих черт
Может быть, вы также нашлиf => (total = 1) => n => n === 1 ? total : f(n * total)(n - 1)Это рекурсивный метод после каррирования. вытаскиватьfactметод.
const fact = f => (total = 1) => n => n === 1 ? total : f(n * total)(n - 1)
const factorial = (x => fact((v => x(x)(v))))(x => fact((v => x(x)(v))))()
factorial(6) // => 720
Сборка Y
будет названfactФункция становится анонимной функцией, создавая фабричную функцию.Y,БудуfactФункция передается в качестве параметра.
const fact = f => (total = 1) => n => n === 1 ? total : f(n * total)(n - 1)
const Y = f => (x => f(v => x(x)(v)))
(x => f(v => x(x)(v))) // 瞧，这不就是黑魔法Y组合子嘛
const factorial = Y(fact)()
factorial(6) // => 720
Анонимная рекурсивная функция, реализованная комбинатором Y, подходит не только для рекурсивной обработки факториальной функции, но и любая рекурсивная фабричная функция может получить настоящую рекурсивную функцию после прохождения через функцию Y.
пейзажи по пути
Последовательность Фибоначчи
Математически,Последовательность Фибоначчиопределяется рекурсивно:
Проще говоря: то есть последовательность Фибоначчи начинается с 0 и 1, а последующие коэффициенты Фибоначчи складываются из двух предыдущих чисел.
0,1,1,2,3,5,8,13,21,34,55,89,144,233......
Рекурсивная реализация в JavaScript:
// 非尾递归
function fibonacci (n) {
if ( n <= 1 ) return 1;
return fibonacci(n - 1) + fibonacci(n - 2);
}
fibonacci(6) // 13
оптимизировано с использованием хвостовых вызововПоследовательность Фибоначчи
// 尾递归写法
function fibonacci (n , before , after) {
if( n <= 1 ) return before;
return fibonacci (n - 1, after, before + after);
}
fibonacci(6, 1, 2) // 13
использование лямбда-выраженийПоследовательность Фибоначчи
// ES6 lambda calculus
const Y = f => (x => f(v => x(x)(v)))(x => f(v => x(x)(v)))
const fibonacci = Y(
f => (n) => n <= 1 ? 1 : f(n - 1) + f(n - 2)
)
fibonacci(6) // 13
Эффект дропа
в жизни,Эффект дропа(эффект Дросте) — рекурсивная визуальная форма, означающая, что часть изображения совпадает со всем изображением, а изображение с эффектом Дросте имеет небольшую часть, похожую на целое изображение. И в этой маленькой части картинки будет маленькая часть, похожая на всю картину, и так далее... Название эффекта Дросте связано с упаковочной коробкой какао-порошка известного голландского бренда Droste (Дросте).Узор такой же, как и вся картинка
Суммировать
я делаюrepository-treeВ процессе проекта я узнал много нового, с чем раньше не сталкивался. Это также является моим первоначальным намерением. Я думаю о всевозможных идеях и пытаюсь найти способ их реализовать. Я, естественно, улучшу свои знания. Используйте этот пост в блоге, чтобы мотивировать себя продолжать обучение. Если что-то не так с приведенным выше определением, пожалуйста, хлопайте по кирпичам.
Ссылаться на
Руководство по функциональному программированию JS
Кантор, Гёдель, Тьюринг - вечная золотая диагональ