Реализуйте парадигмы функционального программирования

21

Ваша компания только начинает работу над проектом, и вы впервые решили использовать стиль кода функционального программирования. Однако ваш начальник действительно неуверен в себе и не хочет использовать встроенные функции, а требует от вас реализации основных функций. В частности , вы должны написать функции: Map, Nest, Apply, Range, Foldи Tableна языке , на ваш выбор. Босс очень занятой человек, и он хочет, чтобы программы были максимально короткими, чтобы он не тратил время на чтение. Он также не хотел бы, чтобы вы использовали циклы, поэтому вы не будете использовать циклы на 10%.

Подробные требования к функциям приведены ниже:

карта

MapФункция принимает два параметра: fи , listгде fфункция и listсписок значений. Он должен вернуть fпримененный к каждому элементу list. Поэтому он будет работать так:

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

возвращается

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

а также

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

возвращается

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

Гнездо

NestФункция принимает три параметра, а: f, arg, timesгде fесть функция, argявляется его началом аргумента, и timesсколько раз применяются функция. Он должен вернуть выражение с fпримененным timesвременем к arg. Поэтому он будет работать так:

Nest(f, x, 3)

возвращается

f(f(f(x)))

а также

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

возвращается

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

Подать заявление

ApplyФункция принимает два параметра: fи , argsгде fфункция и argsсписок. Это должно относиться fк args. Следовательно:

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

возвращается

f(a,b,c)

Диапазон

RangeФункция принимает одно целое число rи выводит целые числа до этого числа. Следовательно:

Range(5)

возвращается

{ 1, 2, 3, 4, 5}

складка

FoldФункция принимает три параметра f, arg, othersгде fесть функция, argпросто параметр, и othersсписок. Это будет работать так:

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

возвращается

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

Стол

Табличные функции должны принимать функцию fи параметр, называемый iteratorв виде: {iMin, iMax}где iMinи iMaxявляются целыми числами. Вы должны подать заявку fв указанном диапазоне. Следовательно:

Table(f, {0, 5})

возвращается

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

Я использовал определение этих функций на странице функционального программирования Mathematica , так что, если вам нужно больше руководств, отправляйтесь туда. Обратите внимание, что вам не нужно будет реализовывать все версии функций, показанных на этой странице, а только те, которые написаны в этом посте.

Стандартные лазейки запрещены как обычно.

Если ваш язык не позволяет передавать функции в качестве аргументов, вам необходимо реализовать эту возможность и добавить ее в свой ответ. Однако количество байтов этой операции не будет добавлено к итогу.

Это кодовый гольф, поэтому выигрывает самый короткий код. Удачи!!!

WizardOfMenlo
источник
Это круто! +1 Однако я не совсем понимаю, как Tableздесь работает. Ваш пример должен быть Table(f, {x, 0, 5})? Я также не понимаю цели x, так как она просто применяет функцию к диапазону.
kirbyfan64sos
@ kirbyfan64sos Спасибо! Да, это была опечатка, я оставил x в качестве ссылки на mathematica, которая использует его как символическое будущее, однако я думаю, что смогу это сделать
WizardOfMenlo
Еще один вопрос: как мы называем функции? Должны ли мы дать им точно такие же имена? Односимвольный?
kirbyfan64sos
@ kirbyfan64sos Так как это код-гольф, я позволю использовать имена из одной буквы, однако в вашем ответе поставьте заголовок над каждой функцией, чтобы мы знали, какая она. Также не используйте встречные буквы.
WizardOfMenlo
Не могли бы вы более конкретно сказать, что считается петлей?
xnor

Ответы:

9

Haskell, много предыдущих байтов насчитывает 127 * 0,9 = 114,3 байта

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)

Никаких петель, только рекурсия.

#это карта: (*2) # [1,2,3]->[2,4,6]

&это гнездо: ((*2) & 3) 4->48

iэто применимо: i (*2) 7->14

rэто диапазон: r 4->[1,2,3,4]

?складывается: ((+) ? 0) [1,2,3,4]->10

%это таблица: (*2) % (2,4)->[4,6,8]

По просьбе разглаженной версии с комментариями. Обратите внимание, &и ?это троичные инфиксные операторы, которые требуют дополнительных скобок при вызове или сопоставлении с шаблоном.

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

Спасибо @dfeuer и @Zgarb за полезные советы

