functional.txt

Functional is a JavaScript library for functional programming.  It
defines the standard higher-order functions (+map+, +reduce+,
+filter+) that you can read about elsewhere on the web.  It also
defines functions for <a href="http://en.wikipedia.org/wiki/Function-level_programming">function-<em>level</em></a> programming: partial function application (+curry+ and +partial+), +compose+, +guard+, and +until+.  Finally, it introduces "string lambdas", which let you write 'x -> x+1', 'x+1', or even '+1' as an
synonym for function(x) {return x+1}.

See the "example page":/sources/javascripts/functional.html
for the API documentation, more examples, and a link to the sources.

h4. String lambdas

Welcome to functional programming!  You've probably already discovered +map+ and +filter+.  (If not, spend a few minutes with Google.)  Try using them in JavaScript.  Isn't it a pain?
  map(function(x){return x+1}, [1,2,3])
    -> [2,3,4]
  filter(function(x){return x>2}, [1,2,3,4]]
    -> [3,4]
  some(function(w){return w.length < 3}, 'are there any short words?'.split(' '))
    ->false

String lambdas let you write these instead:
  map('x+1', [1,2,3])
  select('x>2', [1,2,3,4])
  some('_.length < 3', 'are there any short words?'.split(' '))

Some more examples, using just +map+, +filter+, and +reduce+:
  // double the items in a list
  map('_/2', [1,2,3])
    -> [2, 4, 6]
  // find the odd numbers
  filter('%2', [1,2,3,4])
    -> [1, 3]
  // or the evens
  filter(not('%2'), [1,2,3,4])
    -> [2, 4]
  // find the length of the longest word
  reduce(Math.max, 0, map('_.length', 'how long is the longest word?'.split(' ')))
    -> 7
  // parse a binary array
  reduce('2*x+y', 0, [1,0,1,0])
    -> 10
  // parse a (non-negative) decimal string
  reduce('x*10+y', 0, map('.charCodeAt(0)-48', '123'.split(/(?=.)/)))
    -> 123

h4. Function-level programming

Value-level programming manipulates values, transforming a sequence of inputs into an output.  "Function-level programming:"http://en.wikipedia.org/wiki/Function-level_programming manipulates functions, applying operations to functions to construct a new function.  It's this new function that transforms inputs into outputs.

Here are some examples of function-level programming with Functional.  There's more in the "docs":http://osteele.com/javascript/sources/functional.
  // apply '/' only to values that test true
  map(guard('1/'), [1,2,null,4])
    -> [1, 0.5, null, 0.25]
  // apply '10+' only to even values, leaving the odd ones alone
  map(guard('10+', not('%2')), [1,2,3,4])
    -> [1, 4, 3, 8]
  // write a version of map that only applies to the evens
  var even = not('%2');
  var mapEvens = map.prefilterAt(0, guard.rcurry(even));
  mapEvens('10+', [1,2,3,4])
  // find the first power of two that's greater than 100
  until('>100', '2*')(1)
    -> 128
  // or the first three-digit power of two (these are all the same)
  until('String(_).length>2', '2*')(1)
  until(compose('>2', pluck('length'), String), '2*')(1)
  until(sequence(String, pluck('length'), '>2'), '2*')(1)

h4. Partial function application

Partial function application, or specialization, creates a new
function out of an old one.  For example, given a division function:
  function div(a, b) {return a/b}
a partial application of +div+ is a new function that divides its argument by two:
  var halve = div.partial(_, 2);
Partial application is especially useful as an argument to the higher-order functions such as +map+, where, given a function +div+, we can apply it (the first line below) without an explicit wrapper (the second).
  map(div.partial(_, 10), [10, 20, 30])
  map(lambda(n) {return div(n, 10)}, [10, 20, 30])

+curry+ is a special case of partial function application, and the prevous example could have been handled via +curry+.  Partial function
application in all its generality is only necessary when you're
specializing not just on all the arguments on the left, or all the
arguments on the right, but some distribution of arguments with holes
in the middle.  To illustrate this requires a function with more than two
parameters.

JavaScript doesn't have many functions with more than two parameters. (+splice+ takes three, but +splice+ isn't very functional).  Here's a contrived example, to start (and a real-world example next).

We'll borrow one of the few trinary predicates from math: "between".  +increasing+ tests whether +b+ (the middle argument) lies in the open interval bounded by +a+ and +c+.  Specialize the first and last arguments to produce a functions that tests whether a number is positive, for example.

  function increasing(a, b, c) {
    return a < b && b < c;
  }
  var positive = increasing.partial(0, _, Infinity);
  map(positive, [-1, 0, 1])
    -> [false, false, true]
  var negative = increasing.partial(-Infinity, _, 0);
  map(negative, [-1, 0, 1]) 
    -> [true, false, false]

