Define map in the fewest tokens

0

map is a very basic yet important function in functional programming.

All FP programming languages have it built-in but it is always fun to see how shortly you can define it yourself.

This will be scored in AST nodes, not bytes.

A token is the second-smallest building block of a program, over characters.

A token is:

anything that would be a distinct node if you drew a tree representing the source code

This scoring gives no benefit to single letter AST nodes names, and values succinctness as Paul Graham likes (this definition of AST nodes is his).

Haskell has this super cool definition:

zipWith ($) . repeat

And my lisp-ish AST of it (not required in your answer, just to show it visually)

   Apply (Apply (Var ".") (Apply (Var "zipWith") (Var "$"))) (Var "repeat")

That is 7 tokens. (Var x counts as 1)

I did not write it, so I do not post it as an answer.

Example:

(zipWith ($) . repeat) (* 3) [1, 2, 3] -- [3, 6, 9]

map should be defined as a (named or unnamed) function taking two arguments, the function and the list.

May the most AST nodes-succint code win!

Caridorc

Posted 2015-11-23T18:26:57.710

Reputation: 2 254

Question was closed 2015-11-24T02:36:45.983

5exec "blah blah blah" <- 2 tokens, right? – feersum – 2015-11-23T18:31:00.147

@feersum nice loophole, but if you write code in a string, than you should count the tokens inside the string. Otherwise everything would be written in 2 tokens :) – Caridorc – 2015-11-23T18:32:17.430

@feersum or I may disable exec in general as it is just a cheap way to circle around the rules... – Caridorc – 2015-11-23T18:36:32.463

Should the map be in-place, or should it return a new array? – Doorknob – 2015-11-23T18:36:37.100

@Doorknob mutability is not allowed in FP. Return a new array – Caridorc – 2015-11-23T18:37:01.517

3I'm voting to close as unclear because tokens are not precisely defined. – feersum – 2015-11-23T18:38:07.930

How should the map be implemented? As a function with two arguments, an array and another function? Or can it just assume that the variable names of the array and the function will be constant? – Doorknob – 2015-11-23T18:38:52.607

@feersum true, I should have used the sandbox... I will try my best to define a token – Caridorc – 2015-11-23T18:39:26.523

@Doorknob function with two arguments – Caridorc – 2015-11-23T18:40:00.547

@feersum defined a token – Caridorc – 2015-11-23T18:46:12.867

1I don't think your definition really clears things up. If I drew an AST of your source code, it would have "apply" nodes which don't correspond to tokens of the source. – Peter Taylor – 2015-11-23T19:03:56.940

@PeterTaylor i am not good at doing AST so probably your tree is correct and mine is wrong. – Caridorc – 2015-11-23T19:04:56.767

@PeterTaylor in fact I suspec that [Space] should also be a token – Caridorc – 2015-11-23T19:05:23.797

@PeterTaylor wonderful people on #haskell freenode gave me good info on AST – Caridorc – 2015-11-23T19:34:06.010

@PeterTaylor The correct tree is: Apply (Apply (Var ".") (Apply (Var "zipWith") (Var "$"))) (Var "repeat") where Var x counts as 1 – Caridorc – 2015-11-23T19:34:43.683

3I'd love to see a meta post about this "tokens" concept, to clear this all up before it's used in challenges. – Sparr – 2015-11-23T20:29:50.033

@Sparr I think just saying AST nodes instead of tokens should clear it up – Caridorc – 2015-11-23T20:36:36.863

I chose to define map as map. Bam, 1 AST node. ;) – Morgan Thrapp – 2015-11-23T21:53:33.457

1@MorganThrapp maybe, just maybe if a challenge is implementing x, saying x = builtin_x is a loophole ;) – Caridorc – 2015-11-23T21:55:22.437

2@Caridorc Define a "builtin map". For example, would the Python list comprehension answer be valid? – LegionMammal978 – 2015-11-23T22:45:05.990

@LegionMammal978 I would think so. It does the full workload of creating a new list, calling the transformation function for each item in the given list, and appending each resulting item to the new list. What more could you want from a self-contained map() implementation? – Blacklight Shining – 2015-11-24T05:13:09.253

@BlacklightShining The thing is, thee user doesn't do that, Python does it. – LegionMammal978 – 2015-11-24T11:54:31.053

@LegionMammal978: In the same way that Python creates a list when foo_list = [] is executed? – Blacklight Shining – 2015-11-27T18:03:01.637

@BlacklightShining In that case, the user "does the full workload of" defining the 0 elements of []. – LegionMammal978 – 2015-11-27T18:34:56.193

@LegionMammal978 How do we decide where the line is, then? I'm inclined to accept the list-comprehension answer, given that it's syntactic sugar for creating a new list, etc, etc. – Blacklight Shining – 2015-11-30T03:43:52.733

1@BlacklightShining Let the OP decide. – LegionMammal978 – 2015-11-30T11:25:34.720

Answers

2

Mathematica, 36 11 nodes

Thread@#@#2&

The FullForm of this program is:

Function[Thread[Slot[1][Slot[2]]]]

which has 4 symbols, 2 numbers, and 5 function applications.

LegionMammal978

Posted 2015-11-23T18:26:57.710

Reputation: 15 731

1

Python 3, 19 nodes.

lambda f, x: [f(y) for y in x]

Fairly self-explanatory. Applies f to each element of x and then returns the resulting list.

Interestingly, this code also uses only 19 AST nodes:

def map(f, x):
    for y in x:
        yield f(y)

I'm not totally sure if I'm counting the nodes correctly, because this is the first time I've worked with an AST. But this is what I used to count:

import ast
code = '''
lambda f, x: [f(y) for y in x]
'''
print sum(1 for node in ast.walk(ast.parse(code)))

Morgan Thrapp

Posted 2015-11-23T18:26:57.710

Reputation: 3 574

Wouldn't this be considered a builtin map? [a(b) for b in c] is the same as map(a, c). – LegionMammal978 – 2015-11-23T21:47:08.293

1@LegionMammal978 Same as zipwith is a builtin map, but that was the OP's example. – isaacg – 2015-11-23T21:47:39.213

1@LegionMammal978 Sure, but anything that emulates map is going to be the same as calling map. Plus, the challenge technically never disallows the usage of map as a builtin. ;) – Morgan Thrapp – 2015-11-23T21:47:56.953

@MorganThrapp "you can define it yourself." – LegionMammal978 – 2015-11-23T21:49:17.143

@LegionMammal978 I guess so, but there's nothing saying I can't just define it myself as map = map. – Morgan Thrapp – 2015-11-23T21:50:05.230

1Using the built-in AST is surely the best way of counting – Caridorc – 2015-11-23T22:03:28.020

0

Haskell, 11(?) nodes

flip foldr ([]).((:).)

Not sure about the node count (6 symbols plus 5 function applications?).

nimi

Posted 2015-11-23T18:26:57.710

Reputation: 34 639

Counting nodes is indeed hard. This is why AST-based scoring is so rare – Caridorc – 2015-11-23T22:09:22.063