4
\$\begingroup\$

G'day Just before I submit this to CFLib, it'd be great to get feedback:

<cfscript>
/**
* @hint CFML implementation of Array.reduce(), similar to Javascript's one ref https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/Reduce
* @array Array to reduce
* @callback Callback function to use to reduce. Will receive the following arguments: element (of current iteration of the all), index, array, (optional) result (of preceeding call to callback())
* @initialValue The initial value to use to start the reduction
*/

public any function arrayReduce(required array array, required any callback, any initialValue){
    var startIdx = 1;
    if (!structKeyExists(arguments, "initialValue")){
        if (arrayLen(array) > 0){
            var result = callback(array[1], 1, array);
            startIdx = 2;
        }else{
            return;
        }
    }else{
        var result = initialValue;
    }
    for (var i=startIdx; i <= arrayLen(array); i++){
        result = callback(array[i], i, array, result);
    }
    return result;
}    
</cfscript>

I've created proper unit tests as a gist.

\$\endgroup\$
4
\$\begingroup\$

Interesting discussion!

@AdamTuttle Regarding the behavior in Underscore that you've highlighted: I did some quick tests and found that the same behavior exists in Ruby and native JS (Chrome and FF). This confirmed my suspicions that this seemingly weird behavior is just a product of the reduce algorithm itself.

In the algorithm, "memo" represents the current state of the fold operation. If you don't pass in an initial value, you're implying that the first element of the collection represents the initial state of the fold. From that perspective, the behavior you've shown is exactly what I'd expect.

If you want to remove uppercase letters from a collection and convert that to a string in a functional way, it would make more sense to call filter() to and then reduce(). Example:

adamArr = ['A','d','a','m'];
damArr = _.filter(adamArr, function (letter) { 
    var asciiCode = asc(letter); 
    return asciiCode >= 97 && asciiCode <= 122;
};
damString = _.reduce(damArr, function (memo, letter) {
    return memo & letter;
};
|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ btw, I wanted to make this a reply to AdamT, but apparently I wrote too much for that. \$\endgroup\$ – Russ Jul 27 '13 at 6:11
  • \$\begingroup\$ Hi Russ. Seen in that light, your implementation of Underscore behaves the right way (in that it conforms with the precedent). However I still think THE PRECEDENT uses a poor & illogical approach. It makes no sense to treat the first element of the array in a "special" way the way it does. I think my approach here well be to just document the behavioural difference. Thoughts? If you want more discussion space, feel free to comment on my equivalent blog article instead: cfmlblog.adamcameron.me/2013/07/…. \$\endgroup\$ – Adam Cameron Jul 27 '13 at 17:06
  • \$\begingroup\$ I can see why you might feel that way about the precedent, but I still don't have a conceptual problem with it. It's not that the algorithm is treating the first value in a special way, it is that the algorithm assumes that, wherever you are in the list, the previous value (memo) is the combined result of all previous values. So when you call reduce without an initial value, you're actually starting the iteration at the 2nd position in the list. \$\endgroup\$ – Russ Jul 28 '13 at 16:08
  • \$\begingroup\$ "you're actually starting the iteration at the 2nd position in the list". Which is "treating the first element in the array in a special way": it's being treated differently from all the other elements in the array. I've had a look @ native JS & underscore & Ruby too, and agree that that is how they behave. It's still daft, and I'm still not having a bar of it ;-) \$\endgroup\$ – Adam Cameron Jul 31 '13 at 7:58
  • \$\begingroup\$ Ok, quote from Wikipedia: "The use of an initial value is necessary when the combining function f  is asymmetrical in its types, i.e. when the type of its result is different from the type of list's elements. Then an initial value must be used, with the same type as that of f‍ ‍'s result, for a linear chain of applications to be possible. " en.m.wikipedia.org/wiki/Fold_(higher-order_function) \$\endgroup\$ – Russ Aug 1 '13 at 6:18
2
\$\begingroup\$

I don't see any flaws in your logic... but...

I know you've basically just ported the referenced JavaScript example, but I'm not really fond of the implementation of initialValue.

Instead, have a look at UnderscoreCF's reduce method: (which was itself ported from UnderscoreJS)

/**
*   @header _.reduce(collection, iterator, memo, [context]) : any
*   @hint Also known as inject and foldl, reduce boils down a collection of values into a single value. Memo is the initial state of the reduction, and each successive step of it should be returned by iterator.
*   @example sum = _.reduce([1, 2, 3], function(memo, num){ return memo + num; }, 0);<br />=> 6
*/
public any function reduce(obj = this.obj, iterator = _.identity, memo, this = {}) {

    var outer = {};
    if (structKeyExists(arguments, "memo")) {
        outer.initial = memo;
    }
    _.each(arguments.obj, function(value, index, collection, this) {
        if (!structKeyExists(outer, "initial")) {
            memo = value;
            outer.initial = true;
        }
        else {
            memo = iterator(memo, value, index, this);
        }
    }, arguments.this);

    return memo;
}

Granted it does lean on the _.each method, so it can be a little difficult to wrap your head around. The important bit is:

You can omit the initialValue value and it will be correct no matter what data type is being reduced. Since you have a default value of an empty string, if you're working with numerics, you pretty much have to set an initial value.

On the other hand, the way UnderscoreCF's implementation works is that, if you've not specified a value for memo (initialValue) then it uses the first item in the array as the initial value, and skips the first iteration.

So let's look at two (somewhat contrived) examples:

//string concat
arrayReduce(['A','d','a','m'], function(memo, item){
    return memo & item;
});

This (above) will concatenate the characters together into a string. It would work via either implementation of reduce (yours or UnderscoreCF's).

//sum
arrayReduce([1,2,3,4], function(memo, item){
    return memo + item;
});

This one does a sum, similarly to your example, except that your implementation of reduce will (probably? I haven't tested to see what would happen...) choke because the callback is expecting numerics but memo is defaulted to an empty string for the first iteration.

Hopefully this is clear. It's a subtle difference.


In writing this answer I've thought of a potential bug in the Underscore implementation: What if you're concatenating a string but you only wanted to include lower-cased characters?

arrayReduce(['A','d','a','m'], function(memo, item){
    var asciiCode = asc(item);
    return memo & ( asciiCode >= 97 && asciiCode <= 122 ? item : '');
});

You would expect the result to be: dam but would probably get back Adam with UnderscoreCF's implementation. It would be easily mitigated by passing '' for the initialValue argument to reduce, but it is worth noting.

Food for thought! :)

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Cheers Adam, I've modified the code to get rid of the default initialValue, plus added some unit tests. If what you say about Underscore's handling of the initial value is true, that's just the wrong approach (and there's no way it can reasonably be construed to be right, I think). It shouldn't be the VALUE of the first element in the array, it should be the value of the result of the first callback call... and the callback should be dealing with the potentiality of there being no starting value. Examples of this in my unit tests. Thoughts? \$\endgroup\$ – Adam Cameron Jul 25 '13 at 19:20
  • \$\begingroup\$ I agree that it would be smarter for the first iteration to use the result of the callback as the memo going into the second (that is the bug I implied), but the fix brings us back to the issue of either requiring an initialValue, or setting a default which may be the wrong type, or requiring a param/default in the closure. None of those solutions is ideal, imo. \$\endgroup\$ – Adam Tuttle Jul 25 '13 at 20:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.