Implement map()...with bugs [closed]

Question

EDIT: The behavior may be inconsistent. Also, associative arrays are permitted.

Make a function that iterates through an indexed array, mapping a function of a single argument to each member of the array. The catch: introduce a hidden bug where the function is not correctly applied to at least one index of the input array.

Example:

map(lambda a: a+1, [1, 2, 3, 4])
# Should be [2, 3, 4, 5]
# Could be: [2, 3, 5, 4] or [2, 4, 6, 5] or anything else

Rules:

1. Use either a static method with two arguments, function and array, or a non-static method with one, an array or function (this being of the other type). Examples:

   • std::vector<F> map(F (*fn)(E), std::vector<E> array); (C++)
   • def map(fn, array): ... (Python)
   • Array.prototype.map = function (fn) {...}; (JavaScript)

2. If your language features a method already to do this, re-implement it.

3. The ignored entry may be of any type desired.

4. Assume the arguments to actually be correct (if the language has dynamic type checking).

5. It may or may not be in place.

6. Hide your malice.

7. Highest vote count wins.

Here's an example of a correct, bug-free implementation in JavaScript (excluding type checking):

Array.prototype.map = function (fn) {
  var i   = this.length,
  ret = new Array(i);
  while (i--) { // decrements to 0 after evaluation
    ret[i] = fn(this[i]);
  }
  return ret;
};

Answer 1

Perl

sub mymap (&@) {
  my $fn = shift;
  my @ret;
  while (my $val = shift) {
    local $_ = $_[0]; # map calling convention is element in $_
    push @ret, $fn->();
  }
  return @ret;
}

Looks plausible for at least a moment, until you have the sense to go "why isn't he using $val?"

Answer 2

Javascript

Let's use Object.defineProperty to define a lazy map function that only evaluates its result the first time it is requested.

function map(arr, f) {
    var result = {};
    for (var i = 0; i < arr.length; i++) {
        var value = arr[i], evaluated;
        Object.defineProperty(result, i, {
            get: function () {
                if (!evaluated) {
                    evaluated = f(value);
                }
                return evaluated;
            }
        });
    }
    result.length = arr.length;
    return result;
}

// Used like this    
var x = map([1, 2, 3], function (x) { return x + 1; });

The code has a pretty common error that often occurs when defining functions inside loops - since JS does not introduce a new context in a for loop, the variables i, value, and evaluated are the same for all the 'get' functions. This means that all elements in the result will be the same, namely f(arr[arr.length - 1]). Not very sneaky, but an interesting quirk of JS.

Addition:

Sneaky bug #2: if f(arr[arr.length - 1]) returns falsey, accessing an element in the array will apply f again! So sneaky I didn't realize it myself when writing up the sample.

Answer 3

I thought I'd try to take a stab at my own challenge here...please pardon my long spoilers.

JavaScript

It's a bit simplified compared to the spec (it requires type checking and this isn't necessarily an Array instance)

Array.prototype.map = function (fn) {
  var ret = [];
  for (var i in this) {
    ret.push(fn(i));
  }
  return ret;
};

Sounds great! Where's the problem?

