Your company is just getting started on a project, and for the first time you decided to go use a functional programming code-style. However your boss is really diffident and doesn't want to use built-in functions, and requires you to implement yourself the main functions. In particular you need to write the functions: Map, Nest, Apply, Range, Fold and Table in a language on your choice. The boss is a really busy man, and he wants to have the programs as short as possible, so he doesn't waste time reading. He also would like not for you to use loops, therefore you will have a 10% reduction on the byte count for not using loops.

The detailed requirements of the functions are below:


The Map function takes two parameters: f and list where f is a function and list is a list of values. It should return the f applied to each element of list. Therefore it will work as such:



{ f(a), f(b), f(c) }


Map(f, {{a,b},{b,c}})


{ f({a,b}), f({b,c})}


The Nest function takes three parameters as well: f, arg, times where f is a function, arg is its starting argument, and times is how many times the function is applied. It should return an expression with f applied times times to arg. Therefore it will work as such:

Nest(f, x, 3)




Nest(f, {a,b}, 3)




The Apply function takes two parameters: f and args where f is a function and args a list. It should apply f to the args. Therefore:

Apply(f, {a,b,c})




The Range function takes one integerr and outputs the integers up to that number. Therefore:



{ 1, 2, 3, 4, 5}


The Fold function takes three parameters f, arg, others where f is a function, arg is simple parameter, and others a list. It will work as such:

Fold(f, x, {a, b, c, d})




The table functions should take a function f, and a parameter called iterator in the form: {iMin, iMax} where iMin and iMax are integers. You should apply f over the range specified. Therefore:

Table(f, {0, 5})


{f(0), f(1), f(2), f(3), f(4), f(5)}

I've used the definition of these functions from the Mathematica functional programming page, so head there if you need any more guidance. Note that you will not need to implement all the version of the functions shown in that page, but only those written in this post.

Standard Loopholes are disallowed as usual.

In case your language does not allow functions to be passed as arguments, you need to implement this capability, and add it into your answer. However the byte-count of this operation will not be added to the total.

This is code golf so the shortest code wins. Good luck!!!

  • \$\begingroup\$ This is awesome! +1 However, I don't really get how Table works here. Is your example supposed to be Table(f, {x, 0, 5})? I also don't get the purpose of x at all, since it just applies the function to the range. \$\endgroup\$ Sep 24, 2015 at 14:05
  • \$\begingroup\$ @kirbyfan64sos Thank you! Yes that was a typo, I left x in as a reference to mathematica, which uses it as symbolic feauture, however I think I can get it out \$\endgroup\$ Sep 24, 2015 at 14:08
  • \$\begingroup\$ One more question: how do we name the functions? Do we have to give them the exact same names? Single-letter? \$\endgroup\$ Sep 24, 2015 at 14:15
  • \$\begingroup\$ @kirbyfan64sos Since it is code-golf, I'll allow single letter names, however in your answer put a heading over each function so that we know which one it is. Also do not use colliding letters. \$\endgroup\$ Sep 24, 2015 at 14:18
  • \$\begingroup\$ Could you be more specific about what counts as a loop? \$\endgroup\$
    – xnor
    Sep 24, 2015 at 17:59

11 Answers 11


Haskell, many previous byte counts 127 * 0.9 = 114.3 bytes

f#(a:b)=f a:f#b;f#x=x
r x=i%(1,x)
f%(a,b)|a>b=[]|1<2=f a:f%(a+1,b)

No loops, just recursion.

# is map: (*2) # [1,2,3] -> [2,4,6]

& is nest: ((*2) & 3) 4 -> 48

i is apply: i (*2) 7 -> 14

r is range: r 4 -> [1,2,3,4]

? is fold: ((+) ? 0) [1,2,3,4] -> 10

% is table: (*2) % (2,4) -> [4,6,8]

As requested an ungolfed version with comments. Note, & and ? are ternary infix operators, which require additional parentheses when called or pattern matched.

f # (a:b) = f a : f#b        -- map on a list (a->head, b->tail) is f a in front of mapping f to b
f # x     = x                -- map on the empty list is the empty list
                             -- (non empty lists are caught in the line before) 

(f & x) 0 = x                -- nesting zero times is x
(f & x) i = f $ f&x $ i-1    -- nesting i times is f (nesting one time less)

