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

Question

Это сложная тема моего предыдущего вопроса здесь:

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

Краткая идея

Простая функция ниже:

const L = a => L;

формы

L
L(1)
L(1)(2)
...

Похоже, это формирует список, но фактические данные вообще не сохраняются, поэтому, если требуется хранить такие данные, как [1,2], какова самая разумная практика для выполнения задачи?

Одна из выдающихся идей принадлежит @user633183, который я пометил как принятый ответ (см. Ссылку "Вопрос"), а @Matías Fidemraizer также предоставляет другую версию функции с карри.

Итак, здесь идет:

const L = a => {
  const m = list => x => !x
    ? list
    : m([...list, x]);
  return m([])(a);
}; 

const list1 = (L)(1)(2)(3); //lazy : no data evaluation here
const list2 = (L)(4)(5)(6);

console.log(list1()) // now evaluated by the tail ()
console.log(list2())  

Что мне действительно нравится, так это ленивая оценка.

Хотя данный подход удовлетворяет тому, что я упомянул, эта функция утратила внешнюю структуру, или я должен упомянуть:

Алгебраическая структура

 const L = a => L;

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

Оставил право личности

Одним из самых простых примеров моноидов и идентичности является число и "Strings" а также [Array] в JavaScript.

0 + a === a === a + 0
1 * a === a === a * 1

В строках пустое значение "" это элемент идентичности.

  "" + "Hello world" === "Hello world" === "Hello world" + ""

То же самое относится и к [Array],

То же самое относится и к L:

(L)(a) === (a) === (a)(L)

const L = a => L;

const a = L(5); // number is wrapped or "lift" to Type:L
                // Similarity of String and Array
                // "5"  [5]

//left identity
console.log(
  (L)(a) === (a)    //true 
);
 
//right identity
console.log(
  (a) === (a)(L)    //true
); 

и очевидная идентичность неизменности:

const L = a => L;
 
console.log(
  (L)(L) === (L)    //true
); 
console.log(
  (L)(L)(L) === (L)    //true
); 
console.log(
  (L)(L)(L)(L) === (L)    //true
); 

Также ниже:

const L = a => L;

const a = (L)(1)(2)(3);
const b = (L)(1)(L)(2)(3)(L);

 
console.log(
   (a) === (b)    //true 
);
 

Вопросы

Какой самый умный или самый элегантный способ (очень функциональный и без мутаций (нет Array.push также)) реализовать L это удовлетворяет 3 требованиям:

Требование 0 - Идентичность

Простая функция:

const L = a => L;

уже удовлетворяет закону идентичности, как мы уже видели.

Требование 1 - метод eval()

Хотя L удовлетворяет закону об идентичности, нет способа доступа к перечисленным / накопленным данным.

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

Ленивая оценка кажется правильным подходом, поэтому предоставление более четкой спецификации:

предоставлять eval метод L

const L = a => L; // needs to enhance to satisfy the requirements

const a = (L)(1)(2)(3);
const b = (L)(1)(L)(2)(3)(L);


console.log(
   (a) === (b)    //true 
);

console.log(
   (a).eval()    //[1, 2, 3]
);

console.log(
   (b).eval()    //[1, 2, 3]
);

Требование 3 - Моноид Ассоциативное право

В дополнение к выдающейся структуре Идентификации, Моноиды также удовлетворяют Закону об Ассоциации

(a * b) * c === a * b * c === a * (b * c)

Это просто означает "сгладить список", другими словами, структура не содержит вложенных списков.

[a, [b, c]] не хорошо

Образец:

const L = a => L; // needs to enhance to satisfy the requirements

const a = (L)(1)(2);
const b = (L)(3)(4);
const c = (L)(99);

const ab = (a)(b);
const bc = (b)(c);
const abc1 = (ab)(c);
const abc2 = (a)(bc);

console.log(
   abc1 === abc2  // true for Associative
);

console.log(
   (ab).eval()    //[1, 2, 3, 4]
);

console.log(
   (abc1).eval()   //[1, 2, 3, 4, 99]
);
console.log(
   (abc2).eval()   //[1, 2, 3, 4, 99]
);

Это все для 3 требований для реализации L как моноид

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

Спасибо.

Answer 1

Обновить

