Implementar paradigmas de programación funcional.

21

Su empresa recién está comenzando un proyecto, y por primera vez decidió usar un estilo de código de programación funcional. Sin embargo, su jefe es muy inseguro y no quiere usar funciones integradas, y requiere que implemente las funciones principales. En particular, es necesario escribir las funciones: Map, Nest, Apply, Range, Foldy Tableen un idioma de su elección. El jefe es un hombre muy ocupado, y quiere tener los programas lo más cortos posible, para no perder el tiempo leyendo. También le gustaría que no use bucles, por lo tanto, tendrá una reducción del 10% en el recuento de bytes por no usar bucles.

Los requisitos detallados de las funciones están a continuación:

Mapa

La Mapfunción toma dos parámetros: fy listwhere fes una función y listes una lista de valores. Debe devolver el faplicado a cada elemento de list. Por lo tanto, funcionará como tal:

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

devoluciones

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

y

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

devoluciones

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

Nido

La Nestfunción toma tres parámetros, así: f, arg, timesdonde fes una función, arges su argumento de partida, y timeses cuántas veces se aplica la función. Debería devolver una expresión con tiempos faplicados timesa arg. Por lo tanto, funcionará como tal:

Nest(f, x, 3)

devoluciones

f(f(f(x)))

y

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

devoluciones

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

Aplicar

La Applyfunción toma dos parámetros: fy argsdónde fes una función y argsuna lista. Debería aplicarse fa la args. Por lo tanto:

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

devoluciones

f(a,b,c)

Distancia

La Rangefunción toma un entero ry genera los enteros hasta ese número. Por lo tanto:

Range(5)

devoluciones

{ 1, 2, 3, 4, 5}

Doblez

La Foldfunción toma tres parámetros f, arg, othersdonde fes una función, arges un parámetro simple, y othersuna lista. Funcionará como tal:

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

devoluciones

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

Mesa

Las funciones de la tabla deben tomar una función fy un parámetro llamado iteratoren la forma: {iMin, iMax}donde iMiny iMaxson enteros. Debe aplicar fsobre el rango especificado. Por lo tanto:

Table(f, {0, 5})

devoluciones

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

He usado la definición de estas funciones de la página de programación funcional de Mathematica , así que dirígete allí si necesitas más orientación. Tenga en cuenta que no necesitará implementar todas las versiones de las funciones que se muestran en esa página, sino solo aquellas escritas en esta publicación.

Las lagunas estándar no se permiten como de costumbre.

En caso de que su lenguaje no permita que las funciones se pasen como argumentos, debe implementar esta capacidad y agregarla a su respuesta. Sin embargo, el recuento de bytes de esta operación no se agregará al total.

Este es el código de golf, por lo que gana el código más corto. ¡¡¡Buena suerte!!!

WizardOfMenlo
fuente
¡Esto es asombroso! +1 Sin embargo, realmente no entiendo cómo Tablefunciona aquí. ¿Se supone que es tu ejemplo Table(f, {x, 0, 5})? Tampoco entiendo el propósito x, ya que solo aplica la función al rango.
kirbyfan64sos
@ kirbyfan64sos Gracias! Sí, fue un error tipográfico, dejé x como referencia a Mathica, que lo usa como una característica simbólica, sin embargo, creo que puedo sacarlo
WizardOfMenlo
Una pregunta más: ¿cómo nombramos las funciones? ¿Tenemos que darles exactamente los mismos nombres? Sola letra?
kirbyfan64sos
@ kirbyfan64sos Dado que se trata de código de golf, permitiré nombres de letras individuales, sin embargo, en su respuesta, coloque un encabezado sobre cada función para que sepamos cuál es. Tampoco use letras colisionantes.
WizardOfMenlo
¿Podría ser más específico sobre lo que cuenta como un bucle?
xnor

Respuestas:

9

Haskell, muchos bytes anteriores cuentan 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)

Sin bucles, solo recursión.

#es el mapa: (*2) # [1,2,3]->[2,4,6]

&es nido: ((*2) & 3) 4->48

ise aplica: i (*2) 7->14

res rango: r 4->[1,2,3,4]

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

%es la tabla: (*2) % (2,4)->[4,6,8]

Según lo solicitado, una versión no golfista con comentarios. Tenga en cuenta, &y ?son operadores infijos ternarios, que requieren paréntesis adicionales cuando se los llama o el patrón coincide.

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