i=id                         -- apply in Haskell is just the identity function 

r x = i % (1,x)              -- defined via the "table" of the identity function from 1 to x

(g ? x) (a:b) = g (g?x$b) a  -- folding g into a list (a->head, b->tail) is g applied to (folding g into b) and a
(g ? x) y     = x             -- folding the empty list is x
                             --  again, y must be the empty list, else it would have been handled by the previous line

f % (a,b)                    
  |a>b       = []                -- if iMin is greater than iMax, the table is empty
  |otherwise = f a : f%(a+1,b)   --  otherwise f a in front of the table with iMin increased by one

Thanks to @dfeuer and @Zgarb for some useful hints

  • \$\begingroup\$ I'm new to haskell, it looks quite good, however could you please add an explanation to what you are doing? \$\endgroup\$ Sep 24, 2015 at 17:46
  • 1
    \$\begingroup\$ @WizardOfMenlo: added some comments \$\endgroup\$
    – nimi
    Sep 24, 2015 at 18:00
  • 1
    \$\begingroup\$ Just realized how elegant Haskell is, real good! \$\endgroup\$ Sep 24, 2015 at 18:10
  • 1
    \$\begingroup\$ Ignoring infinite lists and efficiency, m#q=reverse$f((:).m)[]q. This is the same length as yours, but much harder to read. \$\endgroup\$
    – dfeuer
    Sep 24, 2015 at 18:21
  • \$\begingroup\$ You can shorten ! by making it a name instead of an operator: i f=f. \$\endgroup\$
    – dfeuer
    Sep 24, 2015 at 18:36

Python 2, 305.1 bytes (-10% 376 369 366 349 339 bytes)

exec'e=eval;q=len;m=@,l:e("["+"f(l.pop()),"*q(l)+"][::-1]");n=@,x,l:e("f("*l+"*x"+")"*l);r=@:e("r(f-1)+"*(f>1)+"[f]");a=@,a:e("f(a["+`r(q(a))`[1:-1]$",","-1],a[")+"-1])");f=@,x,l:e("f("*q(l)+"x,["+`r(q(l))`[1:-1]$",","-1]),l[")+"-1])");t=@,n,x:e("[f("+`r(x)[n-1:]`$",","),f(")[1:-1]+")]")'.replace("@","lambda f").replace("$",".replace(")

When expanded, equivalent to:

m=lambda f,l:e("["+"f(l.pop()),"*q(l)+"][::-1]")
n=lambda f,x,l:e("f("*l+"*x"+")"*l)
r=lambda i:e("r(i-1)+"*(i>1)+"[i]")
a=lambda f,a:e("f(a["+`r(q(a))`[1:-1].replace(",","-1],a[")+"-1])")
f=lambda f,x,l:e("f("*q(l)+"x,["+`r(q(l))`[1:-1].replace(",","-1]),l[")+"-1])")
t=lambda f,n,x:e("[f("+`r(x)[n-1:]`.replace(",","),f(")[1:-1]+")]")

No loops!

Well, it does a lot of evaling and if your boss can't stand loops, then they'll HATE eval. But, they're going to have to put up with it

A way to do range in a lambda is appreciated so I don't have to do any functions (Shudder.).


  • m=lambda f,l:eval("["+"f(l.pop()),"*len(l)+"][::-1]")
    • Create a string that pops elements from the list, wrap it into a list, reverse it and finally eval it!
  • n=lambda f,x,l:eval("f("*l+"*x"+")"*l)
    • Manually create the string with the nesting, and eval it!
  • r=lambda i:e("r(i-1)+"*(i>1)+"[i]")
    • Create a string that when evaled, either returns [0] or uses recursion to get the previous results and adds the current index to the list. Evals it.
  • a=lambda f,a:eval("f(a["+r(len(a))[1:-1].replace(",","-1],a[")+"-1])")
    • Uses the range function to get the indexes 1-len(list). Replaces the commas in the list stringified with a way to get the correct index of the list a. Evals it!
  • f=lambda f,x,l:eval("f("*len(l)+"x,["+r(len(l))[1:-1].replace(",","-1]),l[")+"-1])")
    • Same as apply except replaces the commas with closing brackets, commas and starting the list index.
  • t=lambda f,n,x:eval("[f("+r(x)[n-1:].replace(",","),f(")[1:-1]+")]")
    • Same as apply and fold except replaces with ending the function and calling the new one. Evals it!

