n01senet

An array of functions.

Write a function (in your favorite language) that takes an integer and returns an array of that length, where each item in the array is a function that returns its own index in the array.

I proposed the above as a challenge for some friends, and got a few nice responses.

bash

The first answer was in bash by agriffis. After some adjustments, he settled on:

makearray() {
  declare x arr=$1
  eval "$arr=()"
  for ((x=0;x<$2;x++)); do
    eval "${arr}_func_$x() { echo $x; }; $arr[x]=${arr}_func_$x"
  done
}

To use it, pass in an array name and your desired array size:

makearray myarray 10

This is a bit of a cheat in that it actually creates an array of function names, not functions or closures. But it's bash, so you should be impressed it's even vaguely possible. To call the function at index 3:

${myarray[3]}

...and that echoes 3 to stdout, just as it should.

Python

Brett wrote a couple solutions in Python, settling on:

lambda x : map(lambda y : lambda : y, range(x))

This is pretty compact, so let's replace a couple of the lambdas with named function definitions:

def makefunc( y ):
  return (lambda : y)

def makearray( x ):
  return map( makefunc, range(x) )

This does exactly the same thing as Brett's original solution, but takes up more space doing it. range(x) gives us a sequence of integers, each of which is their own index. So now all we need to do is convert each of those integers into a function. map() helps us do this by passing each of the integers to makefunc, and returning an array of the results.

So makefunc's job is to take an integer y and return a function. The lambda in makefunc has nothing to the left of its colon (:), so the returned function needs no arguments.

my_array = makearray( 10 )
one_of_the_funcs = my_array[ 3 ]
one_of_the_funcs()  # returns 3

Or you can pack it all back together:

(lambda x : map(lambda y : lambda : y, range(x)))( 10 )[ 3 ]()

JavaScript

I originally thought of this challenge as a way to test someone's skill with JavaScript, so I thought I'd better write a JavaScript solution:

function makearray(x) {
  function makefunc(y) {
    return function(){ return y; }
  }

  var a=[];
  for( var i = 0; i < x; ++i ) {
    a[i] = makefunc(i);
  }
  return a;
}

This is a lot like the longer Python solution, but there's no special lambda syntax, so I have to use the "function" and "return" keywords everywhere. Also you can't generally rely on there being a map function, so I have a for-loop that looks a lot like agriffis' bash solution.

There's no particular benefit to putting the makefunc definition inside makearray, except that it hides that name so nothing outside makearray can call it. The syntax for using it is actually identical to Python's:

makearray(10)[3]()

Watch out, though, because JavaScript makes it easy to do closures incorrectly. It might seem like we don't need makefunc at all, and that this would work:

function makebadarray(x) {
  var a=[];
  for( var i = 0; i < x; ++i ) {
    a[i] = function(){ return i; } // not what you want
  }
  return a;
}

The problem with this is that all of the functions in the array will be referring to the same variable i, whose final value is 10. So although we'll have 10 different functions, they'll all return the same value:

makebadarray(10)[3](); // returns 10 (not 3)

Perl

I first heard about closures while learning Perl, so it's only polite to include it:

sub makearray{ map { my $y = $_; sub{$y} } (0..$_[0]-1) }

Perl's map acts just like Python's, but it has special syntax so you can just say "map {...}" instead of "map( lambda y : ... )". Unfortunately, instead of naming your own variable, the special $_ variable is set to each element of your sequence in turn.

sub{$y} in Perl means the same thing as (lambda : y) in Python.

Oh, and you don't get to name your function parameters either, so makearray's first parameter is called $_[0]. We pass this to the .. operator which is like the range() function (in this case).

The syntax for using this is not identical to Python's:

&{(makearray(10))[3]}

Clojure

I'm on a Clojure kick these days, so of course I had to write:

(defn makearray [x] (map #(fn [] %) (range x)))

The elements here should all be familiar from the Python solution, except the very compact syntax #(fn [] %) which is just a shortcut for (fn [y] (fn [] y)).

A quick aside: It is tempting to say (fn [y] #(y)), but #(y) is a function that executes the value of y instead of simply returning it.

Anyway, a more important detail is that this Clojure makearray doesn't actually return an array. All the previous solutions we've looked at create all ten functions, regardless of which ones we end up calling. In contrast, the Clojure makearray returns a lazy sequence, and doesn't create any functions at all until they're accessed.

So our standard usage:

((nth (makearray 10) 3))

...returns 3 just as the others did, but it only had to create the functions up through the one we asked for.

One practical way to take advantage of this is to change makearray to no longer take an argument, and instead allow it to generate an un-ending series of functions. To do this we simply replace the bounded (range x) with (iterate inc 0). Let's also call the function makeseq since that's more accurate:

(defn makeseq [] (map #(fn [] %) (iterate inc 0)))

Now call it:

((nth (makeseq) 99))

...returns 99, and since no more functions are required (by nth in this case), no more work is done.

Just to drive this home, realize that since makeseq takes no arguments, it's returning an equivalent sequence every time. This means it doesn't need to be a function at all:

(def myseq (map #(fn [] %) (iterate inc 0)))

This sets myseq to the potentially infinite sequence, but at this point none of the functions have actually been created yet. The functions are created on demand:

((nth myseq 25))  ; returns 25
((first myseq))   ; returns 0
(second myseq)    ; returns a function that, when
                  ; called, will return 1

So how would you complete this challenge in your favorite language?

 
A community blog by the members of n01se.net

ARCHIVES
May 2006 / June 2006 / July 2006 / October 2006 / February 2007 / May 2007 / July 2007 / February 2008 / March 2008 / May 2008 /


Powered by Blogger