Gracias a @dfeuer y @Zgarb por algunos consejos útiles

nimi
fuente
Soy nuevo en Haskell, se ve bastante bien, pero ¿podría agregar una explicación a lo que está haciendo?
WizardOfMenlo
1
@WizardOfMenlo: agregó algunos comentarios
nimi
Me acabo de dar cuenta de lo elegante que es Haskell, ¡muy bien!
WizardOfMenlo
1
Haciendo caso omiso de las listas y la eficiencia infinitas, m#q=reverse$f((:).m)[]q. Esta es la misma longitud que la tuya, pero mucho más difícil de leer.
dfeuer
Se puede acortar !por lo que es un nombre en lugar de un operador: i f=f.
dfeuer
5

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

Cuando se expande, equivalente a:

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 hay bucles!

Bueno, hace mucho trabajo evaly si tu jefe no puede soportar los bucles, ODIA la evaluación. Pero van a tener que soportarlo

Se rangeaprecia una forma de hacerlo en una lambda, así que no tengo que hacer ninguna función (Shudder).

Explicaciones:

  • m=lambda f,l:eval("["+"f(l.pop()),"*len(l)+"][::-1]")
    • ¡Crea una cadena que muestre elementos de la lista, envuélvela en una lista, inviértela y finalmente evalúala!
  • n=lambda f,x,l:eval("f("*l+"*x"+")"*l)
    • ¡Crea manualmente la cadena con el anidamiento y evalúala!
  • r=lambda i:e("r(i-1)+"*(i>1)+"[i]")
    • Cree una cadena que, cuando se evaledite, devuelva [0]o utilice la recursividad para obtener los resultados anteriores y agregue el índice actual a la lista. Lo evalúa
  • a=lambda f,a:eval("f(a["+r (len (a))[1:-1].replace(",","-1],a[")+"-1])")
    • Utiliza la función de rango para obtener los índices 1-len (lista). Reemplaza las comas en la lista en cadena con una forma de obtener el índice correcto de la lista a. Lo evalúa!
  • f=lambda f,x,l:eval("f("*len(l)+"x,["+r (len (l))[1:-1].replace(",","-1]),l[")+"-1])")
    • Lo mismo que aplicar excepto que reemplaza las comas con corchetes de cierre, comas y comienza el índice de la lista.
  • t=lambda f,n,x:eval("[f("+r (x) [n-1:].replace(",","),f(")[1:-1]+")]")
    • Lo mismo que aplicar y doblar, excepto que reemplaza al finalizar la función y llamar a la nueva. Lo evalúa!

Mapa, nido, rango, aplicar, doblar, tabla.

Gracias @ Zgarb por una lambda para el rango!

Azul
fuente
Mi jefe tendrá la cabeza sobre su escritorio :) ¿Podría agregar una breve explicación también por favor?
WizardOfMenlo
¿Qué tal r=lambda i:[]if i<1 else r(i-1)+[i]? Sin bucles, solo recursión.
Zgarb
1
Claro, lo tomaré por ahora, pero el jefe necesita más evalpara mostrarles cómo los bucles no son tan malos :)
Azul
¡Decir ah! Otra versión que usa e=eval:r=lambda i:e("r(i-1)+"*(i>1)+"[i]")
Zgarb
¿Puedes cambiarlo de la bonificación del 60% a un 10% por favor? Revisé la especificación de la pregunta, para que sea más justa
WizardOfMenlo
5

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

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

Utiliza Fold para concatenar los resultados de faplicado a cada miembro de len una lista vacía. El uso de funciones integradas reduce esto a M=(f,l)=>l.map(f)(¿no lo usó porque parece barato ...?).

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

Aplicar de forma frecursiva hasta que nse reduzca a 0.

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

Utiliza la propagación ( ...operador) para aplicar la f.

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

Concat na llamada recursiva de Range hasta que nse reduzca a 0.

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

Se aplica la llamada recursiva de doblez y la n-ésimo elemento de la la fhasta que nse decrementa a 0. El uso de las funciones integradas reduce a esto F=(f,x,l)=>l.reduce(f,x)(de nuevo, barato parecido ...).

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

Primero se inicializa ny xen iMin e iMax usando destructuring ( [n,x]=i), luego usa Range para construir la tabla de valores de iMin a iMax. fluego se aplica sobre la tabla usando Map y se devuelve el resultado

