Beware of the Train

[The hope was that this post would come in three somewhat independent sections: one pure programming, in which we develop a small utility in Template Haskell; one largely mathematics, at the upper-level high school to beginning undergraduate level, wherein we describe another approach to constructing our utility; and one purely mathematical, more sophisticated but fairly handwavy, wherein I relate all this stuff to my research interests and describe where it leads. The idea was that you could skip the code and jump to the maths, or read the code and skip the maths, or whatever. However, just the first section has now taken far longer than I'd budgeted, both in time and in space, so I'll save the other two for a later post.]

In a recent post, Hitesh Jasani writes about Haskell's flip operator, which takes a function f and returns a function which behaves like f with the order of its first two arguments reversed. So (flip f) x y z w = f y x z w (we write function application without brackets, as is customary in Haskell). I pointed out to Hitesh that actually, we could write such a function in almost any language which supports higher-order functions, and in dynamic languages (like Perl or Lisp) we can go further, and write a function argmunge, which accepts two functions and permutes the arguments of the first one (the "victim") according to the second (the "munger"). So

(argmunge f g) x1 x2 x3 x4 ... = f xg 1 xg 2 xg 3 xg 4  ...

Here's an implementation of argmunge in Perl, and some code to exercise it:

sub argmunge {
    my $func = shift;
    my $munger = shift; # not necessarily a permutation
    return sub { $func->(@_[@$munger]); }
}

sub myprint {
    print "Called with args ".join(", ", @_)."\n";
}

argmunge(\&myprint, [2,5,5,6])->(0,1,2,3,4,5,6);
argmunge(\&myprint, [3,2,1])->("fred", "barney", "betty", "wilma");

When run, this displays

Called with args 2, 5, 5, 6
Called with args wilma, betty, barney

Here we don't pass the munger in as a function, but rather as a list of values [g(0), g(1), ..., g(n)]. I'm prouder of that code than I probably should be, because it relies on some nice Perl features to work as it does; namely, Perl's argument-passing convention (in which all arguments are passed to a function as a single array called @_), list slicing (in which you can index into a list with another list), and list flattening (in which inclusion of one list in another splices the inner list into the outer list, resulting in a flat list). I remarked that it wouldn't be possible to write a general argmunger in Haskell, because the type of the result depends crucially on the actual value of the munging function. It ought to be possible to write one in a dependently-typed language like Cayenne - anyone care to do so?

[Edit: it's possible to write an even nicer version in Arc.]

Anyway, it may not be possible in vanilla Haskell, but ( it is possible using templates. )

The final code can be found here. As always, all suggestions for how I could improve my code or my development practices are gratefully received!