Вот карри версия tag техника, представленная @user633183.

Я заменил имя тега / это набрать вещи.

  const TYPE = Symbol();
  const typeOf = t => x => x == null
    ? x
    : Object.assign(x, {
      [TYPE]: t
    });

  const isType = t => x => x == null
    ? false
    : x[TYPE] === t;

  const Foo = x => typeOf(Foo)(x);

  console.log(
    isType(Foo)(1) // false
    , isType(Foo)([]) // false
    , isType(Foo)({}) // false
    , isType(Foo)(x => x) // false
    , isType(Foo)(true) // false
    , isType(Foo)(undefined) // false
    , isType(Foo)(null) // false
  );


  console.log(
    isType(Foo)(Foo(1)) // true
    , isType(Foo)(Foo([])) // true
    , isType(Foo)(Foo({})) // true
    , isType(Foo)(Foo(x => x)) // true
    , isType(Foo)(Foo(true)) // true
    , isType(Foo)(Foo(undefined)) // false
    , isType(Foo)(Foo(null)) // false
  );

  console.log(Foo(1) + Foo(2)); //3

Рефакторинг с typeOf а также isType,

Если (EVAL) применяется, весь процесс оценки называется.

Так как это моноид, я буду использовать M не L,

С некоторыми вспомогательными функциями для проверки с использованием JSON.stringfy

Update2

Успешно,

Моноиды

• тождественность
• ассоциативный

Список

• накопление
• Ленивая оценка

Спецификации разделены на каждую краткую функцию, и их состав представляет собой код ниже:

  //Debug/validation use-----------------
  const equalJSON = a => b => JSON.stringify(a) === JSON.stringify(b);
  const logEq = a => b => {
    const result = equalJSON(a)(b);
    console.log(result);
    return result;
  };   //Debug/validation use-----------------


const isPrimitive = val => (val !== Object(val));

const toObj = p => !isPrimitive(p)
  ? p //object return
  : (typeof (p) === "boolean")
    ? new Boolean(p)
    : (typeof (p) === "number")
      ? new Number(p)
      : (typeof (p) === "string")
        ? new String(p)
        : p; //Symbol()


const selfAware = i => i[i] = i;
const isAware = i => (i[i] === i);

const I = i => (i === I) || (i == null)
  ? i
  : selfAware(toObj(i));

const amI = i => (i === I)
  ? true
  : (i == null)
    ? false
    : isAware(i);







const flatArray = (arr1) => arr1
  .reduce((acc, val) => Array.isArray(val)
    ? [...acc, ...flatArray(val)]
    : [...acc, val], []);

const flatList = ls => ls.map(l => amI(l)
  ? flatList(l(EVAL)) : l);

//evaluation to be associative operation: flatten list

const evaluation = list => associative(list);
const associative = list => flatArray(flatList(list));

const identityType = f => { //left&right identity
  const T = x => (x === T)
    ? T //left identity
    : f(x);
  return I(T); //right identity
};


const EVAL = Symbol();
const M = identityType( //Monoid type constructer
  a => { // list accumulation recursion
    const m = list => x => (x === EVAL)
      ? evaluation(list) // list() triggered to eval
      : I(m([...list, x])); // data x joint
    return m([])(a); //initial empty [] list and data a
  }
);

//Validation================

console.log(
  (M) //[Function: M]
);
console.log(
  (M)(M)
);
console.log(
  (M)(M)(M)
);
console.log(
  (M)(M)(M)(M)
);
logEq(
  (M)(M)
)(
  (M)
); //true

logEq(
  (M)(M)(M)
)(
  (M)
); //true

logEq(
  (M)(M)(M)(M)
)(
  (M)
); //true


console.log(
  (M)(EVAL) // []
);
console.log(
  (M)(M)(EVAL) //[]
);
console.log(
  (M)(M)(M)(EVAL) //[]
);
console.log(
  (M)(M)(M)(M)(EVAL) //[]
);
const m = M(5);

//left identity
logEq(
  (M)(m)
)(
  (m)
); //true

//right identity
logEq(
  (m)
)(
  (m)(M)
); //true


console.log(
  (M)(1)(2)(3) //{ [Function: n] isList: true }
);

logEq(
  (M)(1)(2)(3)
)(
  (M)(99)
); //true without evaluation

