Template Haskell, argument munging and operads, part I

[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!

Argmunging in Arc

By the way, here's what an argmunger looks like in Arc:

(def argmunge (munger victim) (fn args (apply victim (map args munger))))

It's used like so:

arc> ((argmunge '(1 0) cons) 'x 'y)
(y . x)
arc> ((argmunge '(2 3 1 1 0 3 2) list) 'a 'b 'c 'd 'e 'f 'g)
(c d b b a d c)

That took a couple of minutes to write, and worked first time. Sw33t! Though I thought I'd got it wrong at first, as there was a bug in my test code :-) Note, by the way, that I'm mapping one list over another, to get the moral equivalent of Perl's list-slicing: this is a spin-off of the way that Arc treats function calls and data-structure indexing as indistinguishable. I'd hoped that I could write an argmunger that could be handed either a list or a function as its munger and Do The Right Thing, but unfortunately I don't think there's any way of determining the domain of an Arc function (the equivalent of the list's length) automatically.

I've changed the method signature so the munger is the first argument: that's because (argmunge m1 (argmunge m2 f)) is equal to (argmunge m1:m2 f). It's usual in operad theory to have the munging functions acting on the right: this is because they usually only consider munging functions which are invertible (ie, permutations), and use the definition (sticking with Lisp notation):

((argmunge' f m) x(m 0) x(m 1) ...) = (f x0 x1 ...)

So (argmunge' f m) is equal to (argmunge m^-1 f). With this definition (which is fine if you only allow permutations) then (argmunge' (argmunge' f m1) m2) is equal to (argmunge' f m1:m2), so it makes more sense for the arguments to be that way round. But when you allow your munging function to be noninvertible, you have to use the definition I gave, and then it makes more sense to have the mungers acting on the left.