Dendrobium
fuente
¿Quieres saber mi filosofía? "Si es barato, cómpralo". No dice en las especificaciones que no puedes usar builtins (todavía), ¡así que úsalos!
Mama Fun Roll
4

Python 3, 218 bytes

La versión ilegible:

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

La versión (más) legible:

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

Yendo aunque sea una lambda a la vez:

Función de mapa P

P=lambda f,x:[f(_)for _ in x]
Solo un simple iterador. No hay mucho que decir aquí.

Función de nido Y

Y=lambda f,x,z:Y(f,f(x),z-1)if z else x
Recurrente hasta llegar a zcero, aplicando fcada vez. La cláusula if al final se siente torpe; Quizás haya una mejor manera de terminar con la recursión.

Aplicar función T

T=lambda f,x:f(*x)
Python tiene un buen operador de expansión para hacer todo el trabajo pesado por mí.

Función de rango H

H=lambda f,x=0:(H(f-1)if~-f else[])+[f]
Este fue más difícil de lo que esperaba. Terminé tomando un enfoque recursivo. Nuevamente, la construcción if-else ocupa muchos bytes, y creo que se puede mejorar. ¿Por qué tiene un muñeco x=0, preguntas? Es así que cuando lo comprimo con el exec, puedo reemplazarlo en =lambda f,xlugar de solo =lambda f.

Función de plegado O

O=lambda f,x,z:O(f,f(x,z[0]),z[1:])if z else x
Muy contento con este. Simplemente corta el primer elemento de la matriz cada vez que se repite, hasta que no quede nada.

Función de tabla N

N=lambda f,x:(N(f,[x[0],x[1]-1])if x[1]-x[0]else[])+[f(x[1])]
Este es horrible y estoy seguro de que hay margen de mejora. Intenté usar las funciones de rango y mapa previamente definidas para una map(f,range(x,y))especie de construcción, pero sin mucho éxito. Terminé haciendo un enfoque recursivo terrible que comparte cierta similitud con la función de rango.

Todas las lambdas están envueltas en una execcon una replacepara acortar significativamente el recuento de bytes.

Tryth
fuente
Estaba a punto de comentar que [f(_)for _ in x]podría acortarse map(f,x), pero luego recordé cuál era el desafío
Cyoce,
4

Julia, 181 bytes

No hay bonificación para mí; Usé bucles generosamente. Lo siento jefe, pero los bucles en Julia son eficientes.

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

Agregar los puntos suspensivos después de un argumento a una función rompe una matriz, tupla o lo que sea que tenga en argumentos de funciones regulares. De lo contrario, la función pensará que está intentando pasar una matriz (o tupla, etc.). No tiene ningún efecto para argumentos únicos.

Nombres de funciones:

  • Mapa: M
  • Nido: N
  • Aplicar: A
  • Distancia: R
  • Doblez: F
  • Mesa: T
Alex A.
fuente
4

tinylisp , 325 * 0.9 = 292.5

El lenguaje es más nuevo que la pregunta, pero no va a ganar de todos modos.

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

Define las funciones A(aplicar), M(mapa), N(anidar), R(rango), T(tabla) y F(plegar), junto con un par de funciones auxiliares. Tespera una lista de dos enteros para su segundo argumento.

Tinylisp ni siquiera tiene construcciones de bucle; todo se logra utilizando la recursividad. Varias de estas funciones no son recursivas de la cola , por lo que si las llama en listas grandes, probablemente arruinarán la pila de llamadas. Todos podrían implementarse con recursión de cola ... pero tomaría más bytes, y este es el código de golf.

Aquí hay una versión ampliada con espacios en blanco y palabras reales para los nombres, que deberían ser bastante legibles si está familiarizado con Lisp. (He alias la mayoría de las construcciones de tinylisp excepto q(cita) y i(si)).

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

Explicación adicional disponible a pedido.

Salida de muestra

Utiliza el entorno REPL de mi implementación de referencia. Usé q(cita) para la función unaria y s(resta) como la función binaria para estos ejemplos, así como la función @(definida en este código) que devuelve una lista de sus argumentos.

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
fuente
2

Python 2.x: 450,6 bytes (493 bytes antes del 10% de descuento)

Respuesta de golf:

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