logEq(
  (M)(1)(2)(3)(EVAL)
)(
  (M)(99)(EVAL)
); //false with evaluation

console.log(
  (M)(1)(2)(3)(EVAL) //[1, 2, 3]
);
console.log(
  (M)(1)(M)(2)(3)(M)(EVAL) //[1, 2, 3]
);

logEq(
  (M)(1)(2)(3)(EVAL) //[1,2,3]
)(
  (M)(1)(M)(2)(3)(M)(EVAL) //[1,2,3]
); //true

console.log("associative----------------");
const a = (M)(1)(2)(3);
const b = (M)(4)(5)(6);
const c = (M)(99);

const ab = (a)(b);
const bc = (b)(c);
const abc1 = (ab)(c);
const abc2 = (a)(bc);
console.log("no eval yet----------------");
console.log(
  (ab)(EVAL) //[1, 2, 3, 4, 5, 6]
);
console.log(
  (bc)(EVAL) //[4, 5, 6, 99]
);
console.log(
  (abc1)(EVAL) //[1, 2, 3, 4, 5, 6, 99]
);
console.log(
  (abc2)(EVAL) //[1, 2, 3, 4, 5, 6, 99]
);
logEq(
  (abc1)(EVAL)
)(
  (abc2)(EVAL)
); // true for Associative law

Answer 2

Ваш тип данных несовместим!

Итак, вы хотите создать моноид. Рассмотрим структуру моноида:

class Monoid m where
    empty :: m           -- identity element
    (<*>) :: m -> m -> m -- binary operation

-- It satisfies the following laws:

empty <*> x = x = x <*> empty     -- identity law
(x <*> y) <*> z = x <*> (y <*> z) -- associativity law

Теперь рассмотрим структуру вашего типа данных:

(L)(a) = (a) = (a)(L)     // identity law
((a)(b))(c) = (a)((b)(c)) // associativity law

Следовательно, согласно вам, элемент идентичности L и бинарная операция является приложением функции. Тем не мение:

(L)(1)                  // This is supposed to be a valid expression.
(L)(1) != (1) != (1)(L) // But it breaks the identity law.

// (1)(L) is not even a valid expression. It throws an error. Therefore:

((L)(1))(L)                // This is supposed to be a valid expression.
((L)(1))(L) != (L)((1)(L)) // But it breaks the associativity law.

Проблема в том, что вы объединяете двоичную операцию с конструктором обратного списка:

// First, you're using function application as a reverse cons (a.k.a. snoc):

// cons :: a -> [a] -> [a]
// snoc :: [a] -> a -> [a] -- arguments flipped

const xs = (L)(1)(2); // [1,2]
const ys = (L)(3)(4); // [3,4]

// Later, you're using function application as the binary operator (a.k.a. append):

// append :: [a] -> [a] -> [a]

const zs = (xs)(ys); // [1,2,3,4]

Если вы используете приложение функции как snoc тогда вы не можете использовать его для append также:

snoc   :: [a] ->  a  -> [a]
append :: [a] -> [a] -> [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) состоит в том, что объединение более эффективно, поскольку списки объединяются справа налево. Следовательно, он не копирует одни и те же значения снова и снова, если вы объединяете несколько списков.

Answer 3

зеркальный тест

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

is (Foo, 1)            // false   1 is not a Foo
is (Foo, tag (Foo, 1)) // true    tag (Foo, 1) is a Foo

Ниже мы реализуем is а также tag, Мы хотим спроектировать их так, чтобы мы могли ввести любое значение, и мы сможем надежно определить тег значения позже. Мы делаем исключения для null а также undefined,

const Tag =
  Symbol ()

const tag = (t, x) =>
  x == null
    ? x
    : Object.assign (x, { [Tag]: t })
    
const is = (t, x) =>
  x == null
    ? false
    : x[Tag] === t
  
const Foo = x =>
  tag (Foo, x)
  
console.log
  ( is (Foo, 1)         // false
  , is (Foo, [])        // false
  , is (Foo, {})        // false
  , is (Foo, x => x)    // false
  , is (Foo, true)      // false
  , is (Foo, undefined) // false
  , is (Foo, null)      // false
  )
  
