[a,b].reduce(f,x) code to [a,b].reduce(f) using tr

问题:

In my previous Quesion:

Extracting data from a function chain without arrays

@Aadit M Shah gave me astonishing solution as follows:

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

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.

回答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.

回答2:

@Aadit M Shah

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.

I think this is not true. In fact, in algebra, Monoids definition does not require such an initial value.

To be precise, the initial value in programming is the Identity element which your own code provides.(see my code to clarify it).

The class is defined by the binary operator, and the binary operator has the full responsibility to match the return value to the same class.

Even for Array, concat operation can be refactored as below, and non-providing initial values even gives first last binary operations which you cannot write down as a concrete value, and your original code already provided the initial value, very propery as id: x => x!

//type system
const typedPrimitive = T => i => {
    const typeProperty = {
        enumerable: false,
        configurable: false,
        writable: false,
        value: true
    };
    const derived = Object(i);
    Object.setPrototypeOf(derived, Object(i));
    Object.defineProperty(derived, T, typeProperty);
    return derived;
};

const typedObject = T => i => {
    const handler = {
        get: (target, name) => name == T//must ==
            ? true : target[name]
    };
    return new Proxy(i, handler);
};

const typed = T => i => (i !== Object(i))//primitives
    ? typedPrimitive(T)(i)
    : typedObject(T)(i)

const istype = T => i => i[T] === true;

const Type = T => i => (i === T) || (i == null)
    ? i
    : typed(T)(i);

const isType = T => i => (i === T)
    ? true
    : (i == null)
        ? false
        : istype(T)(i);

const freeOp = f => Type(freeOp)(f);

//======================

const _L = g => a => b => isType(freeOp)(b)
    ? g((f, a) => a)(b, a)
    : _L(k => g((f, a) => k(f, f(a, b))))(a);

const id = x => x;
const L = _L(id);

const add = (x, y) => Number(x) + Number(y);
const multiply = (x, y) => Number(x) * Number(y);

const unit = (a) => [a];
const join = ([a]) => [].concat(a);
const flatUnit = a => join(unit(a));
const concat = (a, x) => flatUnit(a)
    .concat(x);

const addArray = (a, b) => {
    const aa = isType(addArray)(a)
        ? a : [a];
    return Type(addArray)([...aa, b]);
};

const concatStr = (a, x) => String(a) + String(x);

const max = (a, b) => (a > b) ? a : b;
const min = (a, b) => (a < b) ? a : b;

const first = (a, b) => a;//???
const last = (a, b) => b;

const io = (a, b) => {
    log("a:" + a);
    log("b:" + b);
    return b;
};

log(
    L(1)(2)(3)(4)(5)(freeOp(add))
); // 15
log(
    L(1)(2)(3)(4)(5)(freeOp(multiply))
); // 120
log(
    L(1)(2)(3)(4)(5)(freeOp(concatStr))
); // 12345
log(
    L(1)(2)(3)(4)(5)(freeOp(concat))
); // [ 1, 2, 3, 4, 5 ]
log(
    L([1, 2])([3, 4])([5, 6])([7, 8])([9])(freeOp(concat))
);
log(
    L([1, 2])([3, 4])([5, 6])([7, 8])([9])(freeOp(addArray))
); // [ [ 1, 2 ], [ 3, 4 ], [ 5, 6 ], [ 7, 8 ], [ 9 ] ]
log(
    L(1)(2)(3)(4)(5)(freeOp(max))
); // 5
log(
    L(1)(2)(3)(4)(5)(freeOp(min))
); // 1
log(
    L(1)(2)(3)(4)(5)(freeOp(first))
); // 1
log(
    L(1)(2)(3)(4)(5)(freeOp(last))
); // 5

log(//IO Monoid
    L(1)(2)(3)(4)(5)(freeOp(io))
); // 5


function log(m) {
    console.log((m)); //IO
    return m;
};

Note: Type mutates the original value, so to make it immutable this must be refactored to use Proxy/Reflection in ES6.