[a,b].reduce(f,x) code to [a,b].reduce(f) using transducer /CPS based functional references?

Question

In my previous Quesion:

Extracting data from a function chain without arrays

@Aadit M Shah gave me astonishing solution as follows:

https://mcmap.net/q/1782035/-extracting-data-from-a-function-chain-without-arrays

Given an expression like A(a)(b)(f) where f is a function, it's impossible to know whether f is supposed to be added to the list or whether it's the reducing function. Hence, I'm going to describe how to write expressions like A(a)(b)(f, x) which is equivalent to [a, b].reduce(f, x). This allows us to distinguish when the list ends depending upon how many arguments you provide:

const L = g => function (x, a) {
    switch (arguments.length) {
    case 1: return L(k => g((f, a) => k(f, f(a, x))));
    case 2: return g((f, a) => a)(x, a);
    }
};

const A = L(x => x);

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]

It works due to continuations. Every time we add a new element, we accumulate a CPS function. Each CPS function calls the previous CPS function, thereby creating a CPS function chain. When we give this CPS function chain a base function, it unrolls the chain and allows us to reduce it. It's the same idea behind transducers and lenses.

There are 2 issues remained for me.

1. To distinguish reducing function, I consider some custom Typing mechanism using reflection, but in order to focus on this issue, so far I would like to simply apply

   const isReducer = f => (typeof f === 'function');

2. Requirement to provide an initial value has a limit to fold/reduce, for instance, it's impossible to provide an initial value for binary operations to the reduce such as

   const head = (a, b) => a; const tail = (a, b) => b;

(unless you provide the first/last value manually that makes no sense to run the code) In theory, every binary operations has a identity value, but something is impossible to provide as it is. The only way is to abstract as an identity.

Having said that, I can not refactor the provided code to single arguments and by a reducer type of the function, and the default value as the initial value of the sequence.

Can you provide the refactored code? Also any information of transducer/ CPS for this example is appreciated.

Calgary

"it's impossible to provide an initial value for binary operations such as head and tail" - those are not valid binary operations to reduce anyway, as their types do not fit. Please stop abusing function types as data structures and you'll see why. – Williwaw

I think you are mistaken, because "type" is provided by the binary operation itself, and (a,b)=> a or (a,b)=> b IS binary operation. If you insist not, please give us some reference. – Calgary

@Williwaw If a binary operation is not associative, it's not valid to reduce, but head and tail is associative, therefore they are valid operators to reuduce – Calgary

I don't understand what head and tail are supposed to mean. Typically you would associate them with lists, where they have the types list<a> -> a and list<a> -> list<a>, which are not binary operations at all. – Williwaw

@Williwaw As written above : head = (a,b)=> a and tail = (a,b)=> b. In fact this is well-known binary operators of Monoids reducer. I will give you a sample in my answer here. – Antitrust

@KenOKABE I think you mean head and last. When you said tail it confused both Bergi and me because the tail of a list is everything but the first element. – Detribalize

@AaditMShah Oh, right, Excuse me for my misuse for the term. Yes, it's last. – Antitrust

Answer 1

When you don't provide an initial value, you lose a lot of power. For example, you won't be able to convert the list into an array. This is because the return type has to match the type of the elements of the list. Consider:

foldl :: (b -> a -> b) -> b -> [a] -> b
foldl f a []     = a
foldl f a (x:xs) = foldl f (f a x) xs

foldl1 :: (a -> a -> a) -> [a] -> a
foldl1 f (x:xs) = foldl f x xs

As you can see, the return type of foldl can be any type b which is independent of the type a. However, the return type of foldl1 is forced to be a. Hence, if you have a list A(1)(2)(3)(4)(5) then when you fold this list the result would necessarily have to be a number.

You could get away with it by doing something like A(1)(2)(3)(4)(5)(concat2) where const concat2 = (x, y) => [].concat(x, y) because JavaScript is not a strongly typed language. However, it's not consistent because A([1,2,3])([4,5,6])([7,8,9])(concat2) evaluates to [1,2,3,4,5,6,7,8,9] instead of [[1,2,3],[4,5,6],[7,8,9]]. I don't see any way to convert the second list into an array while preserving its structure if you don't have an initial value.

---

Nevertheless, if you still want to do that then there's very little you'd have to change. Notice that foldl1 just delegates work to foldl. Hence, we just have to keep the first element of the list separate from the rest and use it as the initial value of the accumulator:

const L = g => a => x => typeof x !== "function" ?
    L((f, a) => f(g(f, a), x))(a) :
    g(x, a);

const A = L((f, a) => a);

const xs = A(1)(2)(3)(4)(5);

console.log(xs((x, y) => x + y)); // 15
console.log(xs((x, y) => x * y)); // 120

Finally, if you really want to learn about functional programming and continuations then I suggest that you read SICP (Structure and Interpretation of Computer Programs) or HtDP (How to Design Programs). HtDP is generally considered more beginner friendly. However, I strongly recommend reading SICP.

Detribalize

This is a great post by you as usual. I'm totally impressed, however, not giving an initial value is rather a proper approach I believe, that I can't agree and to prove it, I post my answer. – Antitrust