Церковное кодирование списков с использованием правильных сгибов и списков различий
Вот очередной вопрос после
Как хранить данные функциональной цепочки Monoidal List?
а также
Извлечение данных из цепочки функций без массивов
и здесь я хотел бы выразить свое уважение и благодарность авторам моих Вопросов, особенно @Aadit M Shah и @user633183
Теперь этот вопрос открыт, чтобы прояснить сходства и различия или связь между списком различий и церковным списком.
,
Список отличий
/questions/42518018/kak-hranit-dannyie-funktsionalnoj-tsepochki-monoidal-list/42518025#42518025
Список различий - это функция, которая берет список и добавляет к нему другой список. Например:
const concat = xs => ys => xs.concat(ys); // This creates a difference list.
const f = concat([1,2,3]); // This is a difference list.
console.log(f([])); // You can get its value by applying it to the empty array.
console.log(f([4,5,6])); // You can also apply it to any other array.Крутая вещь в списках различий состоит в том, что они образуют моноид, потому что они просто endofunctions:
const id = x => x; // The identity element is just the id function.
const compose = (f, g) => x => f(g(x)); // The binary operation is composition.
compose(id, f) = f = compose(f, id); // identity law
compose(compose(f, g), h) = compose(f, compose(g, h)); // associativity law
Более того, вы можете упаковать их в аккуратный маленький класс, где композиция функций является оператором точки:
class DList {
constructor(f) {
this.f = f;
this.id = this;
}
cons(x) {
return new DList(ys => this.f([x].concat(ys)));
}
concat(xs) {
return new DList(ys => this.f(xs.concat(ys)));
}
apply(xs) {
return this.f(xs);
}
}
const id = new DList(x => x);
const cons = x => new DList(ys => [x].concat(ys)); // Construct DList from value.
const concat = xs => new DList(ys => xs.concat(ys)); // Construct DList from array.
id . concat([1, 2, 3]) = concat([1, 2, 3]) = concat([1, 2, 3]) . id // identity law
concat([1, 2]) . cons(3) = cons(1) . concat([2, 3]) // associativity law
Вы можете использовать
applyметод для получения значенияDListследующее:
class DList {
constructor(f) {
this.f = f;
this.id = this;
}
cons(x) {
return new DList(ys => this.f([x].concat(ys)));
}
concat(xs) {
return new DList(ys => this.f(xs.concat(ys)));
}
apply(xs) {
return this.f(xs);
}
}
const id = new DList(x => x);
const cons = x => new DList(ys => [x].concat(ys));
const concat = xs => new DList(ys => xs.concat(ys));
const identityLeft = id . concat([1, 2, 3]);
const identityRight = concat([1, 2, 3]) . id;
const associativityLeft = concat([1, 2]) . cons(3);
const associativityRight = cons(1) . concat([2, 3]);
console.log(identityLeft.apply([])); // [1,2,3]
console.log(identityRight.apply([])); // [1,2,3]
console.log(associativityLeft.apply([])); // [1,2,3]
console.log(associativityRight.apply([])); // [1,2,3]Преимущество использования списков различий над обычными списками (функциональные списки, а не массивы JavaScript) состоит в том, что объединение более эффективно, поскольку списки объединяются справа налево. Следовательно, он не копирует одни и те же значения снова и снова, если вы объединяете несколько списков.
Список кодировки церкви
В качестве альтернативы кодированию с использованием церковных пар список можно закодировать, отождествив его с функцией правого сгиба. Например, список из трех элементов x, y и z может быть закодирован функцией более высокого порядка, которая при применении к комбинатору c и значению n возвращает cx (cy (czn)).
/questions/7959932/izvlechenie-dannyih-iz-tsepochki-funktsij-bez-massivov/7959947#7959947
Решение user633183 блестящее. Он использует кодирование списков по Церковью, используя правильные сгибы, чтобы облегчить необходимость продолжения, что приводит к более простому коду, который легко понять. Вот ее решение, измененное, чтобы сделать
foldrкажетсяfoldl:
const L = g => function (x, a) {
switch (arguments.length) {
case 1: return L((f, a) => f(g(f, a), x));
case 2: return g(x, a);
}
};
const A = L((f, a) => a);
const xs = A(1)(2)(3)(4)(5);
console.log(xs((x, y) => x + y, 0)); // 15
console.log(xs((x, y) => x * y, 1)); // 120
console.log(xs((a, x) => a.concat(x), [])); // [1,2,3,4,5]Вот
gцерковный список, накопленный до сих пор. Изначально это пустой список. призваниеgскладывает его справа. Однако мы также строим список справа. Следовательно, похоже, что мы строим список и сворачиваем его слева из-за того, как мы его пишем.
Если все эти функции сбивают вас с толку, то, что действительно делает user633183:
const L = g => function (x, a) {
switch (arguments.length) {
case 1: return L([x].concat(g));
case 2: return g.reduceRight(x, a);
}
};
const A = L([]);
const xs = A(1)(2)(3)(4)(5);
console.log(xs((x, y) => x + y, 0)); // 15
console.log(xs((x, y) => x * y, 1)); // 120
console.log(xs((a, x) => a.concat(x), [])); // [1,2,3,4,5]Как вы можете видеть, она строит список задом наперед, а затем использует
reduceRightсвернуть список в обратном направлении. Следовательно, похоже, что вы строите и складываете список вперед.
Что мне нравится видеть в Diffrence List, так это
- Это кажется естественным и понятным для понимания.
- С конкататацией (сплющиванием) образует моноиды
- Элемент Identity является функцией Identity и не требует внешних начальных значений.
Что мне не нравится
- По крайней мере, приведенный пример кода зависит от массива JavaScript
То, что мне нравится / не нравится в церковном списке, - это, по сути, опосайт вышеупомянутого.
мне нравится
- Он не зависит от реализации JavaScript Array и может сам определять операции: решение user633183
мне не нравится
- Я не знаю, почему он должен быть не левым, а правым сгибом?
список можно закодировать, отождествив его с функцией правого сгиба
Непонятно для реализации моноидов
В частности, Nil не является элементом Identity ( = функция тождества), и в примере кода необходимо указать внешние начальные значения.
Итак, что меня интересует, так это какая-нибудь формализация списка Diffrence, например, списка Церкви.
Спецификация будет
По сути, это список различий
Не зависит от реализации массива JavaScipt
Начальное значение - встроенная функция идентификации.
Спасибо вам.
4 ответа
Корень проблемы
Корень проблемы, лежащей в основе вашей серии вопросов, заключается в том, что вы настаиваете на использовании L(1)(2)(3) синтаксис для построения списка. Этот синтаксис не имеет никакого смысла, и люди неоднократно говорили вам отказаться от использования этого синтаксиса:
user633183 ответ на ваш самый первый вопрос:
Функциональное каррирование и переменные аргументы на самом деле не работают вместе. Это ограничение становится очевидным, когда вы понимаете, что следующие два выражения несовместимы
L (1) -> [ 1 ] L (1) (2) -> [ 1, 2 ]Выше
L (1)возвращает список, но во втором выражении мы ожидаемL (1)быть функцией, к которой мы можем обратиться2,L (1)может быть списком или функцией, которая создает список; это не может быть и то и другое одновременно.Комментарий Берги на ваш второй вопрос:
Прежде всего, если вы хотите использовать функциональное программирование, избегайте функций с переменным числом аргументов или странно смешанных типов возвращаемых данных.
user633183 ответ на ваш третий вопрос:
Итак, говоря о типах, давайте рассмотрим тип
autoCons-autoCons (1) // "lambda (x,n) => isFunction (x) ... autoCons (1) (2) // "lambda (x,n) => isFunction (x) ... autoCons (1) (2) (3) // "lambda (x,n) => isFunction (x) ... autoCons (1) (2) (3) (add, 0) // 6Что ж
autoConsвсегда возвращает лямбду, но этот лямбда имеет тип, который мы не можем определить - иногда он возвращает другую лямбду такого же типа, в других случаях он возвращает совершенно другой результат; в этом случае какое-то число,6Из-за этого мы не можем легко смешивать и комбинировать
autoConsвыражения с другими частями нашей программы. Если вы отбросите этот извращенный диск для создания разнообразных карри интерфейсов, вы можете сделатьautoConsэто типа
Я не вижу веской причины использовать L(1)(2)(3) синтаксис, когда вы могли бы просто написать toList([1,2,3]):
// null :: List a
// cons :: (a, List a) -> List a
const cons = (head, tail) => ({ head, tail });
// xs :: List Number
const xs = cons(1, cons(2, cons(3, null))); // You can either construct a list manually,
// toList :: Array a -> List a
const toList = array => array.length ? cons(array[0], toList(array.slice(1))) : null;
// ys :: List Number
const ys = toList([1,2,3]); // or you can construct a list from an array.
console.log(xs);
console.log(ys);Кроме того, если ваша единственная причина использовать L(1)(2)(3) Синтаксис состоит в том, чтобы "эффективно" помещать элемент в конец списка, тогда вы можете сделать это и с обычными списками. Просто создайте список задом наперед и используйте cons поставить новый элемент в начале списка.
Алгебраическая структура списков
Похоже, у вас есть неортодоксальные убеждения относительно структуры списков:
Во-первых, вы считаете, что заголовок списка всегда должен быть равен нулю:
традиционный способ построения списка, описанный в учебнике по lisp/Scheme, очень неправильный. Ноль не должен быть в конце списка, он должен быть в голове. Lisp/Scheme принесли много путаницы из-за искаженной структуры списка (0 = ноль в хвосте) в мире программирования.
Во-вторых, вы считаете, что вам не нужно указывать начальное значение для сгибов списка:
Я до сих пор не знаю обоснования, по которому вы придерживаетесь значения "init" для сгиба и т. Д. Глядя на некоторые библиотеки, они не используют "init", и я думаю, что они более разумны. https://github.com/benji6/church/blob/master/src/lists.js Чтобы быть точным, они в основном используют Zero=Identity для init, что имеет больше смысла.
Оба эти убеждения плохо информированы. Чтобы понять, почему нам нужно взглянуть на алгебраическую структуру списков:
┌──────────────────────────── A List of a
│ ┌──────────────────────── is
| | ┌──────────────────── either null
| | | ┌───────────────── or
| | | | ┌───────────── cons of
| | | | | ┌───────── an a and
│ | | | | | ┌─── another List of a.
┌──┴─┐ │ ┌─┴┐ | ┌─┴┐ | ┌──┴─┐
List a = null | cons (a, List a)
Список может быть либо пустым, либо непустым. Пустые списки представлены null, Непустые списки формируются путем помещения нового элемента перед другим (возможно, пустым) списком элементов с помощью cons, Мы помещаем новый элемент перед исходным списком, а не за ним, потому что это более естественно:
cons(1, cons(2, cons(3, null))); // This is easier to read and write.
snoc(snoc(snoc(null, 1), 2), 3); // This is more difficult to read and write.
Примечание: нет ничего плохого в использовании snoc, Мы могли бы определить List как List a = null | snoc (List a, a), Тем не менее, это просто более естественно использовать cons, Теперь, в зависимости от того, используем ли мы cons или же snoc определить List Тип данных, либо помещая новые элементы перед списком, либо помещая новые элементы за списком, становится дорогим:
in front of behind
┌─────────────┬─────────────┐
cons │ Inexpensive │ Expensive │
├─────────────┼─────────────┤
snoc │ Expensive │ Inexpensive │
└─────────────┴─────────────┘
Примечание. Использование синтаксиса Haskell для следующих двух абзацев.
Списки различий используются для амортизации стоимости дорогостоящей операции, задерживая объединение списков до тех пор, пока они не потребуются, а затем объединяя их в наиболее эффективном порядке. Например, предположим, что у нас есть выражение as ++ bs ++ cs ++ ds где мы объединяем четыре списка. Если мы используем cons реализация List тогда наиболее эффективный порядок объединения as ++ (bs ++ (cs ++ ds)) вот почему (++) Оператор в Haskell является ассоциативным справа. С другой стороны, если мы используем snoc реализация List тогда наиболее эффективный порядок объединения ((as ++ bs) ++ cs) ++ ds,
При использовании cons реализация List, список различий имеет вид (xs ++) где xs это обычный список. Мы можем составить их вперед, используя обычную композицию функций (т.е. (as ++) . (bs ++) . (cs ++) . (ds ++)). При использовании snoc реализация List, список различий имеет вид (++ xs) где xs это обычный список. Мы можем составить их задом наперед, используя обычную композицию функций (т.е. (++ ds) . (++ cs) . (++ bs) . (++ as)). Это еще одна причина, почему использование cons реализация List является более предпочтительным.
Теперь давайте поменяем передачи и поговорим о частях непустого списка. Когда дело доходит до списков (независимо от того, используем ли мы cons реализация List или snoc реализация List), условия head, tail, init а также last имеют очень конкретные значения:
head tail
│ ┌──────────┴─────────┐
cons(1, cons(2, cons(3, null)));
└──────┬─────┘ │
init last
init last
┌──────────┴─────────┐ │
snoc(snoc(snoc(null, 1), 2), 3);
│ └─┬─┘
head tail
-
headнепустого списка является первым элементом списка. -
tailнепустого списка - это все, кроме первого элемента списка. -
initнепустого списка - это все, кроме последнего элемента списка. -
lastнепустого списка, ну, последний элемент списка.
Следовательно, в зависимости от того, используем ли мы cons или же snoc определить List тип данных, либо head а также tail или же init а также last становится дороже:
head / tail init / last
┌─────────────┬─────────────┐
cons │ Inexpensive │ Expensive │
├─────────────┼─────────────┤
snoc │ Expensive │ Inexpensive │
└─────────────┴─────────────┘
В любом случае, это причина, по которой утверждение "Ноль не должно быть в конце списка, а должно быть в голове" не имеет смысла. Голова списка является первым элементом списка. Ноль не первый элемент списка. Поэтому нелогично утверждать, что ноль всегда должен быть главой списка.
Теперь давайте перейдем к складкам. В зависимости от того, используем ли мы cons или же snoc определить List тип данных, либо foldl или же foldr становится хвостовой рекурсивной:
foldl foldr
┌──────────────────────┬──────────────────────┐
cons │ Tail Recursion │ Structural Recursion │
├──────────────────────┼──────────────────────┤
snoc │ Structural Recursion │ Tail Recursion │
└──────────────────────┴──────────────────────┘
Хвостовая рекурсия обычно более эффективна, если язык выполняет оптимизацию хвостового вызова. Однако структурная рекурсия более естественна, и в языках с отложенной оценкой она становится более эффективной и может работать с бесконечными структурами данных. Говоря о бесконечных структурах данных, cons реализация растет бесконечно вперед (т.е. cons(1, cons(2, cons(3, ....)))) тогда как snoc реализация растет бесконечно назад (т.е. snoc(snoc(snoc(...., 1), 2), 3)). Еще одна причина, чтобы предпочесть cons над snoc,
В любом случае, давайте попробуем понять, почему требуется начальное значение сгиба. Предположим, у нас есть следующий список, xs = cons(1, cons(2, cons(3, null))) и мы складываем это, используя foldr:
cons func
/ \ / \
1 cons 1 func
/ \ -> foldr(func, init, xs) -> / \
2 cons 2 func
/ \ / \
3 null 3 init
Как вы можете видеть, когда мы сокращаем список с помощью foldr мы по существу заменяем каждый cons с func и мы заменяем null с init, Это позволяет вам делать такие вещи, как добавление двух списков, складывая первый список, заменяя cons с cons а также null со вторым списком, ys = cons(4, cons(5, cons(6, null))):
cons cons
/ \ / \
1 cons 1 cons
/ \ -> foldr(cons, ys, xs) -> / \
2 cons 2 cons
/ \ / \
3 null 3 cons
/ \
4 cons
/ \
5 cons
/ \
6 null
Теперь, если вы не предоставите начальное значение, значит, вы не сохраняете структуру списка. Следовательно, вы не сможете добавить два списка. На самом деле, вы даже не сможете восстановить тот же список. Рассматривать:
cons func
/ \ / \
1 cons 1 func
/ \ -> foldr1(func, xs) -> / \
2 cons 2 func
/ \ /
3 null 3
С помощью foldr1 Вы можете найти сумму списка без указания начального значения (т.е. foldr1(plus, xs)), но как бы вы воссоздали тот же список, не прибегая к колдовству? Если вы готовы предоставить начальное значение, то вы можете элегантно написать foldr(cons, null, xs), В противном случае это невозможно сделать, если вы не нарушите принципы функционального программирования и не будете использовать побочные эффекты для искусственного предоставления начального значения изнутри. func сам. В любом случае, вы собираетесь предоставить начальное значение, будь то путем явного указания начального значения или обработки последнего элемента списка как особого случая в func,
Выберите более простую альтернативу. Явно укажите начальное значение. Как утверждает дзен питона:
Красиво лучше, чем безобразно.
Явное лучше, чем неявное.
Простое лучше, чем сложное.
...
Особые случаи не настолько особенные, чтобы нарушать правила.
В любом случае, перейдем к последнему разделу.
Ответы, которые вы искали (и больше)
Было бы неправильно с моей стороны читать вам лекции, не отвечая ни на один из ваших вопросов. Следовательно:
Что касается списков различий, ваше следующее утверждение неверно:
- Элемент Identity является функцией Identity и не требует внешних начальных значений.
На самом деле, если вы сложите список различий, вам все равно потребуется указать начальное значение. Для справки см.
foldrфункция отData.DListпакет на Hackage.Что касается церковных списков, у вас возник следующий вопрос:
- Я не знаю, почему он должен быть не левым, а правым сгибом?
Из-за твоей шалости
L(1)(2)(3)синтаксис, вы можете только построить список в обратном направлении (т.е.L(1)(2)(3) = cons(3, cons(2, cons(1, null)))). Следовательно, если вы хотите свернуть список "вперед", то вы должны использоватьfoldrвместоfoldl, Обратите внимание, что если мы используемsnocвместоconsтогда это на самом деле вперед (то естьL(1)(2)(3) = snoc(snoc(snoc(null, 1), 2), 3)). Это следует из того, чтоsnocпростоconsс аргументами перевернул. Следовательно,foldrзаconsэквивалентноfoldlзаsnocи наоборот, это то, что заметил пользователь 633183.Обратите внимание, что мое первоначальное решение с использованием продолжений действительно использовало
foldlзаcons, но для того, чтобы сделать это, я должен был как-то перевернуть список, так как он строился задом наперед. Вот для чего были продолжения, чтобы перевернуть список. Только позже мне пришло в голову, что мне не нужно полностью менять список. Я мог бы просто использоватьfoldrвместоfoldl,Что касается вашего второго замечания о церковных зашифрованных списках:
- Непонятно для реализации моноидов
Все списки являются моноидами, где элемент идентичности
nullи бинарная операцияappend = (xs, ys) => foldr(cons, ys, xs), Обратите внимание, чтоfoldr(cons, null, xs) = xs(левая личность) иfoldr(cons, ys, null) = ys(правильная личность). Более того,foldr(cons, zs, foldr(cons, ys, xs))эквивалентноfoldr(cons, foldr(cons, zs, ys), xs)(Ассоциативность).Что касается вашего третьего пункта о церковных зашифрованных списках:
- В частности, Nil не является элементом Identity ( = функция тождества), и в примере кода необходимо указать внешние начальные значения.
Да, на самом деле ноль является элементом идентификации для списков. Если
ListТип данных реализован как список разностей, тогда nil - это функция тождества. В противном случае, это что-то еще. Тем не менее, ноль всегда является элементом идентичности для списков.Мы уже обсуждали, зачем нужны внешние начальные значения. Если вы их не предоставите, вы не сможете выполнять определенные операции, такие как
append, Вы должны предоставить начальное значение, чтобы добавить два списка. Либо вы предоставляете начальное значение явно, либо вы предоставляете начальное значение искусственно, обрабатывая первый элемент (при использованииfoldl) или последний элемент (при использованииfoldr) списка как особого случая (и тем самым нарушая принципы функционального программирования).Наконец, относительно интерфейса вашей мечты:
Итак, что меня интересует, так это какая-нибудь формализация списка Diffrence, например, списка Церкви.
Почему вы хотите это сделать? Чего ты надеешься достичь? Церковное кодирование интересно только в теории. Это не очень эффективно на практике. Кроме того, списки различий полезны только тогда, когда вы случайным образом объединяете списки (тем самым, используя преимущества моноидальной структуры списков различий, чтобы сгладить их). Объединение этих двух - действительно плохая идея.
В любом случае, я надеюсь, что вы перестанете задавать такие вопросы и уделите время чтению SICP.
Я не знаю, почему он должен быть не левым, а правым сгибом?
Не существует такой вещи, как "она не должна быть левой складкой" или "она должна быть правой складкой". Моя реализация была выбором, и я предоставил вам очень маленькую программу, чтобы дать вам уверенность, чтобы сделать выбор самостоятельно
Непонятно по отношению к моноидам
Реализация, которую я дал для append это моноидная бинарная операция, nil это элемент идентичности.
const nil =
(c, n) => n
const cons = (x, y = nil) =>
(c, n) => c (y (c, n), x)
const append = (l1, l2) =>
(c, n) => l2 (c, l1 (c, n))
// monoid left/right identity
append (nil, l) == l
append (l, nil) == l
// associativity
append (a, append (b, c)) == append (append (a, b), c)
В частности, Nil не является элементом Identity ( = функция тождества), и в примере кода необходимо указать внешние начальные значения.
Нет, nil это элемент идентичности, как показано выше.
Как правило, ваша цепочка вопросов касается различных способов реализации типа данных в стиле списка без использования составных данных JavaScript. [] или же {},
На самом деле существует множество способов реализовать список. Конечно, существует много традиционных дизайнов, но если ваша цель - создать их самостоятельно, то нет "лучшего" или даже "лучшего" типа. Каждая реализация разработана вокруг набора критериев.
Списки различий и правые списки Черча - только две возможные кодировки. Мы можем использовать совершенно другую кодировку для упрощенного списка -
const nil =
() => nil
const cons = (x, y = nil) =>
k => k (x, y)
Этот список можно свернуть влево или вправо
const foldl = (f, init) => l =>
l === nil
? init
: l ((x, y) => foldl (f, f (init, x)) (y))
const foldr = (f, init) => l =>
l === nil
? init
: l ((x, y) => f (foldr (f, init) (y), x))
Общие функции карт и фильтров реализованы тривиально foldlr
const map = f =>
foldr
( (acc, x) => cons (f (x), acc)
, nil
)
const filter = f =>
foldr
( (acc, x) => f (x) ? cons (x, acc) : acc
, nil
)
map (x => x * x) (autoCons (3, 4, 5))
// == autoCons (9, 16, 25)
filter (x => x !== 4) (autoCons (3, 4, 5))
// == autoCons (3, 5)
Обратите внимание, что они по существу идентичны предыдущей реализации, хотя nil а также cons построить совершенно другую структуру данных. Это мощная сущность абстракции данных.
length а также toArray не нужно никаких изменений. Мы можем реализовать интерфейс Monoid -
const append = (l1, l2) =>
l1 === nil
? l2
: l1 ((x, y) => cons (x, append (y, l2)))
// left/right identity
append (nil, l) == l
append (l, nil) == l
// associativity
append (a, append (b, c)) == append (append (a, b), c)
append (autoCons (1, 2, 3), autoCons (4, 5, 6))
// == autoCons (1, 2, 3, 4, 5, 6)
Монада? Конечно -
const unit = x =>
cons (x, nil)
const bind = f =>
foldl
( (acc, x) => append (acc, f (x))
, nil
)
// left/right identities
bind (f) (unit (x)) == f (x)
bind (unit, m) == m
// associativity
bind (g) (bind (f) (m)) == bind (x => bind (g) (f (x)))
bind (x => autoCons (x, x, x)) (autoCons (1, 2, 3))
// == autoCons (1, 1, 1, 2, 2, 2, 3, 3, 3)
Прикладное?
const ap = mx =>
bind (f => map (f) (mx))
ap (autoCons (2, 3, 4)) (autoCons (x => x * x, x => x ** x))
// == autoCons (2 * 2, 3 * 3, 4 * 4, 2 ** 2, 3 ** 3, 4 ** 4)
// == autoCons (4, 9, 16, 4, 27, 256)
Дело в том, что ни одна из этих реализаций не является особенной. Список здесь и список, данный в моем другом ответе, могут легко удовлетворить эти интерфейсы, потому что nil а также cons сформировать надежный договор. То же самое со списком различий - это просто еще одна реализация с четко определенным и надежным поведением. Каждая реализация имеет свой собственный профиль производительности и будет работать по-разному в разных ситуациях.
В качестве упражнения вы должны попробовать собственную реализацию nil а также cons Затем создайте оттуда другие функции первого и высшего порядка.
традиционный способ построения списка, описанный в учебнике по lisp/Scheme, очень неправильный. Ноль не должен быть в конце списка, он должен быть в голове. Lisp/Scheme принесли много путаницы из-за искаженной структуры списка (0 = ноль в хвосте) в мире программирования.
Вы понятия не имеете, что говорите
Это продолжение /questions/12198317/tserkovnoe-kodirovanie-spiskov-s-ispolzovaniem-pravilnyih-sgibov-i-spiskov-razlichij/12198319#12198319
Ответ @ Аадит М Шах
Теперь давайте перейдем к складкам. В зависимости от того, используем ли мы
consили жеsnocопределитьListтип данных, либоfoldlили жеfoldrстановится хвостовой рекурсивной:
foldl foldr
┌──────────────────────┬──────────────────────┐
cons │ Tail Recursion │ Structural Recursion │
├──────────────────────┼──────────────────────┤
snoc │ Structural Recursion │ Tail Recursion │
└──────────────────────┴──────────────────────┘
Хвостовая рекурсия обычно более эффективна, если язык выполняет оптимизацию хвостового вызова. Однако структурная рекурсия более естественна, и в языках с отложенной оценкой она становится более эффективной и может работать с бесконечными структурами данных. Говоря о бесконечных структурах данных,
consреализация растет бесконечно вперед (т.е.cons(1, cons(2, cons(3, ....)))) тогда какsnocреализация растет бесконечно назад (т.е.snoc(snoc(snoc(...., 1), 2), 3)). Еще одна причина, чтобы предпочестьconsнадsnoc,
Фальшивка snoc как Structural Recursion естественна, и я хотел бы поделиться там ответом. /questions/23401563/kakoe-opredelenie-dlya-estestvennaya-rekursiya/23401573#23401573
"Естественная" (или просто "структурная") рекурсия - лучший способ начать обучение студентов рекурсии. Это потому, что у него есть замечательная гарантия, на которую указывает Джошуа Тейлор: она гарантированно прекратит [*]. Студентам достаточно трудно сосредоточиться на такой программе, и если сделать это "правилом", это может спасти их от удара головой о стену.
Когда вы решаете покинуть сферу структурной рекурсии, вы (программист) берете на себя дополнительную ответственность, которая заключается в том, чтобы гарантировать, что ваша программа останавливается на всех входах; это еще одна вещь, чтобы подумать и доказать.
Еще одна причина, чтобы предпочесть снок вместо минусов.
В любом случае, давайте попробуем понять, почему требуется начальное значение сгиба. Предположим, у нас есть следующий список,
xs = cons(1, cons(2, cons(3, null)))и мы складываем это, используяfoldr:
cons func
/ \ / \
1 cons 1 func
/ \ -> foldr(func, init, xs) -> / \
2 cons 2 func
/ \ / \
3 null 3 init
Как вы можете видеть, когда мы сокращаем список с помощью
foldrмы по существу заменяем каждыйconsсfuncи мы заменяемnullсinit, Это позволяет вам делать такие вещи, как добавление двух списков, складывая первый список, заменяяconsсconsа такжеnullсо вторым списком,ys = cons(4, cons(5, cons(6, null))):
cons cons
/ \ / \
1 cons 1 cons
/ \ -> foldr(cons, ys, xs) -> / \
2 cons 2 cons
/ \ / \
3 null 3 cons
/ \
4 cons
/ \
5 cons
/ \
6 null
Теперь, если вы не предоставите начальное значение, значит, вы не сохраняете структуру списка. Следовательно, вы не сможете добавить два списка. На самом деле, вы даже не сможете восстановить тот же список. Рассматривать:
cons func
/ \ / \
1 cons 1 func
/ \ -> foldr1(func, xs) -> / \
2 cons 2 func
/ \ /
3 null 3
С помощью
foldr1Вы можете найти сумму списка без указания начального значения (т.е.foldr1(plus, xs)), но как бы вы воссоздали тот же список, не прибегая к колдовству? Если вы готовы предоставить начальное значение, то вы можете элегантно написатьfoldr(cons, null, xs), В противном случае это невозможно сделать, если вы не нарушите принципы функционального программирования и не будете использовать побочные эффекты для искусственного предоставления начального значения изнутри.funcсам. В любом случае, вы собираетесь предоставить начальное значение, будь то путем явного указания начального значения или обработки последнего элемента списка как особого случая вfunc,
Ну, я действительно не понимаю, почему вы делаете это, когда я написал код без начального значения и опроверг эту серию мнений о том, что "должно быть указано начальное значение".
Я уже показал часть своего кода, но, опять же, вот как:
const plus = a => b => Number(a) + Number(b);
const sum = left => right => left === I
? right
: plus(left(sum))(right);
log(
list3(sum)
);
Когда вы жестко кодируете "начальное значение", что вы на самом деле делаете?
Например, для операции "плюс", как вы выбрали начальное значение должно быть 0?
Это пришло из ниоткуда? Никогда, на самом деле 0 в качестве начального значения определяется сам бинарный оператор.
В вашей голове вы подумали: "Хорошо, 0+a = a = a + 0, так что это должно быть начальное значение!",
или вы подумали: "Хорошо 1 * a = a = a * 1, так что это должно быть!",
или вы подумали: "Хорошо, [].concat(a) = [a], так что [Muse] будет начальным значением!"
право? Что делаешь? Вы просто берете элемент идентичности в своей голове, и это абсолютно бессмысленно, потому что мы используем компьютер и пишем код!
Если то, что вам действительно нужно, это элемент идентичности, код как таковой. По крайней мере, я сделал.
const sum = left => right => left === I //hit the bottom of pairs
? right // reflect the right value of the bottom pair.
Если это I отражать правильное значение нижней пары, потому что я тождество I = a=>aи на самом деле я мог бы переписать код как:
const sum = left => right => left === I
? (left)(right)
: plus(left(sum))(right);
Обратите внимание, так как он попадает в нижнюю пару, операция цикла:
plus(left(sum))(right) становится (left)(right)
таким образом, нам не нужно тратить нашу работу мозга только для того, чтобы идентифицировать очевидные начальные значения, такие как 0 или же 1 или же [] это в основном ценности личности.
const list = L(3)(4)(5)
const max = (a, b) => (a > b) ? a : b;//initial value would be -Infinity
const min = (a, b) => (a < b) ? a : b;//initial value would be Infinity
Можно определить бинарные операторы для идентификации первого / последнего, который не зависит от реализации левого / правого сгиба.
const first = (a, b) => a; //initial value is 3 <= nonsense
const last = (a, b) => b; //initial value is 3 <= nonsense
// what if the list members is unknown??
Моя реализация:
Личность / ноль на голове не хвосты
Не требуются жесткие начальные значения.
const log = (m) => {
console.log(m); //IO
return m;
};
const I = x => x;
const K = x => y => x;
const V = x => y => z => z(x)(y);
const left = K;
const right = K(I);
log("left right test---------");
log(
left("boy")("girl")
);
log(
right("boy")("girl")
);
const pair = V;
const thePair = pair("boy")("girl");
log("pair test---------");
log(
thePair(left)
);//boy
log(
thePair(right)
);//girl
const list1 = pair(I)(1);// Identity/Nil on the head not tails...
const list2 = pair(list1)(2);
const list3 = pair(list2)(3);
log("list right test---------");
log(
list3(right)
);//3
//Dive into the list and investigate the behevior
log("inspect---------");
const inspect = left => right => left === I
? (() => {
log(right);
return I;
})()
: (() => {
log(right);
return left(inspect);
})();
list3(inspect);
log("plus---------");
const plus = a => b => Number(a) + Number(b);
const sum = left => right => left === I
? right
: plus(left(sum))(right);
log(
list3(sum)
);
log("fold---------");
const fold = f => left => right => left === I
? right //if root Identity, reflect the right of the pair
: f(left(fold(f)))(right);
log(
list3(fold(plus))
);
log("list constructor---------");
const isFunction = f => (typeof f === 'function');
const _L = x => y => z => isFunction(z)
? L(pair(x)(y)(z)) // not a naked return value but a list
: _L(pair(x)(y))(z);
const L = _L(I);
log(
L(1)(2)(3)(fold(plus))
);//fold returns a list // type match
log("inspect the result------------------------");
const plusStr = a => b => String(a) + String(b);
// binary operators define the type or
//the category of Monoid List
const unit = (a) => [a];
const join = ([a]) => [].concat(a);
const flatUnit = a => join(unit(a));
const toArray = a => x => flatUnit(a)
.concat(x);
L(1)(2)(3)
(fold(plus))
(inspect);
//6
L(1)(2)(3)
(fold(plusStr))
(inspect);
//"123"
L(1)(2)(3)
(fold(toArray))
(inspect);
//[ 1, 2, 3 ]Исходя из этой реализации, я хотел бы ответить на
Церковное кодирование списков с использованием правильных сгибов и списков различий
Корень проблемы
Корень проблемы, лежащей в основе вашей серии вопросов, заключается в вашем настойчивом использовании
L(1)(2)(3)синтаксис для построения списка.
Как мы уже подтвердили, нет ничего плохого в том, чтобы составлять список только по функциям. Церковное кодирование - это способ построить все с помощью функции карри. Так что это утверждение неверно.
Этот синтаксис не имеет никакого смысла, и люди неоднократно говорили вам отказаться от использования этого синтаксиса:
Если вы настаиваете на том, что причина в том, что что-то не имеет смысла, из-за того, что "люди неоднократно говорили вам воздерживаться", я рад сказать, что вы не правы, и давайте посмотрим, что сказали люди.
- user633183 ответ на ваш самый первый вопрос:
Функциональное каррирование и переменные аргументы на самом деле не работают вместе. Это ограничение становится очевидным, когда вы понимаете, что следующие два выражения несовместимы
L (1) -> [ 1 ]
L (1) (2) -> [ 1, 2 ]
Выше
L (1)возвращает список, но во втором выражении мы ожидаемL (1)быть функцией, к которой мы можем обратиться2,L (1)может быть списком или функцией, которая создает список; это не может быть и то и другое одновременно.
Проблема несоответствия типов уже решена, следовательно, эта проблема больше не существует для L,
- Комментарий Берги на ваш второй вопрос:
Прежде всего, если вы хотите использовать функциональное программирование, избегайте функций с переменным числом аргументов или странно смешанных типов возвращаемых данных.
Опять же, проблема несоответствия типов уже решена, следовательно, эта проблема больше не существует для L,
- user633183 ответ на ваш третий вопрос:
Итак, говоря о типах, давайте рассмотрим тип
autoCons-
autoCons (1) // "lambda (x,n) => isFunction (x) ...
autoCons (1) (2) // "lambda (x,n) => isFunction (x) ...
autoCons (1) (2) (3) // "lambda (x,n) => isFunction (x) ...
autoCons (1) (2) (3) (add, 0) // 6
Что ж
autoConsвсегда возвращает лямбду, но этот лямбда имеет тип, который мы не можем определить - иногда он возвращает другую лямбду такого же типа, в других случаях он возвращает совершенно другой результат; в этом случае какое-то число,6Из-за этого мы не можем легко смешивать и комбинировать
autoConsвыражения с другими частями нашей программы. Если вы отбросите этот извращенный диск для создания разнообразных карри интерфейсов, вы можете сделатьautoConsэто типа
Опять же, проблема несоответствия типов уже решена, следовательно, эта проблема больше не существует для L И, наконец, обратите внимание, это не я, кто реализовал, чтобы сделать L возвращает голое значение, без L,
Я не вижу веской причины использовать
L(1)(2)(3)синтаксис, когда вы могли бы просто написатьtoList([1,2,3]):
Также нет абсолютно никаких оснований запрещать использовать L(1)(2)(3) синтаксис, когда есть другой способ записи. Это проблема выбора.
Кроме того, если ваша единственная причина использовать
L(1)(2)(3)Синтаксис состоит в том, чтобы "эффективно" помещать элемент в конец списка, тогда вы можете сделать это и с обычными списками. Просто создайте список задом наперед и используйтеconsпоставить новый элемент в начале списка.
Я должен прокомментировать эффективность позже, но до сих пор, почему на земле кто-то должен реализовать обратный список в обратном порядке, когда существующий метод alreday достигает его естественно и просто?? Как вы можете оправдать это нарушением простоты только для того, чтобы поддержать использование лихорадки в "нормальных списках"?? Что вы подразумеваете под "нормальным"?
К сожалению, я не могу найти здесь ни одного из "корней проблемы".
Алгебраическая структура списков
Похоже, у вас есть неортодоксальные убеждения относительно структуры списков:
- Во-первых, вы считаете, что заголовок списка всегда должен быть равен нулю:
традиционный способ построения списка, описанный в учебнике по lisp/Scheme, очень неправильный. Ноль не должен быть в конце списка, он должен быть в голове. Lisp/Scheme принесли много путаницы из-за искаженной структуры списка (0 = ноль в хвосте) в мире программирования.
Правильный. На самом деле, у меня есть еще одна причина, которую я еще не определил. Я определю позже.
- Во-вторых, вы считаете, что вам не нужно указывать начальное значение для сгибов списка:
Я до сих пор не знаю обоснования, по которому вы придерживаетесь значения "init" для сгиба и т. Д. Глядя на некоторые библиотеки, они не используют "init", и я думаю, что они более разумны. https://github.com/benji6/church/blob/master/src/lists.js Чтобы быть точным, они в основном используют Zero = Identity для init, что имеет больше смысла.
Правильный.
Оба эти убеждения плохо информированы. Чтобы понять, почему нам нужно взглянуть на алгебраическую структуру списков:
Список может быть либо пустым, либо непустым. Пустые списки представлены
null, Непустые списки формируются путем помещения нового элемента перед другим (возможно, пустым) списком элементов с помощьюcons, Мы помещаем новый элемент перед исходным списком, а не за ним, потому что это более естественно:
cons(1, cons(2, cons(3, null))); // This is easier to read and write.
snoc(snoc(snoc(null, 1), 2), 3); // This is more difficult to read and write.
Ну, я могу понять, теперь вы настаиваете
1 + 2 + 3 записать как функцию бинарного оператора в последовательной операции трудно читать и писать, потому что это
plus(plus(plus(0, 1), 2), 3);
и мы должны ввести "ноль на каждом хвосте", потому что это легче читать и писать? Sereiously? Я бы не согласился, и мне интересно, что чувствуют другие люди.
Ну, чтобы выразить следующую структуру
Список
aлибо ноль, либо минусыaи еще один списокa,
const list1 = pair(I)(1);// Identity/Nil on the head not tails...
const list2 = pair(list1)(2);
выглядит более "естественно" для меня. Фактически этот синтаксис структуры напрямую соответствует Append операция.
Кроме того, факт минусы / нильсы заключается в следующем:
Для получения списка списков пользователю / коду необходимо добавить несколько логик проверки вставки Nils и Nils для каждой операции cons. Это действительно надоедает и теряет простоту кода.
Для "snoc", Nil / Zero / Null / 0or1, независимо от того, является ли элемент идентификации первой единицы, поэтому проверка вставки Nil не требуется для каждой операции. Опять же, это так же, как мы не проверяем проверку вставки Nil для каждого времени бинарных операций, таких как + или же x, Мы заботимся только о личности на голове или корне.
Примечание: нет ничего плохого в использовании
snoc, Мы могли бы определитьListкакList a = null | snoc (List a, a), Тем не менее, это просто более естественно использоватьcons, Теперь, в зависимости от того, используем ли мыconsили жеsnocопределитьListТип данных, либо помещая новые элементы перед списком, либо помещая новые элементы за списком, становится дорогим:
in front of behind
┌─────────────┬─────────────┐
cons │ Inexpensive │ Expensive │
├─────────────┼─────────────┤
snoc │ Expensive │ Inexpensive │
└─────────────┴─────────────┘
Это довольно очевидная низкая стоимость для "позади", или для добавления имеет больше преимуществ. Довольно редко нам нужно добавлять новые данные в существующие списки.
Примечание. Использование синтаксиса Haskell для следующих двух абзацев.
список различий... Это еще одна причина, почему использование
consреализацияListявляется более предпочтительным.
Требование взлома, такое как diffrence для эксплуатационных расходов, является взломом, который "snoc" не нуждается. Поэтому я действительно не понимаю, что ваше мнение о существовании обходного метода является преимуществом.
Теперь давайте поменяем передачи и поговорим о частях непустого списка. Когда дело доходит до списков (независимо от того, используем ли мы
consреализацияListилиsnocреализацияList), условияhead,tail,initа такжеlastимеют очень конкретные значения:
head tail
│ ┌──────────┴─────────┐
cons(1, cons(2, cons(3, null)));
└──────┬─────┘ │
init last
init last
┌──────────┴─────────┐ │
snoc(snoc(snoc(null, 1), 2), 3);
│ └─┬─┘
head tail
-
headнепустого списка является первым элементом списка. -
tailнепустого списка - это все, кроме первого элемента списка. -
initнепустого списка - это все, кроме последнего элемента списка. -
lastнепустого списка, ну, последний элемент списка.
Следовательно, в зависимости от того, используем ли мы
consили жеsnocопределитьListтип данных, либоheadа такжеtailили жеinitа такжеlastстановится дороже:
head / tail init / last
┌─────────────┬─────────────┐
cons │ Inexpensive │ Expensive │
├─────────────┼─────────────┤
snoc │ Expensive │ Inexpensive │
└─────────────┴─────────────┘
Это верно, и это распространенный сценарий, когда для кода нужны новые данные = "последний" и накопленные данные = "инициал", и это было так легко реализовать в моем собственном коде, потому что "snoc" / pair обеспечивает left ("init") и right ("последний") с недорогой стоимостью.
const plus = a => b => Number(a) + Number(b);
const sum = left => right => left === I
? right
: plus(left(sum))(right);
log(
list3(sum)
);
Это очень лаконично и легко реализовать, читать / писать и понимать.
Конечно, простота проистекает из одинаковой структуры между последовательной операцией Plus бинарный оператор и pair ("Snoc").
//`1 + 2 + 3`
plus(plus(plus(0, 1), 2), 3);
snoc(snoc(snoc(ID, 1), 2), 3);
В любом случае, это причина, по которой утверждение "Ноль не должно быть в конце списка, а должно быть в голове" не имеет смысла. Голова списка является первым элементом списка. Ноль не первый элемент списка. Поэтому нелогично утверждать, что ноль всегда должен быть главой списка.
Я не вижу смысла выбирать более сложные структуры, особенно для начинающих.
На самом деле слово cons используется везде и с другой стороны, snoc очень редко можно найти.
https://en.wikipedia.org/wiki/Cons не описывает даже пустое слово snoc и, конечно, нет никаких объяснений. Я думаю, что это действительно нездоровая ситуация. что происходит здесь??
Я знаю, что есть исторический контекст: https://en.wikipedia.org/wiki/S-expression, и хотя важно уважать работы пинонеров, однако переоценку сложности по простой структуре можно объяснить только авторитаризмом.
Мне очень жаль, но я, вероятно, должен отметить, что часть ответственности - ваша, на самом деле, очень опытные программисты и замечательные наставники с энтузиазмом, как вы, ребята, по некоторым причинам переоценивают cons и недооценивать snoc,
Если бы я был учителем, чтобы преподавать список детям, какую структуру на первом месте? "Snoc". Это прямолинейно, более понятно и проще в использовании.
Сходство с последовательной двоичной операцией.
//`1 + 2 + 3`
plus(plus(plus(0, 1), 2), 3);
snoc(snoc(snoc(ID, 1), 2), 3);
Легко.
Минусы? Тяжело с Нильсом.
Я отделю остальную часть респондента от другого поста, потому что это слишком долго. =>