Here's how to use +compose+ and +curry+ to generalize some of the examples from the first section
into reusable functions.  You'll probaby like or hate these function definitions to the
extent that you like or hate Haskell.
  var longest = compose(reduce.curry(Math.max, 0), map.curry('_.length'), "_.split(' ')");
  longest("how long is the longest word?");
    -> 7
  longest("I bet floccinaucinihilipipification is longer.");
    -> 29
  var parseUnsignedInt = compose(reduce.curry('x*10+y.charCodeAt(0)-48', 0), '_.split(/(?=.)/)')
  parseUnsignedInt('123')
    -> 123

A real-world example:  This adds a +sum+ method to Array.  Note how the 'this' lambda, which is short for function()[return this}, moves the object from object position to argument position so that the curried reduce can apply to it.
  Array.prototype.sum = reduce.curry('+', 0).compose('this')
  [1,2,3].sum()
     -> 6

Another example:  If you're using Prototype, you can replace the first line below by the second:
  Event.observe('myobj', 'click', function() {...})
  onclick(''myobj', function() {...})
by defining a specialized version of Event.observe:
    var onclick = Event.observe.bind(Event).partial(_, 'click');

Is this better than the following?
  function onclick(element, handler) {
    Event.observe(elenent, 'click', handler);
  }

It's a matter of taste, with some performance considerations as well.  The function-level version is less efficient, and to the untrained eye it's also harder to read.

On the other hand, the functional version doesn't include as much
plumbing, with its attendent opportunity for error.  The second
definition  of +onclick+, considered as a general replacement for Event.observer(..., 'click', ...), has two such errors.  One shows up as soon as
you use it; the second is considerably more subtle.  Whether functional programming is appropriate, for reasons of efficiency or readability, in any particular instance, it's nice to have it, at lest for prototyping, in your arsenal.

h4. A Note on Performance

In most languages, including JavaScript, invoking a function is one of the slowest
things you can do.  The implementations of languages designed for functional programming
use a variety of techniques to optimize function calls.  JavaScript is not one of those languages.

Functional attempts to reduce the cost of higher-order-programming where doing so doesn't add to the code complexity or readability too much.  Each higher-order function and method is a small number of lines, and each function-returning method attempts to do as much work as possible outside the function that it returns, to optimize the case where the returned function is called more than once (as an argument to a higher-order function such as +map+, for example).

Still, using Functional is expensive.  Invoking a constructed function results in at least twice as many invocations as invoking the underlying function.  This isn't any different from using +bind+ in the Prototype library, say, but, the more of your program you write in a functional style --- and therefore the more method calls you introduce --- the slower it will be.  As with any library, be aware that you may have to hand-compile performance-critical sections of your code into an approximation of you would have written without the library anyway; if you think you already know what needs to be optimized (or that your whole program does), or you aren't comfortable with measuring performance periodically in order to intelligently trade execution time against implementation time, you may want to eschew libraries, especially higher-order ones.

h4. Compatibility

Functional is known to work in Firefox 2.0 and Safari 3.0.  I didn't intentionally use any non-standard ECMAScript constructs, but meta-programming such as this tends to turn up corners in the browser implementations.

String lambda use regular expressions and +eval+.  The rest of the code is free of above.  The intent of this separation is that the code might be portable to environments that don't support +eval+, such as Flash and mobile environments, or regular expressions, such as Flash and OpenLaszlo.  I haven't tested it against any of these environments, thoug, so I've kept the code in one file for now.

h4. Future Directions

Functional programming doesn't always mesh well with OO, especially with Javascript's absence of bound methods.  There are currently two sets of methods to partially apply a function: +bind+ binds its object (the first argument to +apply+); and [r][n]curry and +partial+ bind the other arguments (the arguments to +call+, which list is the second argument to +apply+).

One problem with this is the syntax.  If you want to specialize both the object and the parameters, such as in the example with Event.observe above, you need two chained function calls.  This is a tradeoff: it's because each of +bind+ and +partial+ does a single thing.  I considered adding a single omnibus function that bound everything, but it looked just as verbose, and more confusing, than the present solution.

The other problem is performance.  Invoking the function returned by fn.bind(a) goes through one extra function call beyond the cost of invoking fn().  That's unavoidable.  Invoking the function returned by fn.partial(b,c) also goes through one extra function call (as well as a loop and some conditionals to merge the argument lists).  That's unavoidable too.  But a call to the function returned by fn.bind(a).partial(b,c) or fn.partial(b,c).bind(a) goes through *two* extra function calls.  It only needs one.

Someday I'll publish fast-functional.js, which patches functional.js to fix this problem.  It modifies fn.bind(a).partial(b,c) and fn.partial(b,c).bind(a) to return a function that calls the underlying function directly, instead of trampolining once for each method in the chain.  Later I'll describe a generalization of this technique, for defining function algebras with combinatoric reductions.

h4. Credits

I bummed the +[].slice.call(arguments, 0)+ idiom from http://www.coryhudson.com/blog/2007/03/10/javascript-currying-redux, and used it all over the place to avoid an iteration or non-native function call.  The ECMAScript Language Specification is careful to define +slice+ in such a way that this works, but I don't think I would have thought of it.


Agenda:
- remove arg from map?
Blog:
- search for ***
- add iframe version
Later:
- S to compose an n-ary function
- filtering arguments: permutations, annihilators, prefilter
- something better for the oo bridge
- oo integration: bind, 'this'
- add jsmin version
- add +specialize+, same as partial but doesn't curry; "non-standard distinction"
- add prototype library
- string environments
OSDoc:
- add version number
- factor 'reporting'
- doc requirements

Generalized a+b*c, over its operators:
  ops(op1, op2, a, b, c) = a `op1` (b `op2` c)
var ap = curry.uncurry();
var ops = Function.S(ap.prefilterSlice('c op1 op2 a -> [op1, a, c]'), ap.prefilterSlice('op1 op2 a b c -> [op2,b,c]'))
ops('+','*',2,3,4)

Array.prototype.sum = reduce.curry('+', 0).compose('this')

map.rcurry(map(compose(ncurry('f(x)', 2).aritize(1), Function.toFunction), [invoke('toUpperCase'),'.length'])).compose('x -> f -> f(x)')(3)

var mapFunctions = map.rcurry(map(compose(ncurry('f(x)', 2).aritize(1), Function.toFunction), [invoke('toUpperCase'),'.length'])).compose('x -> f -> f(x)');

mapFunctions(['1+', '2+', '3+'], 1)

//Function.prototype.postfilter = Functional.sequence.curry;



postfilter = Functional.compose.curry.compose(Function.toFunction);

wrappedBy = function() {}

// install on proto Array each; Enumerable all any collect detect each find findAll
// grep: 2 inject 2, map min 2, partition reject select sortBy; 
//synonyms: Array.each Hash.each
'all any collect detect each find findAll map partition reject select sortBy grep[1] inject[1] min[1]'.each(function(name) {
  var index = 0;
  var parts = name.split(/\[\]/);
  if (parts) {name = parts[0]; index = parseInt(parts[1]]
  // excpet: they can be nulls
  if (typeof iterable[name] == 'function')
    Iterable[name] = wrapped(iterable[name]);
Function.toFunction.guard(Function.K)
  wrapped = Functonal.prefilterAt.rcurry(_, 0, Function.toFunction.rcurry(true));
}

Number.prototype.times = function(fn, receiver) {
    var limit = Math.max(0, this);
    for (var i = 0; i < limit; i++)
        fn.call(receiver, i);
}

// var oldRequest = Ajax.Request;
// Ajax.Request = (function() {
//     return function(url, options) {
//         info(arguments);
//         return oldRequest("functional-examples.js", arguments[1]);
//         return oldRequest.apply(Ajax, arguments);
//         if (options.onSuccess)
//             options.onSuccess = options.onSuccess.reporting();
//         return oldRequest.apply(this, url, [options].concat([].slice.call(arguments, 2)));
//     }
// })(Ajax.Request);

// 
// If +binding+ is supplied, it acts an environment for the new function.
// >> 'x -> x+a'.lambda({a:1})(2)
String.prototype.lambda = function(binding) {
    
    var body = 'return (' + expr + ')';
    alert(binding, new Function(params, body));
        with (binding)
            return new Function(params, body);


.bq [T]he aim of functional programming is to transform a program which
describes a problem into a program which describes a solution
-- "Claus Reinke":http://www.haskell.org/pipermail/haskell-cafe/2006-December/020147.html


, but "function-level".  It's in a style that has been called "point-free":http://haskell.org/haskellwiki/Pointfree (and even pointless:"http://haskell.org/haskellwiki/Pointfree#Problems_with_pointfree").

injection, projection, modification, and composition.  Injection lets you create a function when you don't have one.  In JavaScript, the +function+ keywords and the builtin functions.  Projection gets out of the function level; function application (to a value) does this.  Within the system, a function can be modified, and funcions can be composed.
Function-level programming rests on three pedestals: composition, control, specialization.  First, it must be possible to combine existing functions into new functions.  The higher-order functions (and methods) +compose+, +sequence+, and +filterAt+ do this; "adjectives" such as +uncurry+ and +flip+ modify functions so that they can be properly composed.  Second, there need to be control structures.  +map+ and +reduce+ are examples of control structures; more exotic examples are +guard+ and +until+.  Finally, it must be possible to create specialized functions out of general ones.  Partial function application, of which +curry+ is a special case, does this.

/**
 * Returns a function that has the same effect as this function, but returns
 * itself.  This is useless for pure-functional functions, but can be used
 * to make chainable methods in procedural/OO code.
 * == f.returning.apply(this, args...) == this, but with side effect of f()
 * Without +returning+:
 * >> var value = 1;
 * >> var object = {effector: function() {value += 1}};
 * >> object.effector() == object -> false
 * With +returning+:
 * >> object.effector.bind(object).returning() == object -> true
 * >> returning(object.effector.bind(object)) == object -> true
 * >> value -> 4
*/
Function.prototype.returning = function(/*args...*/) {
    var fn = this;
    return function() {
        fn.apply(this, arguments);
        return this;
    }
}


fix formatting problems: paragraphs, -&gt;
switch to jquery?
make jdoc work w/out prototype?


 * Note that `uncurry` is *not* the inverse of `curry`.