Implement functional programming paradigms

Question

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:

Map

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:

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

returns

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

and

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

returns

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

Nest

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)

returns

f(f(f(x)))

and

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

returns

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

Apply

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

returns

f(a,b,c)

Range

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

Range(5)

returns

{ 1, 2, 3, 4, 5}

Fold

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

returns

f(f(f(f(x,a),b),c),d)

Table

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

returns

{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!!!

Answer 1

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

f#(a:b)=f a:f#b;f#x=x
(f&x)0=x;(f&x)i=f$f&x$i-1
i=id
r x=i%(1,x)
(g?x)(a:b)=g(g?x$b)a;(g?x)y=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

Answer 2

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:

e=eval;q=len
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.).

Explanations:

• 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!

Answer 3

Javascript ES6, 197 * 0.9 = 177.3 bytes

M=(f,l)=>F((a,b)=>[...a,f(b)],[],l)
N=(f,x,n)=>f(--n?N(f,x,n):x)
A=(f,l)=>f(...l)
R=n=>n--?[...R(n),n+1]:[]
F=(f,x,l,n=l.length)=>n--?f(F(f,x,l,n),l[n]):x
T=(f,i)=>([n,x]=i,M(q=>f(q+n-1),R(x-n+1)))

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.

Answer 4

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)
A(f,x)=f(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

Answer 5

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.

Answer 6

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
       (cons
         (list (q q) (car lyst))
         (quote-all (cdr lyst)))
       lyst)))

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

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

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

(define range*
  (lambda (accumulator a b)
    (i (less b a)
       accumulator
       (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))
       arg)))

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]
@
Q
A
M
N
,
R
T
F
tl> (A s (@ 10 7))
3
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))
1

Answer 7

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

Golfed answer:

y=len
z=lambda a,b:a.append(b)
_=lambda a:a if a is not None else[]
def M(a,b,c=None):
 c=_(c);d=y(b)
 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.

Apply:

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

Map:

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

Nest:

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.

Range:

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)

Fold:

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

Table:

def T(function, iterator, current=None, result=None):
    if current is None:
        current = iterator[0]
        result = []
    result.append(function(current))
    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])
    else:
        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)
65536
>>> N(lambda *args: F(lambda a, b: a * b, 1, args) if len(args) > 1 else str(args[0]) + 'a', R(5), 10)
'120aaaaaaaaa'

Answer 8

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[] =>
        g(*v);

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

Answer 9

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

f1={2*it}
f2={a,b,c,d,e->a*b*c*d*e}
f3={a,b->a*b}
l=[1,2,3,4,5]
l2=[1,9]
y=5
x=1
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)

Output

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