Ними
источник
Я новичок в Haskell, выглядит неплохо, однако не могли бы вы добавить пояснение к тому, что вы делаете?
WizardOfMenlo
1
@WizardOfMenlo: добавлено несколько комментариев
nimi
Просто понял, насколько элегантен Хаскелл, действительно хорошо!
WizardOfMenlo
1
Игнорирование бесконечных списков и эффективности m#q=reverse$f((:).m)[]q. Это такая же длина, как у вас, но намного сложнее для чтения.
dfeuer
Вы можете сократить !, сделав его имя вместо оператора: i f=f.
dfeuer
5

Python 2, 305,1 байта (-10% 376 369 366 349 339 байтов)

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(")

Когда развернуто, эквивалентно:

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]+")]")

Никаких петель!

Ну, это делает много, evalи если ваш босс не может стоять на петлях, то они будут ненавидеть Eval. Но им придется смириться с этим

Способ делать rangeлямбду очень важен, поэтому мне не нужно выполнять никаких функций (Shudder.).

Пояснения:

  • m=lambda f,l:eval("["+"f(l.pop()),"*len(l)+"][::-1]")
    • Создайте строку, которая извлекает элементы из списка, оберните ее в список, переверните ее и, наконец, оцените!
  • n=lambda f,x,l:eval("f("*l+"*x"+")"*l)
    • Вручную создайте строку с вложенностью и оцените ее!
  • r=lambda i:e("r(i-1)+"*(i>1)+"[i]")
    • Создайте строку, которая при evalредактировании либо возвращает, [0]либо использует рекурсию для получения предыдущих результатов и добавляет текущий индекс в список. Зло это.
  • a=lambda f,a:eval("f(a["+г (LEN (а))[1:-1].replace(",","-1],a[")+"-1])")
    • Использует функцию range для получения индексов 1-len (list). Заменяет запятые в списке на строчные, чтобы получить правильный индекс списка a. Извращает это!
  • f=lambda f,x,l:eval("f("*len(l)+"x,["+г (LEN (л))[1:-1].replace(",","-1]),l[")+"-1])")
    • То же самое, что и применить, за исключением того, что заменяет запятые закрывающими скобками, запятыми и запуском индекса списка.
  • t=lambda f,n,x:eval("[f("+г (х) [п-1:].replace(",","),f(")[1:-1]+")]")
    • То же самое, что применить и сложить, за исключением замены завершением функции и вызова новой. Извращает это!

Карта, гнездо, дальность, применить, сложить, таблица.

Спасибо @Zgarb за лямбду за диапазон!

синий
источник
У моего босса моя голова на столе :) Не могли бы вы также добавить краткое объяснение, пожалуйста?
WizardOfMenlo
Как насчет r=lambda i:[]if i<1 else r(i-1)+[i]? Никаких петель, только рекурсия.
Згарб
1
Конечно, сейчас я возьму это, но боссу нужно больше, evalчтобы показать им, что петли не так уж и плохи :)
Blue
Ха! Другая версия с использованием e=eval:r=lambda i:e("r(i-1)+"*(i>1)+"[i]")
Zgarb
Вы можете изменить его с бонуса 60% на 10%, пожалуйста? Я пересмотрел спецификацию вопроса, чтобы сделать его более справедливым
WizardOfMenlo
5

Javascript ES6, 197 * 0,9 = 177,3 байта

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

Карта ( M=(f,l)=>F((a,b)=>[...a,f(b)],[],l)):

Использует Fold для объединения результатов, fпримененных к каждому члену, в lпустой список. Использование встроенных функций уменьшает это до M=(f,l)=>l.map(f)(не использовал его, потому что это кажется дешевым ...?).

Гнездо ( N=(f,x,n)=>f(--n?N(f,x,n):x)):

Применить fрекурсивно, пока nне уменьшится до 0.

Применить ( A=(f,l)=>f(...l)):

Использует распространение ( ...оператор) , чтобы применить lна f.

Диапазон ( R=n=>n--?[...R(n),n+1]:[]):

Concat nк рекурсивному вызову Range, пока nне уменьшится до 0.

Сложить ( F=(f,x,l,n=l.length)=>n--?f(F(f,x,l,n),l[n]):x):

Применяется рекурсивный вызов Fold и n«й элемент lк fдо nне уменьшается до 0. Использование встроенных функций уменьшает это в F=(f,x,l)=>l.reduce(f,x)(опять же , казалось , дешево ...).

Таблица ( T=(f,i)=>([n,x]=i,M(q=>f(q+n-1),R(x-n+1)))):

