The Map Puzzle

Here’s a fun programming puzzle.

In any language, define a function map that takes another function f and maps it over a list l. This means that map returns a new list where f has been applied to every element of l.

An example in Python:

def map(f, l):
    return [f(x) for x in l]

Here’s the catch: you can’t use any of your language’s iteration constructs, e.g. for, while, each, or obviously any built-in map. The above example is banned because of the for.

Sample solution:

def map(f, l):
    if len(l) == 0:
        return []
    return [f(l[0])] + map(f, l[1:])