0
\$\begingroup\$

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;
};
\$\endgroup\$

closed as off-topic by cat, Martin Ender Apr 18 '16 at 15:59

  • This question does not appear to be about programming puzzles or code golf within the scope defined in the help center.
If this question can be reworded to fit the rules in the help center, please edit the question.

  • \$\begingroup\$ I sense malice in OP ;) developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/… \$\endgroup\$ – eithed Jul 15 '14 at 10:39
  • \$\begingroup\$ @eithedog I meant correct in that it doesn't screw up the array returned. I wasn't worried about type checking when I typed it up. ;) \$\endgroup\$ – Isiah Meadows Jul 15 '14 at 10:50
  • 1
    \$\begingroup\$ Does the function ALWAYS have to remove an element or can it be inconsistent in it's behavior? \$\endgroup\$ – Jordon Biondo Jul 15 '14 at 20:52
  • 1
    \$\begingroup\$ Maybe a #define true ((int)(random()*15)-15) could "fix" a few problems...fails 1/15 of the time... \$\endgroup\$ – Isiah Meadows Jul 16 '14 at 7:17
  • 1
    \$\begingroup\$ I'm voting to close this question as off-topic because underhanded challenges are no longer on-topic on this site. meta.codegolf.stackexchange.com/a/8326/20469 \$\endgroup\$ – cat Apr 18 '16 at 15:04

11 Answers 11

8
\$\begingroup\$

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?"

\$\endgroup\$
  • 12
    \$\begingroup\$ Perl itself looks cryptic to me. Even correct code is hard for me to understand. \$\endgroup\$ – Isiah Meadows Jul 15 '14 at 2:00
4
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Had similar idea (creating function nap on Array and iterating via for in, which would cause the length of output array to be increased by one) - unfortunately the prerequisite of The catch: introduce a hidden bug where the function is not applied to one entry of the input array foiled my plan :D \$\endgroup\$ – eithed Jul 16 '14 at 9:15
  • \$\begingroup\$ I loosened it up to "not correctly applied", requiring "at least one" instead of just one to be off, and the behavior being inconsistent (sometimes works), because that was how everyone interpreted the rules. Now, I won't make an exception for just adding one. The first part, "not correctly applied" means either it isn't applied or the output at that index is wrong. \$\endgroup\$ – Isiah Meadows Jul 16 '14 at 9:21
  • \$\begingroup\$ Cool! That opens up more possibilities to abuse JS! :x \$\endgroup\$ – eithed Jul 16 '14 at 9:27
  • \$\begingroup\$ @eithedog What do you think of mine? \$\endgroup\$ – Isiah Meadows Jul 16 '14 at 9:28
  • 1
    \$\begingroup\$ @eithedog As the Underhanded C Contest once said, the best underhanded code is clear, straight-forward, obvious, and wrong. \$\endgroup\$ – Isiah Meadows Jul 16 '14 at 9:48
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ This doesn't work for non-zero-based arrays, even if you fix the </<= bug, does it? outArray is a zero-based array, regardless of whether inArray is, and you use the same index i for both inArray and outArray. \$\endgroup\$ – hvd Aug 10 '14 at 13:25
3
\$\begingroup\$

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!

\$\endgroup\$
  • 3
    \$\begingroup\$ Lisp itself looks cryptic to me. Even correct code is hard for me to understand. \$\endgroup\$ – John Dvorak Jul 15 '14 at 3:07
  • \$\begingroup\$ @JanDvorak Did you copy my Perl comment? ;) \$\endgroup\$ – Isiah Meadows Jul 15 '14 at 4:26
  • \$\begingroup\$ @impinball I absolutely did. I hope you don't mind ;-) \$\endgroup\$ – John Dvorak Jul 15 '14 at 4:43
  • 1
    \$\begingroup\$ So would (defun xmap (l f) (when (car l) ... work? (note the car in place of the cdr.) \$\endgroup\$ – Alex Jul 15 '14 at 20:21
  • 2
    \$\begingroup\$ This has a typo: the recursive call to x-map does not match the function name xmap. \$\endgroup\$ – kernigh Jul 15 '14 at 20:44
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ The length method will never work in older IE, because the for-in loop. \$\endgroup\$ – Isiah Meadows Jul 16 '14 at 7:21
  • \$\begingroup\$ Does it have to be cross-browser compliant? I'd say this code being an abomination that shouldn't have been brought to this word, it's another perk! \$\endgroup\$ – eithed Jul 16 '14 at 8:07
  • \$\begingroup\$ Nope...even more underhandedness \$\endgroup\$ – Isiah Meadows Jul 16 '14 at 8:08
  • \$\begingroup\$ Could have been worse... A for-in loop with arrays are easy to screw up. \$\endgroup\$ – Isiah Meadows Jul 16 '14 at 9:09
0
\$\begingroup\$

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).

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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))]
\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.