Map, nest, range, apply, fold, table.

Thanks @Zgarb for a lambda for range!

  • \$\begingroup\$ My boss will have my head on his desk :) Could you add a brief explanation as well please? \$\endgroup\$ Sep 24, 2015 at 19:08
  • \$\begingroup\$ How about r=lambda i:[]if i<1 else r(i-1)+[i]? No loops, only recursion. \$\endgroup\$
    – Zgarb
    Sep 24, 2015 at 19:23
  • 1
    \$\begingroup\$ Sure, I'll take that for now but the boss needs more eval to show them how for loops aren't so bad :) \$\endgroup\$
    – Blue
    Sep 24, 2015 at 19:25
  • \$\begingroup\$ Ha! Another version using e=eval: r=lambda i:e("r(i-1)+"*(i>1)+"[i]") \$\endgroup\$
    – Zgarb
    Sep 24, 2015 at 19:31
  • \$\begingroup\$ can you change it from the 60% bonus to a 10% please? I revised the question specification, so to make it fairer \$\endgroup\$ Sep 24, 2015 at 20:53

Javascript ES6, 197 * 0.9 = 177.3 bytes


Map (M=(f,l)=>F((a,b)=>[...a,f(b)],[],l)):

Uses Fold to concat the results of f applied to every member of l onto an empty list. Using built-in functions reduces the this to M=(f,l)=>l.map(f) (didn't use it because it seems cheap...?).

Nest (N=(f,x,n)=>f(--n?N(f,x,n):x)):

Apply f recursively until n is decremented to 0.

Apply (A=(f,l)=>f(...l)):

Uses the spread (...) operator to apply l onto f.

Range (R=n=>n--?[...R(n),n+1]:[]):

Concat n to recursive call of Range until n is decremented to 0.

Fold (F=(f,x,l,n=l.length)=>n--?f(F(f,x,l,n),l[n]):x):

Applies the recursive call of Fold and the n'th element of l to f until n is decremented to 0. Using built-in functions reduces this to F=(f,x,l)=>l.reduce(f,x) (again, seemed cheap...).

Table (T=(f,i)=>([n,x]=i,M(q=>f(q+n-1),R(x-n+1)))):

First initializes n and x to iMin and iMax using destructuring ([n,x]=i), then uses Range to construct the table of values from iMin to iMax. f is then applied over the table using Map and the result is returned.

  • \$\begingroup\$ Wanna know my philosophy? "If it's cheap, buy it." It doesn't say in the specs that you can't use builtins (yet), so use them! \$\endgroup\$ Nov 11, 2015 at 1:04

Python 3, 218 bytes

The unreadable version:

exec("P!:[f(_)for _ in x];Y!,z:Y(f,f(x),z-1)if z else x;T!:f(*x);H!=0:(H(f-1)if~-f else[])+[f];O!,z:O(f,f(x,z[0]),z[1:])if z else x;N!:(N(f,[x[0],x[1]-1])if x[1]-x[0]else[])+[f(x[1])]".replace("!","=lambda f,x"))

The (more) readable version:

P=lambda f,x:[f(_)for _ in x]
Y=lambda f,x,z:Y(f,f(x),z-1)if z else x
T=lambda f,x:f(*x)
H=lambda f,x=0:(H(f-1)if~-f else[])+[f]
O=lambda f,x,z:O(f,f(x,z[0]),z[1:])if z else x
N=lambda f,x:(N(f,[x[0],x[1]-1])if x[1]-x[0]else[])+[f(x[1])]

Going though it one lambda at a time:

Map function P

P=lambda f,x:[f(_)for _ in x]
Just a simple iterator. Not much to say here.

Nest function Y

Y=lambda f,x,z:Y(f,f(x),z-1)if z else x
Recursing until z hits zero, applying f every time. The if clause at the end feels clunky; perhaps there is a better way to end the recursion.

Apply function T

T=lambda f,x:f(*x)
Python has a nice expansion operator to do all of the heavy lifting for me.

Range function H

H=lambda f,x=0:(H(f-1)if~-f else[])+[f]
This one was harder than I was expecting. Ended up taking a recursive approach. Again, the if-else construction takes up a lot of bytes, and I feel it can be improved. Why does it have a dummy x=0, you ask? It's so that when I compress it with the exec, I can replace =lambda f,x instead of just =lambda f.

Fold function O

O=lambda f,x,z:O(f,f(x,z[0]),z[1:])if z else x
Pretty happy with this one. Just lops off the first element of the array every time it recurses, until there's nothing left.

Table function N

N=lambda f,x:(N(f,[x[0],x[1]-1])if x[1]-x[0]else[])+[f(x[1])]
This one is horrible and I'm sure there's room for improvement. Tried to use the range and map functions previously defined for a map(f,range(x,y)) sort of construction, but without much success. Ended up doing a terrible recursive approach which shares some similarity to the range function.

All the lambdas are wrapped up in an exec with a replace to shorten the byte count significantly.

  • \$\begingroup\$ I was about to comment that [f(_)for _ in x] could be shortened to map(f,x), but then I remembered what the challenge was \$\endgroup\$
    – Cyoce
    Sep 8, 2016 at 16:26

Julia, 181 bytes

No bonus for me; I used loops liberally. Sorry boss, but loops in Julia are efficient!

M(f,x)=[f(i...)for i=x]
N(f,x,n)=(for i=1:n x=f(x...)end;x)
R(n)=(i=0;x={};while i<n push!(x,i+=1)end;x)
F(f,x,a)=(for b=a x=f(x,b)end;x)
T(f,i)=[f(j)for j=i[1]:i[2]]

Adding the ellipses after an argument to a function breaks an array, tuple, or what have you into regular function arguments. Otherwise the function will think you're trying to pass an array (or tuple, etc.). It has no effect for single arguments.

Function names:

  • Map: M
  • Nest: N
  • Apply: A
  • Range: R
  • Fold: F
  • Table: T

tinylisp, 325 * 0.9 = 292.5

The language is newer than the question, but it's not going to win anyway.

(d @(q(a a)))(d Q(q((l)(i l(c(@(q q)(h l))(Q(t l)))l))))(d A(q((f a)(v(c(q f)(Q a))))))(d M(q((f l)(i l(c(A f(@(h l)))(M f(t l)))l))))(d N(q((f a x)(i x(A f(@(N f a(s x 1))))a))))(d ,(q((m a b)(i(l b a)m(,(c b m)a(s b 1))))))(d R(q((a)(,()1 a))))(d T(q((f r)(M f(A ,(c()r))))))(d F(q((f a l)(i l(F f(A f(@ a(h l)))(t l))a))))

Defines the functions A (apply), M (map), N (nest), R (range), T (table), and F (fold), along with a couple helper functions. T expects a list of two integers for its second argument.

Tinylisp doesn't even have any loop constructs; everything is accomplished using recursion. Several of these functions are not tail-recursive, so if you call them on large lists they will probably blow the call stack. They could all be implemented with tail recursion... but it would take more bytes, and this is code golf.

Here's an expanded version with whitespace and real words for names, which should be pretty readable if you're familiar with Lisp. (I've aliased most of the tinylisp builtins except for q (quote) and i (if).)

(d define d)
(define cons c)
(define car h)
(define cdr t)
(define subtract s)
(define less l)
(define eval v)

(define lambda
  (q (()
      (arglist expr)
      (list arglist expr))))

(define list (lambda args args))

(define quote-all
  (lambda (lyst)
    (i lyst
         (list (q q) (car lyst))
         (quote-all (cdr lyst)))

(define Apply
  (lambda (func arglist)
    (eval (cons (q func) (quote-all arglist)))))

(define Map
  (lambda (func lyst)
    (i lyst
         (Apply func (list (car lyst)))
         (Map func (cdr lyst)))

(define Nest
  (lambda (func arg times)
    (i times
       (Apply func
              (list (Nest func arg (subtract times 1))))

(define range*
  (lambda (accumulator a b)
    (i (less b a)
       (range* (cons b accumulator) a (subtract b 1)))))

(define Range
  (lambda (x)
    (range* 1 x)))

(define Table
  (lambda (func iterator)
    (Map func
         (Apply range* (cons () iterator)))))

(define Fold
  (lambda (func arg lyst)
    (i lyst
       (Fold func
             (Apply func (list arg (car lyst)))
             (cdr lyst))

Further explanation available upon request.

Sample output

Uses the REPL environment from my reference implementation. I used q (quote) for the unary function and s (subtract) as the binary function for these examples, as well as the function @ (defined in this code) which returns a list of its arguments.

tl> [line of definitions goes here]
tl> (A s (@ 10 7))
tl> (M q (@ 1 2 3 4))
((q 1) (q 2) (q 3) (q 4))
tl> (N q 123 4)
(q (q (q (q 123))))
tl> (R 5)
(1 2 3 4 5)
tl> (T q (@ 3 7))
((q 3) (q 4) (q 5) (q 6) (q 7))
tl> (F s 10 (@ 4 3 2))

Python 2.x: 450.6 bytes (493 bytes before 10% discount)

Golfed answer:

z=lambda a,b:a.append(b)
_=lambda a:a if a is not None else[]
def M(a,b,c=None):
 if d:z(c,A(a,b[0]))
 return M(a,b[1:],c)if d else c
def N(a,b,c):d=A(a,b);return N(a,d,c-1)if c>1 else d
A=lambda a,b:a(*b)if type(b)is list else a(b)
def R(a,b=None):b=_(b);b.insert(0,a);return b if a<=1 else R(a-1,b)
def F(a,b,c):d=a(b,c[0]);return F(a,d,c[1:])if y(c)>1 else d
def T(a,b,c=None,d=None):
 if c is None:c=b[0];d=[]
 z(d,a(c));return T(a,b,c+1,d)if c<b[1]else d

This question was fun. I decided to write my functions without using the Python equivalents (though that may have been a valid loophole) and to write the functions as though Python supports tail recursion. To make this work, I used a lot of optional parameters that allow the required calls to still work.

Below I have ungolfed listings for each function.


A = lambda function, arguments: function(*arguments) if type(arguments) is list else function(arguments)


def M(function, arguments, result=None):
    result = result if result is not None else []
    length = len(arguments)
    if length != 0:
        result.append(A(function, arguments[0]))
    return M(function, arguments[1:], result) if length != 0 else result


def N(function, arguments, times):
    result = A(function, arguments)
    return N(function, result, times - 1) if times > 1 else result

Note that this function requires that the passed function be able to represent multiple arguments variably. Another approach would have been to enforce that the function always received a single list, but that would have required that the passed functions be able to interpret argument lists. There were assumptions either way, so I chose the one that fit the rest of the system better.


def R(ceiling, result=None):
    result = result if result is not None else []
    result.insert(0, ceiling)
    return result if ceiling <= 1 else R(ceiling - 1, result)


def F(function, initial, rest):
    result = function(initial, rest[0])
    return F(function, result, rest[1:] if len(rest) > 1 else result


def T(function, iterator, current=None, result=None):
    if current is None:
        current = iterator[0]
        result = []
    return T(function, iterator, current + 1, result) if current < iterator[1] else result

Here is sample output using the following helper functions:

square = lambda x: x * x
def add(*args):
    addTwo = lambda a, b: a + b
    if len(args) == 1 and type(args[0]) is list:
        return F(addTwo, 0, args[0])
        return F(addTwo, 0, args)

>>> M(square, R(10))
[1, 4, 9, 16, 25, 36, 49, 64, 81, 100]
>>> M(add, [R(i) for i in R(10)])
[1, 3, 6, 10, 15, 21, 28, 36, 45, 55]
>>> T(square, [0, 10])
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100]
>>> N(square, 2, 4)
>>> N(lambda *args: F(lambda a, b: a * b, 1, args) if len(args) > 1 else str(args[0]) + 'a', R(5), 10)
  • \$\begingroup\$ Wow, looks really good! \$\endgroup\$ Sep 24, 2015 at 17:58
  • \$\begingroup\$ That seems like a skewed sense of aesthetics ; ) I always find it amusing to see golfed Python since the first Python book I read talked about how Python enforces readability. \$\endgroup\$
    – sadakatsu
    Sep 24, 2015 at 18:03
  • \$\begingroup\$ I do indeed have a skewed sense of aesthetics :) \$\endgroup\$ Sep 24, 2015 at 18:07
  • \$\begingroup\$ I am confused by other people's scores. I took 10% of the score of each of the required functions which did not use a loop (which was all of them), but other people took 10% of the whole score for each function that did not use a loop (which can be up to 60% off). Which is the correct approach? \$\endgroup\$
    – sadakatsu
    Sep 24, 2015 at 20:48
  • \$\begingroup\$ Yours is the correct way to go, I had an unrealistic expectation and so initially I had in mind the 60% approach, but now I think the 10% will be more stimulating and the righter between the two \$\endgroup\$ Sep 24, 2015 at 20:52

Ceylon, 370 * 0.9 = 333 364 * 0.9 = 327.4

Most of those functions are already available in Ceylon's language package (though sometimes with a bit different signature), but we are defining them here like requested in the question.

alias I=>Integer;R[]m<A,R>(R(A)g,A[]l)=>f((R[]x,A y)=>x.append([g(y)]),[],l);A n<A>(A(A)g,A a,I t)=>f((A x,I y)=>g(x),a,r(t));R y<A,R>(Callable<R,A>g,A v)given A satisfies Anything[]=>g(*v);I[]r(I i)=>t((j)=>j,[1,i]);A f<A,O>(A(A,O)g,A a,O[]o)=>if(nonempty o)then f(g,g(a,o[0]),o.rest)else a;R[]t<R>(R(I)g,[I,I]i)=>i[1]<i[0]then[]else[g(i[0]),*t(g,[i[0]+1,i[1]])];

Actually only two of the functions (t and f) are actually using recursion (over lists and integers, respectively), the other ones are based on these. (Apply is a bit of an outlier, it doesn't really relate to the others.)

I interpret "List" as Ceylon's Sequential type, which is an immutable ordered (possibly empty) sequence of elements. [R*] stands for Sequential<R> – for some reason we can also write it R[], which is one byte shorter.

A function type is Callable<R, A>, where A is a tuple type for the arguments, like [X, Y, Z] (i.e. some subtype of Anything[]). As a shortcut we can write R(X,Y,Z) instead of Callable<R,[X,Y,Z]>.

I aliased Integer as I to save some bytes.

Here is a formatted (and slightly commented) version:

// implement functional paradigms
// Question: http://codegolf.stackexchange.com/q/58588/2338
// My Answer: http://codegolf.stackexchange.com/a/64515/2338

alias I => Integer;

// map – based on fold.
R[] m<A, R>(R(A) g, A[] l) =>
        f((R[]x,A y) => x.append([g(y)]), [], l);

// nest – based on fold + range, throwing away the second
//        argument in a proxy function.
A n<A>(A(A) g, A a, I t) =>
        f((A x, I y) => g(x), a, r(t));

// apply – this looks quite heavy due to type safety.
//         This uses the "spread operator" *.
R y<A, R>(Callable<R,A> g, A v)
        given A satisfies Anything[] =>

// range – based on table (using the identity function)
I[] r(I i) =>
        t((j) => j, [1, i]);

// fold – a plain list recursion.
A f<A, O>(A(A, O) g, A a, O[] o) =>
        if (nonempty o) then f(g, g(a, o[0]), o.rest) else a;

// table – an integer recursion.
//        (Not sure why the min/max parameters need
//         to be passed in one argument.)
R[] t<R>(R(I) g, [I, I] i) =>
        i[1] < i[0] then [] else [g(i[0]), *t(g, [i[0] + 1, i[1]])];

Using "loops"

Table and Map can be implemented shorter using loops (actually, an sequence comprehension):

// map – using a sequence comprehension:
R[] m<A, R>(R(A) g, A[] l) =>
        [for(a in l) g(a)];

// table – map with an integer range.
//        (Not sure why the min/max parameters need
//         to be passed in one argument.)
R[] t<R>(R(I) g, [I, I] i) =>
        m(g, i[0]..i[1]);

Though I'm not sure if the use of the .. operator for the integer range counts as using a built-in function. If this is allowed, the resulting code is this here, length 312:

alias I=>Integer;R[]m<A,R>(R(A)g,A[]l)=>[for(a in l)g(a)];A n<A>(A(A)g,A a,I t)=>f((A x,I y)=>g(x),a,r(t));R y<A,R>(Callable<R,A>g,A v)given A satisfies Anything[]=>g(*v);I[]r(I i)=>t((j)=>j,[1,i]);A f<A,O>(A(A,O)g,A a,O[]o)=>if(nonempty o)then f(g,g(a,o[0]),o.rest)else a;R[]t<R>(R(I)g,[I,I]i)=>m(g,i[0]..i[1]);

(It could be made even shorter by defining r(I i) => 1..i, resulting in score 301. Though that looks even more like cheating.)

If .. is not allowed, we'll have to implement it again. We can use these implementations for r and t (with the m above):

// range – based two-limit range 
I[] r(I i) =>
        q(1, i);

// two-limit range implemented recursively
I[] q(I i, I j) =>
        j < i then [] else [i, *q(i + 1, j)];

// table – map with an integer range.
//        (Not sure why the min/max parameters need
//         to be passed in one argument.)
R[] t<R>(R(I) g, [I, I] i) =>
        m(g, q(i[0], i[1]));

This results in 348 bytes, better than the completely recursive version, but not after applying the bonus.


Scala 3 (compile-time), 403 * 0.9 = 362.7 bytes

This works using compiletime black magic.

import compiletime.S
type T=Tuple
type E=EmptyTuple
type^[F[_],X<:T]<:T=X match{case h*:t=>F[h]*:(F^t)case _=>X}
type N[F[_],X,T]=T match{case 0=>X case S[t]=>N[F,F[X],t]}
type>[A<:T,X]=X match{case 0=>A case S[e]=>X*:A>e}
type R[X]=E>X
type F[G[_,_],X,L]=L match{case h*:t=>F[G,G[X,h],t]case _=>X}
type-[F[_],I]<:T=I match{case(b,e)=>S[e]match{case`b`=>E case _=>F[b]*:(F-(S[b],e))}}

Try it in Scastie

  • ^ is Map.
  • N is Nest.
  • % is Apply.
  • R is Range.
  • F is Fold.
  • - is Table. NB there is a compiler bug so most functions (type constructors) don't work with my implementation of Table, and only the identity function seems to work.

The first 3 lines are just so long names aren't repeated. T and E are typealiases we'll need later, and S is a type that gives the successor of a singleton type, e.g. S[1] becomes 2. S is extremely useful here, as it can not only add 1, but also subtract 1 using match types.

import compiletime.S
type T=Tuple
type E=EmptyTuple


type ^[F[_], X <: T] <: T = X match {
  case h *: t => F[h] *: (F ^ t)
  case _ => E

Here, we declare a type ^ that takes 2 parameters, F and X. The [_] after F means that F is a type constructor of 1 argument, which we'll treat as a function taking a single parameter. X <: T means that X is a subtype of T, which is an alias for Tuple. The second <: T means that ^ returns a tuple (this is necessary because ^ is recursive).

The body of ^ is a match type. The first case if X has at least one element (tuples can be uncons-ed in Scala 3). If so, X is destructured into a head h and a tail t. F[h] applies F to h, and we join that using *: to the result of mapping the result of the tuple (F ^ t is equivalent to ^[F, t]). The second case will be reached if X is empty, in which case we return E, the empty tuple (or rather, the type of an empty tuple).


type N[F[_], X, T] = T match {
  case 0 => X
  case S[t] => N[F, F[X], t]

This is more interesting. Here, F is the function to repeatedly apply, X is the starting argument, and T is how many times to apply F. If T is 0, we simply return X. Otherwise, we see if it is the successor of some type t. If T is a literal type extending Int, t will be T - 1, so the second case is basically calling N(F, F(X), T - 1).


type %[F[_], X] = F[X]

This is boring. It just takes a function F and another argument X and applies F to X.


type >[A <: T, X] = X match {
  case 0 => A
  case S[e] => X *: A > e
type R[X] = E > X

R is the Range function, but >, a tail-recursive type, does all the heavy-lifting. > takes an accumulator tuple A and an integer X. When X reaches 0, it's time to return the accumulator. Otherwise, we use S to find an e that is X - 1. X is prepended to the accumulator and > is called again with e. R just calls > with an empty tuple as the accumulator to start it off.


type F[G[_, _], X, L] = L match{
  case h *: t => F[G, G[X, h], t]
  case _ => X

Here, G is a function/type constructor that takes two parameters (like F[_] above). X is the starting argument, and L is the tuple to fold over. If L is not empty, the first case will be matched, so we call F again with the same function G, but with X as the result of applying G on X and the first element of L, and with L as L's tail.


type -[F[_], I] <: T = I match{
  case (b, e) => S[e] match{
    case `b` => E
    case _ => F[b] *: ( F - (S[b],e) )

This got a little hairy because of how the second parameter is taken, and it's also affected by a compiler bug (mentioned above). First, we destructure the iterator I to get the start and end (here, b and e). If b is greater than e, we return an empty tuple (E). To test that, we find e + 1 (S[e]) and check if that matches b. Otherwise (case _), we apply F to Imin/b and prepend that to the result of calling Table with b + 1 (S[b]) as the new beginning.


Go, 489 bytes, int only

func M(f func(int)int,L[]int)(Q[]int){for _,e:=range L{Q=append(Q,f(e))};return}
func N(f func(int)int,s,t int)int{if t<1{return s};return f(N(f,s,t-1))}
func A(f func(...int)int,L[]int)int{return f(L...)}
func R(r int)(O[]int){for i:=1;i<=r;i++{O=append(O,i)};return}
func F(f func(int,int)int,x int,o[]int)int{l:=len(o)-1;if len(o)<2{return f(x,o[l])}else{return f(F(f,x,o[:l]),o[l])}}
func T(f func(int)int,k...int)(O[]int){if len(k)>1{for i:=k[0];i<=k[1];i++{O=append(O,f(i))}};return}

Attempt This Online!

Golang is really not designed for concise functional programming. This solution works on ints only.

Go, 492 bytes, generic

func M[I,O any](f func(I)O,L[]I)(Q[]O){for _,e:=range L{Q=append(Q,f(e))};return}
func N[I any](f func(I)I,s I,t int)I{if t<1{return s};return f(N(f,s,t-1))}
func A[I,O any](f func(...I)O,L[]I)O{return f(L...)}
func R(r int)(O[]int){for i:=1;i<=r;i++{O=append(O,i)};return}
func F[I any](f func(I,I)I,x I,o[]I)I{l:=len(o)-1;if len(o)<2{return f(x,o[l])}else{return f(F(f,x,o[:l]),o[l])}}
func T[K any](f func(int)K,k...int)(O[]K){if len(k)>1{for i:=k[0];i<=k[1];i++{O=append(O,f(i))}};return}

Attempt This Online!


Groovy (146 Bytes) (146*90%=131.4)

P.S. I don't know what you're considering as a 'loop' in this context, I only applied the bonus after I was told to in the comments by OP and will remove if 2-3 additional users say these collection functions and iterators are loops and that I don't deserve the bonus. Also, if you want to call me out on my use of 1..it, please do so and I will rework it / update my bytecount.

m={f,l->l.collect{f(it)}}            // Map
n={f,x,n->n.times{x=f(x)};x}         // Nest
a={f,l->f(l)}                        // Apply
r={1..it}                            // Range (Is this cheating?)
f={f,x,l->l.each{x=f(x,it)};x}       // Fold
t={f,l->(l[0]..l[1]).collect{f(it)}} // Table

Example Input/Output

println m(f1,l)
println n(f1,x,y)
println a(f2,l)
println r(y)
println f(f3,x,l)
println t(f1,l2)


MAP:   [2, 4, 6, 8, 10]
NEST:  32
APPLY: 120
RANGE: [1, 2, 3, 4, 5]
FOLD:  120
TABLE: [2, 4, 6, 8, 10, 12, 14, 16, 18]

Try it yourself: https://groovyconsole.appspot.com/edit/5203951758606336

  • \$\begingroup\$ This technically does not use loops, so remember the bonus! Else, great answer! \$\endgroup\$ Sep 8, 2016 at 18:53
  • \$\begingroup\$ Technically no loops?! Really?! .each{} .times{} .collect{} are iterators. \$\endgroup\$ Sep 8, 2016 at 18:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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