Hacker News Reader

Comment by ultimape | Hacker News Reader

For those not familiar with Clojure, here's a great demonstration of the concept done up in JavaScript: http://jlongster.com/Transducers.js--A-JavaScript-Library-fo...

View on HN

From that link:

"The reduce function is the base transformation; any other transformation can be expressed in terms of it (map, filter, etc)."

This seems so obvious in retrospect -- I can't believe I had never made that connection before.

I had a similar epiphany while learning about regular expressions in Perl. That connection with text processing is what helped me understand list comprehensions. They seem strikingly similar.

For JS, I personally prefer lo-dash for this kind of work, or dropping in polyfills from MDN.

For some context, here are .map functions applied to normal arrays http://jsperf.com/native-vs-array-js-vs-underscore/54

I've been looking for similar libraries that work on typed-arrays because they are so much more efficient when working with web-workers or with raw canvas data. My attempts at hacking it in feel like they are just bad ideas: http://jsperf.com/float32array-map/2

Most people use underscore/lodash for this stuff. The difference is that the js transducers libraries don't create intermediate arrays, only do enough work to produce the requested output, and work on top of anything that can be coerced into the iteration protocol. I've seen demos of using Facebook's Immutable JS, CSP.js [1], and I don't see why you couldn't put them on top of Typed Arrays or a FRP library like Kefir.

[1] http://jlongster.com/s/nationjs-slides/

Yeah, the overhead of creating intermediate typed arrays is exactly what I'm trying to avoid with this.

Lo-Dash 3.0 will have support for lazy evaluation in its chaining syntax that supports shortcut fusion and avoids intermediate arrays as well.

Do you know if they work with typed arrays?

For me the "ephiphany" was when I realized reduce don't need to be (T,T)->T, but can be (T1, T2) -> T1.

They can also be (T1,T2)->T3

Not really?

When you reduce with function f(T1, T2) -> T3 the result of previous iteration becomes first argument for the next iteration, so they must be of the same "type".

Or am I missing something?

Ah, no, you're right.

I was thinking that mapping can be f(T1)->T2 and how reducing can change types too, but I guess I wasn't paying enough attention because of course the reduce signature is f(accumulator, input) and the output is accumulator, so yea, you're absolutely right: f(T1,T2)->T1

Yeah. That's actually how you implement lists in lambda calculus, as opaque functions that accept a "visitor". There are two different ways of doing it:

    -- Mogensen-Scott encoding
    data ScottList a = ScottList (forall r. (a -> ScottList a -> r) -> r -> r)

    -- Boehm-Berarducci encoding
    data ChurchList a = ChurchList (forall r. (a -> r -> r) -> r -> r)

Roughly, the first encoding gives you pattern matching, and the second gives you foldr (reduce). Either of these operations is sufficient to do anything with the list.

Also note that both of these are encodings of lazy (potentially infinite) lists. To encode strict (guaranteed finite) lists, you really need algebraic data types like in ML, the visitor pattern can't do that.

Graham Hutton has a very nice tutorial [0] on the universality of fold, which shows this elegantly (in Haskell, though).

[0] Graham Hutton, "A tutorial on the universality and expressiveness of fold", J. Functional Programming 9(4): 355–372, July 1999. http://www.cs.nott.ac.uk/~gmh/fold.pdf

There is also Transducers Explained [1] if you are familiar with JavaScript.

(Shameless plug in the hope it may be helpful to someone)

[1]: http://simplectic.com/blog/2014/transducers-explained-1/

For JavaScripters, there's also the 'Like Underscore, but lazier' Lazy.js http://danieltao.com/lazy.js/

Reply on news.ycombinator.com