Сначала инициализируется nи xдля iMin и iMax с помощью destructuring ( [n,x]=i), затем использует Range для построения таблицы значений от iMin до iMax. fЗатем применяется к таблице с помощью Map, и результат возвращается.

Dendrobium
источник
Хотите знать мою философию? «Если это дешево, купи это». В спецификациях не сказано, что вы не можете использовать встроенные функции (пока), поэтому используйте их!
Мама Fun Roll
4

Python 3, 218 байт

Нечитаемая версия:

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

(Более) читаемая версия:

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

Пройдя по одной лямбде за раз:

Функция карты P

P=lambda f,x:[f(_)for _ in x]
Просто простой итератор. Не так много, чтобы сказать здесь.

Гнездовая функция Y

Y=lambda f,x,z:Y(f,f(x),z-1)if z else x
Повторяется до тех пор, пока не zдостигнет нуля, применяя fкаждый раз. Предложение if в конце кажется неуклюжим; возможно, есть лучший способ закончить рекурсию.

Применить функцию T

T=lambda f,x:f(*x)
В Python есть хороший оператор расширения, который сделает всю тяжелую работу за меня.

Функция диапазона H

H=lambda f,x=0:(H(f-1)if~-f else[])+[f]
Этот был сложнее, чем я ожидал. Закончилось рекурсивным подходом. Опять же, конструкция if-else занимает много байтов, и я чувствую, что ее можно улучшить. x=0Вы спрашиваете, почему у него есть манекен ? Это так, что когда я сжимаю его с exec, я могу заменить =lambda f,xвместо просто =lambda f.

Сложить функцию O

O=lambda f,x,z:O(f,f(x,z[0]),z[1:])if z else x
Очень доволен этим. Просто обрезает первый элемент массива каждый раз, когда он повторяется, пока ничего не останется.

Столовая функция N

N=lambda f,x:(N(f,[x[0],x[1]-1])if x[1]-x[0]else[])+[f(x[1])]
Это ужасно, и я уверен, что есть место для улучшения. Попытка использовать функции диапазона и карты, ранее определенные для своего map(f,range(x,y))рода конструкции, но без особого успеха. Закончилось ужасным рекурсивным подходом, который имеет некоторое сходство с функцией диапазона.

Все лямбды обернуты в execa, replaceчтобы значительно сократить количество байтов.

Tryth
источник
Я собирался прокомментировать, что [f(_)for _ in x]можно сократить до map(f,x), но потом я вспомнил, что это был за вызов
Cyoce
4

Юлия, 181 байт

Нет бонуса для меня; Я использовал петли свободно. Извините босс, но петли в Юлии эффективны!

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]]

Добавление эллипсов после аргумента в функцию разбивает массив, кортеж или что-то еще на обычные аргументы функции. В противном случае функция будет думать, что вы пытаетесь передать массив (или кортеж и т. Д.). Это не влияет на отдельные аргументы.

Имена функций:

  • Карта: M
  • Гнездо: N
  • Подать заявление: A
  • Диапазон: R
  • Fold: F
  • Стол: T
Алекс А.
источник
4

тинилисп , 325 * 0,9 = 292,5

Язык новее, чем вопрос, но он все равно не победит.

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

Определяет функции A(применить), M(карта), N(гнездо), R(диапазон), T(таблица) иF (сложить), а также несколько вспомогательных функций. Tожидает список из двух целых чисел для своего второго аргумента.

Тинилисп даже не имеет петлевых конструкций; все выполняется с помощью рекурсии. Некоторые из этих функций не являются хвостово-рекурсивными , поэтому, если вы вызываете их в больших списках, они, вероятно, сорвут стек вызовов. Все они могут быть реализованы с помощью хвостовой рекурсии ... но это заняло бы больше байтов, и это кодовый гольф.

Вот расширенная версия с пробелами и реальными словами для имен, которая должна быть довольно удобочитаемой, если вы знакомы с Lisp. (Я присвоил псевдоним большинству встроенных тинилиспов, за исключением q(цитата) и i(если).)

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

Дальнейшее объяснение доступно по запросу.

Образец вывода

Использует среду REPL из моей эталонной реализации. Я использовал q(цитата) для унарной функции и s(вычитание) в качестве двоичной функции для этих примеров, а также функцию @(определенную в этом коде), которая возвращает список ее аргументов.

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
DLosc
источник
2

Python 2.x: 450,6 байта (493 байта до 10% скидки)

Гольф ответ:

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

