Lambda the Ultimate

What about the second version makes it clearer? I have some thoughts, but I want to see what other people think without influencing them.

Array.prototype.slice.call(arguments).reduce(...

This is gobbledygook to me. If I knew what each of those words meant, I'm sure it would be clearer, but I'm generally not a fan of this kind of functional style. You have to mentally model each sequence of words. I find it easier to model the comprehension I wrote above in one step rather than to piece together a bunch of higher-order incantations.

Well, its a real function from an application I was asked to help with, and I came up with the two possible implementations. If you allow the argument to be an array of arrays, rather than the arrays as a 'varargs' type function you can get rid of the Gobledygook. I will edit the original function definitions because I don't want this bit to get in the way of discussing the different styles.

What I want to understand is how people find the readability and understandability of the imperative vs the high-order functional style.

Javascript lends itself to the procedural style. Functional style is a poor fit to the language. In a lisp or some other naturally compositional language, it would be clearer in functional style.

Consider the inductive definition of a permutation: prepend one element of the list with the permutation of the rest of the elements of the list. Then translate induction to recursion, and you get:

;; remove one element from a list.  Used to remove the prepended 
;; element when deriving permutations.
(define (remove x lst)
  (cond
   ((null? lst) '())
   ((= x (car lst))(remove x (cdr lst)))
   (else (cons (car lst) (remove x (cdr lst))))))

;; return a list the permutations of lst. 
(define (permute lst)
  (cond
   ((= (length lst) 1)(list lst))
   (else (apply append
		(map(lambda (i) 
		      (map (lambda (j)(cons i j))
			   (permute (remove i lst))))lst)))))

As Lisp is untyped, lets use the term 'structure'. This has the same problem (for me) as the JavaScript functional version, it is not clear what the intermediate types/structures are. For example to know shape of the data structure returned from 'apply append (map (lambda i...)' I have to know the rest of the function, I have to work from the leaves of the AST upward holding the structure in my head. This makes it hard to understand what the code does, and it makes it even harder to just look at a fragment of code and know what it does.

The imperative version has the advantage that we establish the type of the mutable object to be an array of arrays '[[]]', and it remains that for the whole program fragment. Understanding the mutations on an object that remains the same type throughout seems easier for people than constructing the intermediate types as they parse the AST from the bottom up in their heads.

For me I like the elegance of the functional approach when I write it, but I don't like it when I have to read and understand other peoples code (or my own old code). Ironically for functional languages that have read-only data, the code itself seems to be write-only :-)

Is that what the relational cross product operator does? I would guess it to be symmetric, using a pair constructor instead of cons.

[a, b]*[c, d] = [(a,c), (a,d), (b,c), (b,d)] ≠ [a:c, a:d, b:c, b:d]

Well it joins two tables, in an extensible way so:

[(a, b), (c, d)] * [(1, 2), (3, 4)] = [(a, b, 1, 2), (a, b, 3, 4), (c, d, 1, 2), (c, d, 3, 4)]

So in a language like JS with no native tuples (or where tuples and arrays are the same thing, which might be a good idea). It obvously works just as well with tuples, the output being an array of tuples instead of an array of arrays.

[[a, b], [c, d]] * [[1, 2], [3, 4]] = [[a, b, 1, 2], [a, b, 3, 4], [c, d, 1, 2], [c, d, 3, 4]]

So it would have to assume the convention that a singleton tuple is just a value.

I am not sure if the distinction between list and tuple is meaningful in a dynamically typed language?

The closest I can get in JS is:

function cross(x, y) {
    var a = [];
    for (var i = 0; i < x.length; ++i) {
        for (var j = 0; j < y.length; ++j) {
            a.push(x[i].concat([y[j]]));
        }
    }
    return a;
}

function permutations3(xss) {
    return xss.reduce(cross, [[]]);
}

Hmm, good spot. Its only using concat because it creates a new Array for the result. I guess what is really needed is a push that returns a new copy. It was not my intention to rely on weak typing, so I would class this as a bug. I will fix the examples.

double post

I don't understand your tensor notation above or how the relational cross product is supposed to solve this problem. Could you elaborate? I can rewrite my solution as a fold like this:

perm = foldl (\yss xs -> [x:ys | x <- xs, ys <- yss]) [[]]

I don't see how that lambda corresponds to cross.

function cross(x, y) {
    var a = [];
    for (var i = 0; i < x.length; ++i) {
        for (var j = 0; j < y.length; ++j) {
            a.push(x[i].concat(y[j]));
        }
    }
    return a;
}

function permutations(xss) {
    var xsss = xss.map(function(xs) {
        return xs.map(function(x) {
            return [x];
        });
    });
    return xsss.reduce(cross, [[]]);
}

As for the tensor notation, now I think about it, I am probably abusing the mathematical notation too much, although there is probably something that could be done with some more thought.

I'm guessing this works because JavaScript is weakly promoting single values to arrays when you don't pass it an array. This will turn in to a bug when you want to find the permutations of arrays. No?

Because it wraps each value in another array, it is effectively doing:

a.concat([b])

which is the same as cons (apart from producing a fresh copy). 'permutations' does the wrapping before calling cross. Without the wrapping with '[]' it does produce incorrect results with permutations of arrays.

The alternative is to define this operation:

function op(x, y) {
    var a = [];
    for (var i = 0; i < x.length; ++i) {
        for (var j = 0; j < y.length; ++j) {
            a.push(x[i].concat([y[j]]));
        }
    }
    return a;
}

function perm(xss) {
    return xss.reduce(op, [[]]);
}

This isn't a cross product, it does exactly the same as the list comprehension now. I am not quite sure what it would be called?

Oh I missed that you're preprocessing the input to add the required [] wrapper before you call reduce. That takes away a bit from the elegance I think. We could define

pairwise :: (a -> b -> c) -> [a] -> [b] -> [c]
pairwise f xs ys = [f x y | x <- xs, y <- ys]

perm = foldl (pairwise (:)) [[]]

Which looks like it might work until you puzzle out that foldl takes its arguments the other way. Plumbing these functional contraptions together is a pain as soon as you're not pipe-lining single-parameter functions, which is most of why I dislike this style. I'd stick with something like the explicit recursion or maybe something like this:

def perm xss 
   var tot = [[]]
   for xs in xss
      tot = [x:ys | x <- xs, ys <- tot]
   return tot

This version works for me, and moving the discussion towards language design, I think I can see some general principles here:

- Keep types of object to a minimum, preferring to mutate an object of fixed type over creating intermediate objects of unknown type, or whose type depends on other types.
- Prefer non scoped blocks that do not capture values (for type blocks over lambdas)
- Prefer declarative value operations like list comprehension over loops or higher order functions where it is simpler (however I have seen people struggle with complex SQL queries, but are happy to write imperative code to do the same thing).

It is also tempting to not allow any free variables in function definitions, so that only local variables and arguments are allowed.

however I have seen people struggle with complex SQL queries, but are happy to write imperative code to do the same thing

SQL is not compositional, so I don't find this surprising at all. Composing LINQ queries is much easier for example, and complex LINQ queries aren't nearly as difficult as complex SQL queries (although LINQ could be better too).

SQL has two syntaxes for joins, the compositional one is:

(subquery...) join (subquery...) on ...

Right, so full SQL is not compositional, and it provides no means of query abstraction. Each of those subqueries should in principle permit local bindings:

DECLARE @tmp = (subquery...)
(subquery...) join @tmp on ...

Stored procedures are a kludge compared to proper query abstraction.

Well you can use 'as'?

(select ... as tmp) join tmp

Still even if it didn't support this, that would not make it non compositional. You can have compositional languages with no variables at all.

As far as I know there is no query that can be expressed using the non-compositional (relational calculus like) syntax that cannot be expressed in the compositional (relational algebra like) part.

I don't think this is the problem though. I think its that people lose track of the intermediate results. This is the same as the code examples above, the imperative reduces the intermediate results, minimises the different types (in this case the result row types).

I agree about error visibility. I think elegantly the left fold of the (relational) cross product is the clearest description:

function perm3(xss) {
    return xss.reduce(cross, [[]]);
}

The mathematical notation is nice, but it does depend on arbitrary convention. To formalise the notation so that it relies on only a small set of extensible syntax/semantics seems hard. A generic comprehension notation seems the best bet, and is similar.

The question is, as we have finite intelligence, when it comes to understanding complex algorithms and programs, are we able to cope with more complexity in imperative languages? Should a language designed to allow programmers to manage the highest levels of complexity therefore be an imperative language?