It is widely known in the JavaScript world that the for-in loop returns the indices of arrays, not the entries. The confusion still brings headaches, even to some more seasoned developers. Also, in past versions of IE, for-in loops also iterated over additional properties, such as Array.prototype.toString. The proper way to fix this bug would be to use this[i] instead of i and append `if (this.hasOwnProperty(i)), so that it looks like this:

 Array.prototype.map = function(fn) {
   var ret = [];
   for (var i in this) {
     if (this.hasOwnProperty(i)) {
       ret.push(fn(this[i]));
     }
   }
   return ret;
 };
 

This looks correct now?

 

Try again. If there is any enumerable property ever assigned to the array, this loop will also see it and apply the function to it. That is relatively easy to do, considering the two standard means of setting properties default to being enumerable (which you can't change this way, either):

 object.prop = val;
 object['prop'] = val;
 

Keep in mind that you can assign a property to anything in JavaScript. If you were to try that "correct" implementation on a standards-comforming browser you would get this:

 var old = [1, 2, 3, 4, 5];
 old.foo = 'Hi!';
 var new = old.map(function (a) {return a + 1;});
 console.log('Old length: ' + old.length);
 console.log('New length: ' + new.length);
 console.log('Old contents: ' + old); // implicit toString
 console.log('New contents: ' + new);
 

 Output:
 Old length: 5
 New length: 6
 Old contents: 1,2,3,4,5
 New contents: 2,3,4,5,6,Hi!1
 

Also, there is no guarantee that the for-in loop iterates in order. The push() method implies the need to be in order. This could mean that the last line could very well print out the contents as 2,6,4,3,Hi!1,5.

The only way to define a non-enumerable property is through Object.defineProperty(), Object.defineProperties(), Object.create(), and the like.

Moral of the story, never use for-in loops to iterate through arrays. It's a code smell, and a terrible one at that. It leads to misunderstanding and bugs. It was clearly designed for associative arrays, not indexed ones. This should prove it. Always use the more standard for loop. Not only is it quicker, it is harder to screw up with. The for loop should have been:

 for (var i = this.length - 1; i > 0; i--) {
   ret[i] = this[i];
 }
 

Ironically, this could be done out of order.

Answer 4

C-sharp

So since this function will ship with a large library (really!), we'll have to keep it as generic as possible - it even works for non-zero based arrays (first entry)!

public U[] Map<T, U>(T[] inArray, Func<T, U> fn)
{
    U[] outArray = new U[inArray.Length];

    for (int i = inArray.GetLowerBound(0); i < inArray.GetUpperBound(0); i++)
        outArray[i] = fn(inArray[i]);

    return outArray;
}

So obviously the '<' in the for-loop should be '<='. An array with 2 elements has an upperbound of 1. The idea behind this trick is that everyone is used to writing 'i = 0; i < a.len', and will hopefully miss this detail at the first glance. The last entry in the outArray will remain zero.

Answer 5

Here's a nice broken recursive lisp function:

(defun xmap (l f) (when (cdr l) (cons (funcall f (car l)) (xmap (cdr l) f))))

(cdr l) will be NIL when l has one element, so the base case is a single-element list (in which the return value is nothing). Therefore, the output list is mapped from every element of the input list, except the last one.

This solution has the delightful property of being one letter different from a working function. Happy debugging with 3AM tired eyeballs!

Answer 6

C++

Let's have fun with some meta programming.

template <class ...Args>
struct Helper;

// base case for Helper
template <class F, class T>
struct Helper<F, T, std::tuple<>> {
    using type = std::tuple<T>;
};

template <class F, class T, class ...Args>
struct Helper<F, T, std::tuple<Args...>> {
    using t1 = typename F::template apply<T>;
    using type = std::tuple<t1, Args...>;
};

template <class F, class ...Args>
struct Map;

// base case for Map
template <class F>
struct Map<F, std::tuple<>> {
    using type = std::tuple<>;
};

template <class F, class T, class ...Args>
struct Map<F, std::tuple<T, Args...>> {
    using type = typename Helper<F, T, typename Map<F, typename std::tuple<Args...>>::type>::type;
};

Usage:

struct Func {
    template <class T>
    using apply = typename std::add_rvalue_reference<T>::type;
};

Map<Func, std::tuple<int, double , int const>>::type t;
// t suppose to have type std::tuple<int&&, double&&, int const&&>
// but it is std::tuple<int&&, double&&, int const>

The Map struct is a meta function that can apply another meta function to the types of a tuple, except the last member...

in Coliru

While the base case for Map is required to handle empty tuple, the base case for Helper isn't really helpful. Delete it will make everything working again.

Answer 7

PowerShell

I spent two hours trying to think of ways to be tricky with PowerShell, so I hope this isn't too easy to see through. Shouldn't be too hard to figure out what I did here.

function Map-Array($inArray, $functionName){
$outArray = $inArray.Clone()
$inArray.GetLowerBound(0)..($inArray.GetUpperBound($inArray.Rank-1)-1)|%{$outArray[$_-1] = & $functionName $([char]$inArray[$_-1])}
$outArray
}
function Black-Box($in){[char](([int]$in)-32)}
$x=@('a','b','c','d','e','f')

$y = Map-Array -inArray $x -functionName 'Black-Box'

Black-Box capitalizes all letters in the char array $x, anything else it just rolls back 32 spots on the ASCII table.

However...

-join $y
ABCDeF

Went a little overboard with my array index checking heh. Mainly because I like the fact that an index of -1 automatically points to the last element in the array in Powershell.

Answer 8

JS

_{(after a little editing, because first was second and second was first but now first is more... interesting)}

Let me borrow the OP's code, however due to our company's naming policy we need to change the name:

Array.prototype.array_map = function (fn) {
  var i   = this.length,
  ret = new Array(i);
  while (i--) { // decrements to 0 after evaluation
    ret[i] = fn(this[i]);
  }
  return ret;
};

var a = [1,2,3].array_map(function(x){ return x+1 });
console.log(a);

[2, 3, 4, array_map: function]

What's this rubbish?

The problem lies with definition of properties on objects. Array is an object in JS (or should I say Object). While map property is defined (or undefined if your browser is very old), JS has no problems with overwriting it and while the value of it will change (from one function to the other) the properties of this property won't (map isn't enumerable). Creating another method on Array.prototype by default defines this property as enumerable and as such is "accessible" (or - displays) like any other value of the array. Adding call to defineProperty solves this problem:

var a = [1,2,3].array_map(function(x){ return x+1 }); console.log(a);
[2, 3, 4, array_map: function]

Object.defineProperty(Array.prototype, "array_map", {enumerable : false});
var b = [1,2,3].array_map(function(x){ return x+1 }); console.log(b);
[2, 3, 4]

---

I always felt that there should be map on objects (associative arrays for you non-JS folks). As there's no such method in JS this code golf gave me the opportunity to write one.

First, let's define method length, as there's no such method in JS on objects as well (sheesh, JS, c'mon):

Object.prototype.length = function() { var size = 0; for (var key in this) size++; return size; }

Now, let's do this!

Object.prototype.map = function (f) { 
    var r=this;
    for (var i=0; i<this.length(); i++) 
        if (this[i]) 
            r[i] = f(this[i]);
    return r;
}

Seriously, I don't know why JS didn't have it before. Now, let's test it!

var a = {O: 1, 1: 2, 2: 3}; 
console.log(a, 1); 
console.log(a.map(function(x){ return x+1 }), 2);

Object {1: 2, 2: 3, O: 1, length: function, map: function} 1
Object {1: 3, 2: 4, O: 1, length: function, map: function} 2

Perfect!

I hope this didn't give too much headache to any of you JS developers out there. This code is riddled with problems - creating methods on Object (big no no), implementation of length (object doesn't actually have length, as methods on given object are part of the object - you can see that in the output itself; you can count the property indexes but this is not the way to do it), but the offending problem is actually a malice on my part - actually the O in the a objects isn't 0. While we're creating r as a copy of object, by iterating through it via for loop we're assigning values to all numeric elements, but r[0] isn't there.

Answer 9

Clojure

A simple, lazily evaluating map (basically a simplified version of Clojure's map).

(defn map' [f coll] (if (next coll) (lazy-seq (cons (f (first coll)) (map' f (rest coll))))))

(map' #(* % %) [0 1 2 3 4 5])
=> (0 1 4 9 16)

You would probably want to check if the collection is empty, without dropping one element from it. (next coll) returns nil if the collection has one element in it. Correct behaviour could be gained by using (seq coll).

Answer 10

PHP

function map($arr, $func){
    foreach($arr as &$x)
        $x = $func($x);

    $result = array();
    foreach($arr as $x)
        $result[] = $x;
    return $result;
}

This one is obvious to those who know PHP. $x is still a reference to the last item after the first loop.

Answer 11

Python

Um, since the question says "at least one":

ma = lambda m:[1]*len(m)

---

Slightly foolproofed:

def ma(p, f):
    return [0] + ma(p[1:],f) if m[0]==1 else [1] * len(m)

---

I know, I know, bring on the downvotes. Here's another:

ma = lambda m,f:[f(x) for x in range(len(p))]