чередной вопрос после

Как хранить данные функциональной цепочки Monoidal List?

а также

Извлечение данных из цепочки функций без массивов

и здесь я хотел бы выразить свое уважение и благодарность авторам моих Вопросов, особенно @Aadit M Shah и @ user633183

Теперь этот вопрос открыт для выяснения сходства и различий или отношений междуСписок отличий а такжеЦерковный список

.

Список отличий

https://stackoverflow.com/a/51320041/6440264

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

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 возвращает c x (c y (c z n)).

https://stackoverflow.com/a/51420884/6440264

Решение 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

Начальное значение - встроенная функция идентификации.

Спасибо вам.