console.log
  ( is (Foo, Foo (1))         // true    we can tag primitives
  , is (Foo, Foo ([]))        // true    we can tag arrays
  , is (Foo, Foo ({}))        // true    we can tag objects
  , is (Foo, Foo (x => x))    // true    we can even tag functions
  , is (Foo, Foo (true))      // true    and booleans too
  , is (Foo, Foo (undefined)) // false   but! we cannot tag undefined
  , is (Foo, Foo (null))      // false   or null
  )

Теперь у нас есть функция Foo который способен различать ценности, которые он произвел. Foo становится осознающим себя -

const Foo = x =>
  is (Foo, x)
    ? x              // x is already a Foo
    : tag (Foo, x)   // tag x as Foo

const f =
  Foo (1)

Foo (f) === f // true

L высшего сознания

С помощью is а также tag мы можем сделать List самосознание. Если дан вход List помеченное значение, List может ответить согласно вашей спецификации проекта.

const None =
  Symbol ()

const L = init =>
{ const loop = (acc, x = None) =>
    // x is empty: return the internal array
    x === None
      ? acc

    // x is a List: concat the two internal arrays and loop
    : is (L, x)
      ? tag (L, y => loop (acc .concat (x ()), y))

    // x is a value: append and loop
    : tag (L, y => loop ([ ...acc, x ], y))

  return loop ([], init) 
}

Мы попробуем это, используя ваши тестовые данные -

const a =
  L (1) (2)

const b =
  L (3) (4)

const c =
  L (99)

console.log
  ( (a) (b) (c) () // [ 1, 2, 3, 4, 99 ]
  , (a (b)) (c) () // [ 1, 2, 3, 4, 99 ]
  , (a) (b (c)) () // [ 1, 2, 3, 4, 99 ]
  )

Стоит сравнить эту реализацию с последней -

// previous implementation
const L = init =>
{ const loop = (acc, x) =>
    x === undefined   // don't use !x, read more below
      ? acc
      : y => loop ([...acc, x], y)
  return loop ([], init)
}

В нашей ревизии добавлена ​​новая ветка для is (L, x) это определяет новое моноидальное поведение. И самое главное, любое возвращаемое значение в завернутом tag (L, ...) так что позже он может быть идентифицирован как L помеченное значение. Другое изменение заключается в явном использовании None условное обозначение; дополнительные замечания по этому поводу были добавлены в конце этого поста.

равенство L ценности

Определить равенство L(x) а также L(y) мы столкнулись с другой проблемой. Составные данные в JavaScript представлены объектами, которые нельзя просто сравнить с === оператор

console.log
  ( { a: 1 } === { a: 1 } ) // false

Мы можем написать функцию равенства для L, возможно, называется Lequal

const l1 =
  L (1) (2) (3)

const l2 =
  L (1) (2) (3)

const l3 =
  L (0)

console.log
  ( Lequal (l1, l2) // true
  , Lequal (l1, l3) // false
  , Lequal (l2, l3) // false
  )

Но я не буду вдаваться в подробности в этом посте. Если вам интересно, я освещал эту тему в этом Q&A.

// Hint:
const Lequal = (l1, l2) =>
  arrayEqual   // compare two arrays
    ( l1 ()    // get actual array of l1
    , l2 ()    // get actual array of l2
    )

пометка в глубине

Техника тегирования, которую я использовал здесь, - та, которую я использую в других ответах Это сопровождается более обширным примером здесь.

другие замечания

Не использовать !x проверить пустое значение, потому что оно вернет true за любую "ложь" x, Например, если вы хотите составить список L (1) (0) (3) ... Это остановится после 1 так как !0 является true, Ложные значения включают 0, "" (пустой строки), null, undefined, NaN и конечно false сам. Именно по этой причине мы используем явное None символ для более точной идентификации, когда список заканчивается. Все остальные входы добавляются во внутренний массив.

И не полагайтесь на такие хаки, как JSON.stringify проверить на предметное равенство. Структурный обход абсолютно необходим.

const x = { a: 1, b: 2 }
const y = { b: 2, a: 1 }

console.log
  (JSON.stringify (x) === JSON.stringify (y)) // false

console.log
  (Lequal (L (x), L (y))) // should be true!

Для советов о том, как решить эту проблему, см. Этот Q&A