Этот вопрос был веселым. Я решил написать свои функции без использования эквивалентов Python (хотя это могло быть допустимой лазейкой) и написать функции, как будто Python поддерживает хвостовую рекурсию. Чтобы заставить это работать, я использовал много дополнительных параметров, которые позволяют требуемым вызовам все еще работать.

Ниже приведены списки для каждой функции.

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

Обратите внимание, что эта функция требует, чтобы передаваемый functionэлемент мог представлять несколько аргументов по-разному. Другой подход состоял бы в том, чтобы обеспечить, чтобы функция всегда получала один список, но для этого требовалось, чтобы переданные функции могли интерпретировать списки аргументов. В любом случае были предположения, поэтому я выбрал тот, который лучше соответствует остальной системе.

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

Вот пример вывода с использованием следующих вспомогательных функций:

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'
sadakatsu
источник
Вау, выглядит действительно хорошо!
WizardOfMenlo
Это похоже на искаженное чувство эстетики; Я всегда нахожу забавным видеть Python в гольфе с тех пор, как в первой книге о Python, которую я прочитал, говорилось о том, как Python обеспечивает читабельность.
садакацу
У меня действительно есть искаженное чувство эстетики :)
WizardOfMenlo
Я смущен оценками других людей. Я взял 10% от оценки каждой из необходимых функций, которые не использовали цикл (который был всеми из них), но другие люди взяли 10% от общего результата для каждой функции, которая не использовала цикл (который может быть до 60%). Какой правильный подход?
садакацу
Ваш правильный путь, у меня были нереалистичные ожидания, и поэтому изначально я имел в виду подход на 60%, но теперь я думаю, что 10% будут более стимулирующими и вернее между ними
WizardOfMenlo
2

Цейлон, 370 * 0,9 = 333 364 * 0,9 = 327,4

Большинство из этих функций уже доступны в языковом пакете Цейлона (хотя иногда и с немного другой сигнатурой), но мы определяем их здесь, как указано в вопросе.

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]])];

На самом деле только две функции ( tи f) фактически используют рекурсию (над списками и целыми числами соответственно), остальные основаны на них. (Применить - это немного необычно, на самом деле это не относится к другим.)

Я интерпретирую «Список» как последовательный тип Цейлона, который представляет собой неизменную упорядоченную (возможно, пустую) последовательность элементов. [R*]означает Sequential<R>- по какой-то причине мы можем также написать этоR[] , что на один байт короче.

Тип функции - это Callable<R, A>где Aтип кортежа для аргументов, например [X, Y, Z](например, некоторый подтип Anything[]). В качестве ярлыка мы можем написать R(X,Y,Z)вместо Callable<R,[X,Y,Z]>.

Я псевдонимы , Integerкак Iдля сохранения некоторых байт.

Вот отформатированная (и слегка прокомментированная) версия:

// 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]])];

Используя "петли"

Таблица и Карта могут быть реализованы короче, используя циклы (на самом деле, понимание последовательности):

// 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]);

Хотя я не уверен, считается ли использование ..оператора для целочисленного диапазона встроенной функцией. Если это разрешено, результирующий код будет таким, длина 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]);

(Это можно сделать еще короче, определив r(I i) => 1..iрезультат, получив 301 балл. Хотя это больше похоже на обман.)

Если ..не разрешено, мы должны будем реализовать это снова. Мы можем использовать эти реализации для rи tmвыше):

// 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]));

В результате получается 348 байт, что лучше, чем полностью рекурсивная версия, но не после применения бонуса.

Пауло Эберманн
источник
0

Groovy (146 байт) (146 * 90% = 131,4)

PS Я не знаю, что вы рассматриваете как «цикл» в этом контексте, я применил бонус только после того, как мне сказали в комментариях OP и удалит, если 2-3 дополнительных пользователя скажут эти функции сбора и итераторы это петли и что я не заслуживаю бонуса. Кроме того, если вы хотите позвонить мне по поводу моего использования 1..it, пожалуйста, сделайте это, и я переработаю его / обновлю свой 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

Пример ввода / вывода

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)

Выход

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]

Попробуйте сами: https://groovyconsole.appspot.com/edit/5203951758606336

Урна волшебного осьминога
источник
Это технически не использует петли, поэтому запомните бонус! Остальное, отличный ответ!
WizardOfMenlo
Технически петель нету ?! В самом деле?! .each {} .times {} .collect {} являются итераторами.
Волшебная Урна Осьминога