How to store data of a functional chain of Monoidal List?

Question

This is an advanced topic of my prior question here:

How to store data of a functional chain?

The brief idea is

A simple function below:

const L = a => L;

forms

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

This seems to form a list but the actual data is not stored at all, so if it's required to store the data such as [1,2], what is the smartest practice to have the task done?

One of the prominent ideas is from @user633183 which I marked as an accepted answer(see the Question link), and another version of the curried function is also provided by @Matías Fidemraizer .

So here goes:

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())  

What I really like is it turns out lazy evaluation.

Although the given approach satisfies what I mentioned, this function has lost the outer structure or I must mentiion:

Algebraic structure

 const L = a => L;

which forms list and more fundamentally gives us an algebraic structure of identity element, potentially along with Monoid or Magma.

Left an Right identity

One of the easiest examples of Monoids and identity is number and "Strings" and [Array] in JavaScript.

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

In Strings, the empty quoate "" is the identity element.

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

Same goes to [Array].

Same goes to 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
); 

and the obvious identity immutability:

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
); 

Also the below:

const L = a => L;

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

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

Questions

What is the smartest or most elegant way (very functional and no mutations (no Array.push, also)) to implement L that satisfies 3 requirements:

Requirement 0 - Identity

A simple function:

const L = a => L;

already satisfies the identity law as we already have seen.

Requirement 1 - eval() method

Although L satisfies the identity law, there is no method to access to the listed/accumulated data.

(Answers provided in my previous question provide the data accumulation ability, but breaks the Identity law.)

Lazy evaluation seems the correct approach, so providing a clearer specification:

provide eval method of 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]
);

Requirement 3 - Monoid Associative law

In addition to the prominent Identify structure, Monoids also satisfies Associative law

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

This simply means "flatten the list", in other words, the structure does not contain nested lists.

[a, [b, c]] is no good.

Sample:

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]
);

That is all for 3 requirements to implement L as a monoid.

This is a great challenge for functional programming to me, and actually I tried by myself for a while, but asking the previous questions, it's very good practice to share my own challenge and hear the people and read their elegant code.

Thank you.

Answer 1

Your data type is inconsistent!

So, you want to create a monoid. Consider the structure of a monoid:

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

Now, consider the structure of your data type:

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

Hence, according to you the identity element is L and the binary operation is function application. However:

(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.

The problem is that you are conflating the binary operation with the reverse list constructor:

// 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]

If you're using function application as snoc then you can't use it for append as well:

snoc   :: [a] ->  a  -> [a]
append :: [a] -> [a] -> [a]

Notice that the types don't match, but even if they did you still don't want one operation to do two things.

What you want are difference lists.

A difference list is a function that takes a list and prepends another list to it. For example:

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.

The cool thing about difference lists are that they form a monoid because they are just 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

Even better, you can package them into a neat little class where function composition is the dot operator:

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

You can use the apply method to retrieve the value of the DList as follows:

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]

An advantage of using difference lists over regular lists (functional lists, not JavaScript arrays) is that concatenation is more efficient because the lists are concatenated from right to left. Hence, it doesn't copy the same values over and over again if you're concatenating multiple lists.

Answer 2

mirror test

To make L self-aware we have to somehow tag the values it creates. This is a generic trait and we can encode it using a pair of functions. We set an expectation of the behavior –

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

Below we implement is and tag. We want to design them such that we can put in any value and we can reliably determine the value's tag at a later time. We make exceptions for null and 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
  )

We now have a function Foo which is capable of distinguishing values it produced. Foo becomes self-aware –

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 of higher consciousness

Using is and tag we can make List self-aware. If given an input of a List-tagged value, List can respond per your design specification.

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) 
}

We try it out using your test data –

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 ]
  )

It's worth comparing this implementation to the last one –

// 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)
}

In our revision, a new branch is added for is (L, x) that defines the new monoidal behavior. And most importantly, any returned value in wrapped in tag (L, ...) so that it can later be identified as an L-tagged value. The other change is the explicit use of a None symbol; additional remarks on this have been added a the end of this post.

equality of L values

To determine equality of L(x) and L(y) we are faced with another problem. Compound data in JavaScript are represented with Objects which cannot be simply compared with the === operator

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

We can write an equality function for L, perhaps called 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
  )

But I won't go into how to do that in this post. If you're interested, I covered that topic in this Q&A.

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

tagging in depth

The tagging technique I used here is one I use in other answers. It is accompanied by a more extensive example here.

other remarks

Don't use !x to test for an empty value because it will return true for any "falsy" x. For example, if you wanted to make a list of L (1) (0) (3) ... It will stop after 1 because !0 is true. Falsy values include 0, "" (empty string), null, undefined, NaN, and of course false itself. It's for this reason we use an explicit None symbol to more precisely identify when the list terminates. All other inputs are appended to the internal array.

And don't rely on hacks like JSON.stringify to test for object equality. Structural traversal is absolutely required.

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!

For advice on how to solve this problem, see this Q&A