Esta pregunta fue divertida. Decidí escribir mis funciones sin usar los equivalentes de Python (aunque eso podría haber sido un vacío legal válido) y escribir las funciones como si Python soportara la recursión de cola. Para que esto funcione, utilicé muchos parámetros opcionales que permiten que las llamadas requeridas sigan funcionando.

A continuación tengo listados sin golf para cada función.

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

Tenga en cuenta que esta función requiere que el pasado functionpueda representar múltiples argumentos de forma variable. Otro enfoque habría sido exigir que la función siempre recibiera una lista única, pero eso habría requerido que las funciones aprobadas pudieran interpretar listas de argumentos. Hubo suposiciones de cualquier manera, así que elegí la que mejor se adaptaba al resto del sistema.

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

Aquí hay una salida de muestra usando las siguientes funciones auxiliares:

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
fuente
Wow, se ve muy bien!
WizardOfMenlo
Eso parece un sentido sesgado de la estética; ) Siempre me resulta divertido ver Python golfizado desde que el primer libro de Python que leí habló sobre cómo Python impone la legibilidad.
sadakatsu
De hecho, tengo un sentido estético sesgado :)
WizardOfMenlo
Estoy confundido por los puntajes de otras personas. Tomé el 10% de la puntuación de cada una de las funciones requeridas que no usaban un bucle (que eran todas), pero otras personas tomaron el 10% de la puntuación completa para cada función que no usaba un bucle (que puede ser hasta 60% de descuento). ¿Cuál es el enfoque correcto?
sadakatsu
La tuya es la forma correcta de ir, tenía una expectativa poco realista y por lo que inicialmente tenía en cuenta el enfoque de 60%, pero ahora creo que el 10% será más estimulante y el más justo entre los dos
WizardOfMenlo
2

Ceilán, 370 * 0.9 = 333364 * 0.9 = 327.4

La mayoría de esas funciones ya están disponibles en el paquete de idioma de Ceylon (aunque a veces con una firma un poco diferente), pero las estamos definiendo aquí como se solicita en la pregunta.

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

En realidad, solo dos de las funciones ( ty f) están utilizando la recursividad (sobre listas y enteros, respectivamente), las otras se basan en ellas. (Aplicar es un poco atípico, realmente no se relaciona con los demás).

Interpreto "Lista" como el tipo secuencial de Ceylon, que es una secuencia de elementos ordenada inmutable (posiblemente vacía). [R*]significa Sequential<R>, por alguna razón, también podemos escribirlo R[], que es un byte más corto.

Un tipo de función es Callable<R, A>, donde Aes un tipo de tupla para los argumentos, como [X, Y, Z](es decir, algún subtipo de Anything[]). Como atajo podemos escribir en R(X,Y,Z)lugar de Callable<R,[X,Y,Z]>.

Alias Integercomo Ipara guardar algunos bytes.

Aquí hay una versión formateada (y ligeramente comentada):

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

Usando "bucles"

Table and Map se puede implementar de manera más corta usando bucles (en realidad, una comprensión de secuencia):

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

Aunque no estoy seguro si el uso del ..operador para el rango entero cuenta como una función incorporada. Si esto está permitido, el código resultante es este, longitud 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]);

(Podría hacerse aún más corto definiendo r(I i) => 1..i, dando como resultado una puntuación de 301. Aunque eso se parece aún más a hacer trampa).

Si ..no está permitido, tendremos que implementarlo nuevamente. Podemos usar estas implementaciones para ry t(con lo manterior):

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

Esto da como resultado 348 bytes, mejor que la versión completamente recursiva, pero no después de aplicar la bonificación.

Paŭlo Ebermann
fuente
0

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

PD: No sé lo que estás considerando como un 'bucle' en este contexto, solo apliqué el bono después de que OP me lo dijo y lo eliminaré si 2-3 usuarios adicionales dicen estas funciones de colección e iteradores son bucles y eso no merezco la bonificación. Además, si desea llamarme sobre mi uso de 1..it, hágalo y lo reelaboraré / actualizaré mi 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

Ejemplo de entrada / salida

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)

Salida

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]

Pruébelo usted mismo: https://groovyconsole.appspot.com/edit/5203951758606336

Urna de pulpo mágico
fuente
Esto técnicamente no usa bucles, ¡así que recuerda la bonificación! De lo contrario, gran respuesta!
WizardOfMenlo
¿Técnicamente no hay bucles? ¡¿De Verdad?! .cada {} .times {} .collect {} son iteradores.
Urna de pulpo mágico