Hagamos Diet Haskell

21

Haskell tiene tuplas que se pueden escribir como

(a,b,c)

Sin embargo, esto es solo azúcar sintáctico para

(,,)a b c

En general, se puede formar una n tupla con n-1 , s entre (... )seguido de sus elementos separados por espacios. Por ejemplo, la 7-tupla, (1,2,3,4,5,6,7)puede estar formada por

(,,,,,,)1 2 3 4 5 6 7

Como Haskell no tiene 1-tuplas, no se pueden formar. Tampoco será responsable de las tuplas vacías.

Las tuplas anidadas se pueden formar usando parens para anular el orden de las operaciones.

((1,2),3) == (,)((,)1 2)3

Como parte de nuestra búsqueda para eliminar todo el azúcar sintáctico de Haskell, le pediré que escriba un programa que elimine también el azúcar sintáctico de las tuplas de Haskell.

Su programa debe tomar una tupla, una matriz o una cadena que represente una tupla azucarada y debe generar una cadena que represente una tupla "sin azúcar". Las tuplas de entrada solo contendrán enteros positivos u otras tuplas.

Como estamos jugando al golf aquí, su rendimiento debe ser corto. No debe contener innecesarios

  • Espacios Los espacios deben usarse solo para separar los argumentos de las funciones de una tupla y no deben aparecer después de un )o antes de un(

  • Paréntesis. Los paréntesis deben usarse solo al formar funciones de tupla o al anidar tuplas.

Esta es una pregunta de , por lo que las respuestas se puntuarán en bytes con menos bytes mejor.

Casos de prueba

(1,2)     -> (,)1 2
(1,2,3)   -> (,,)1 2 3
((1,2),3) -> (,)((,)1 2)3
(1,2,3,4) -> (,,,)1 2 3 4
(1,(2,3)) -> (,)1((,)2 3)
(10,1)    -> (,)10 1
Asistente de trigo
fuente
Si no me falta nada, ¿cubren 1-tuplas pero no tuplas vacías ...? ¿Son válidas las tuplas vacías de entrada?
totalmente humano
3
@totallyhuman No tienes que manejar tuplas vacías.
Wheat Wizard
El quinto caso de prueba tiene un extra,
H.PWiz
2
También por "números" quieres decir "enteros positivos"?
Erik the Outgolfer
2
Casos de prueba sugeridos: ((1,(2,3)),4,(5,6))y (1,(2,3),4).
Ørjan Johansen

Respuestas:

17

Haskell , 169148 bytes

init.tail.fst.([]%)
p:k="(,"
l%('(':r)|(y,x:s)<-[]%r,m<-y:l=last$m%(p:s):[(p:p:(l>>k)++x:foldl(\r x->x++[' '|x>k,r>k]++r)[x]m,s)|x<',']
l%r=lex r!!0

Pruébalo en línea! Toma la tupla como una cuerda. init.tail.fst.([]%)Es la función principal anónima. Úselo a, por ejemplo, fy use like f "(3,(14,1),4,7)", que produce "(,,,)3((,)14 1)4 7".

¿Por qué no se proporciona la entrada como una tupla de Haskell? Como Haskell está fuertemente tipado, una tupla (1,2)tiene tipo (Int,Int)1 y una tupla (1,(2,3))tiene tipo (Int,(Int,Int)). Por lo tanto, una función que acepta el primer tipo de tupla no se puede aplicar al segundo tipo, y especialmente no puede haber ninguna función que tome una tupla 2 arbitraria .

Explicación:

  • p:k="(,"es una forma corta para asignar pa '('y ka ",".
  • (%)es la función de análisis y conversión recursiva. El primer argumento es una lista de entradas de tuplas ya analizadas, el segundo argumento es el resto de la cadena original. Cada llamada devuelve una tupla de la tupla convertida actual (como una cadena y entre paréntesis) y el resto de la cadena.
    • l%('(':r)Si la cadena comienza con un corchete de apertura, debemos analizar una nueva entrada de tupla.
      (y,x:s)<-[]%rAplicamos recursivamente %y obtenemos una entrada de tupla yy la cadena restante se divide en el siguiente carácter xy el resto de la cadena s.
      m<-y:lAgregamos la nueva entrada ya la lista actual de entradas ya encontradas ly llamamos al resultado m.
    • El siguiente personaje xahora es una coma ,o un corchete de cierre ). El last$ <B> :[ <A> |x<',']es solo una forma más corta de escribir if x == ')' then <A> else <B>.
    • Entonces, si a ,es el siguiente, debemos analizar de manera recursiva la siguiente entrada: m%(p:s)anteponemos un corchete de apertura para terminar en el caso correcto y pasar la lista de entradas ya encontradas m.
    • Si no x == ')', terminamos la tupla actual y necesitamos hacer la transformación requerida:(p:p:(l>>k)++x:foldl(\r x->x++[' '|x>k,r>k]++r)[x]m,s)
      • p:p:(l>>k)++x:Si hemos encontrado n entradas, entonces mtiene n elementos y y, la lista antes de agregar el elemento encontrado más recientemente, tiene n-1 entradas. Esto es útil ya que necesitamos n-1 , para una ntupla de elemento y l>>kfunciona en listas como "concatenar la lista kconsigo mismo tantas veces como ytenga elementos" . Por lo tanto, esta primera parte produce una cadena como "((,,,)".
      • foldl(\r x->x++[' '|x>k,r>k]++r)[x]mconcatena los elementos de m(en orden inverso, porque al agregar nuevas entradas al frente mmismo se construyó en orden inverso) al tiempo que agrega solo espacios entre dos elementos si ambos son números: [' '|x>k,r>k]verificamos si las entradas actuales xy los rnúmeros se comparan lexicográficamente que ","- si no son los números, que ya son una representación tupla encerrada entre paréntesis, y '(' < ','las bodegas.
    • Si el ajuste de patrones l%('(':r)desde el principio falla, entonces terminamos en la última línea: l%r=lex r!!0. Esto significa que necesitamos analizar un número y devolver el número y el resto de la cadena. Afortunadamente, existe la lexfunción que hace exactamente eso (analiza el siguiente token válido de Haskell, no solo los números). Sin embargo, la tupla resultante está envuelta en una lista, por lo que usamos !!0para obtener el primer elemento de la lista.
  • init.tail.fst.([]%)es la función principal que toma una cadena y se aplica %con una lista vacía. Por ejemplo, para una entrada "(1,2)", aplicando ([]%)rendimientos ("((,)1 2)",""), por lo que la tupla externa y los corchetes deben eliminarse. fstobtiene el primer elemento de la tupla, tailquita el soporte de cierre y initel de apertura.

Editar: ¡ Muchas gracias a @ Ørjan Johansen por jugar al golf un total de 21 bytes !


1 En realidad, el tipo es (Num t1, Num t) => (t, t1) , pero esa es una historia diferente.

2 Ignorando las funciones polimórficas como id , que en realidad no pueden funcionar con su entrada.

Laikoni
fuente
1
Se podría escribir una función polimórfica utilizando una clase de tipos Desugarable, pero habría que declarar instancias Inty todos los tipos de tuplas.
Bergi
1
gse puede acortar foldr1(\x r->x++[' '|x>k,r>k]++r)e inlinear.
Ørjan Johansen
@ Bergi: ... y uno no puede declarar instancias para todos los tipos de tuplas . :-) (Pruebe: show (1,2,3,4,5,6,7,8,9,0,1,2,3,4,5)en GHCi, luego agregue un ,6al final e intente nuevamente.)
wchargin
1
Mejora de la línea para seis bytes más: use m<-y:l, doble a la izquierda en lugar de a la derecha y use [x]como valor inicial. Pruébalo en línea!
Ørjan Johansen
1
fpuede ser anónima: init.tail.fst.([]%).
Ørjan Johansen
11

Haskell 141 bytes138 bytes (Gracias a Ørjan Johansen)

import Language.Haskell.TH
f(TupE l)='(':tail(","<*l)++')':""%l
q%(LitE(IntegerL i):l)=q++show i++" "%l
_%(e:l)='(':f e++')':""%l
_%[]=[]

ftiene tipo Exp -> String.

  • Entrada: una resistencia de plantilla de HaskellExp (es decir, la representación AST estándar de valores de Haskell de tipo arbitrario, básicamente, código de Haskell analizado antes de la verificación de tipo); debe representar una tupla que contenga solo números enteros no negativos y otras tuplas similares.

  • Salida: una cadena que contiene la sintaxis desugared para esa expresión de tupla.

Manifestación:

$ ghci TupDesugar.hs 
GHCi, version 8.3.20170711: http://www.haskell.org/ghc/  :? for help
Loaded GHCi configuration from /home/sagemuej/.ghc/ghci.conf
Loaded GHCi configuration from /home/sagemuej/.ghci
[1 of 1] Compiling Main             ( TupDesugar.hs, interpreted )
Ok, 1 module loaded.
*Main> :set -XTemplateHaskell -XQuasiQuotes
*Main> f <$> runQ [|(1,2)|]
"(,)1 2"
*Main> f <$> runQ [|(1,2,3)|]
"(,,)1 2 3"
*Main> f <$> runQ [|((1,2),3)|]
"(,)((,)1 2)3"
*Main> f <$> runQ [|(1,2,3,4)|]
"(,,,)1 2 3 4"
*Main> f <$> runQ [|(1,(2,3))|]
"(,)1((,)2 3)"
*Main> f <$> runQ [|(10,1)|]
"(,)10 1"
dejó de girar en sentido antihorario
fuente
2
Puede cambiar ")"++a ')':dos lugares y guardar el espacio después tailde moverlo fuera del paréntesis.
Ørjan Johansen
7

Haskell , 119 bytes

data T=I Int|U[T]
f(U t)="(("++init(t>>",")++')':foldr(\x y->f x++[' '|f x>",",y>","]++y)")"t
f(I n)=show n
init.tail.f

Pruébalo en línea! Utiliza un tipo de datos personalizado Tpara representar tuplas, es decir, una tupla ((1,2),3)se representa como U[U[I 1,I 2],I 3]. Ejemplo de uso: init.tail.f $ U[U[I 1,I 2],I 3]rendimientos (,)((,)1 2)3.

Laikoni
fuente
6

Python 2 , 110 bytes

def f(t):
 s='('+','*~-len(t)+')';c=0
 for i in t:
	try:s+=' '*c+`+i`;c=1
	except:s+='(%s)'%f(i);c=0
 return s

Pruébalo en línea!

Toma a tuple.

Erik el Outgolfer
fuente
4

GNU sed, 149 82 + 2 = 84 bytes

+2 bytes para la -rbandera.

y/(),/<>'/
:
s/([^<>']+)'/,\1 /
t
s/ ?<(,+)([^>]+)>/((\1)\2)/
t
s/^.|(\)) |.$/\1/g

Pruébalo en línea!

Explicación

y/(),/<>'/                   # Replace parens and commas with brackets and apostrophes
:
  s/([^<>']+)'/,\1 /.          # Remove each apostrophe and insert comma after <
  t                            # Branch to : if substitution was made
  s/ ?<(,+)([^>]+)>/((\1)\2)/  # Change <,,,...> to ((,,,)...)
  t                            # Branch to : if substitution was made
s/^.|(\)) |.$/\1/g           # Remove outermost ()s and extra spaces
Jordán
fuente
Esto falla en algunos casos más complicados: ((1,(2,3)),4,(5,6))y (1,(2,3),4).
Ørjan Johansen
@ ØrjanJohansen Buena captura. Echaré un vistazo después del desayuno.
Jordan
3

JavaScript, 75 bytes

f=a=>`(${t=a.map(x=>'')})${a.map(v=>t=1/v?1/t?' '+v:v:`(${f(v)})`).join``}`

Matriz de entrada de número | matriz, cadena de salida.

Gracias a Neil, ahorre 2 bytes

tsh
fuente
(1/t?' ':0)+vpuede ser 1/t?' '+v:v.
Neil
2

Mathematica, 94 bytes

{"(",","&/@Most@#,")",c=1>0;(xIf[j=ListQ@x,c=j;"("<>#0@x<>")",If[c,c=j;x," "<>x]])/@#}<>""&

Contiene una función U+F4A1incorporada no imprimible Function.

Toma un Listnúmero entero Strings. Si esto no está permitido, esto se puede solucionar agregando 10 bytes más (esta versión toma una Listde Lists / Integers):

{"(",","&/@Most@#,")",c=1>0;(xIf[j=ListQ@x,c=j;"("<>#0@x<>")",If[c,c=j;""," "]<>ToString@x])/@#}<>""&
JungHwan Min
fuente
2

Pip , 45 bytes

{Y"()"b:yJ',X#a-1Fcab.:c>0?s.cyJ(fc)bR") "')}

Esta es una función que toma una lista como argumento. Pruébalo en línea!

Versión comentada

; Define an anonymous function (the argument is available inside as the variable a)
{
  ; Yank the string "()" into y variable
  Y "()"
  ; Create a string of len(a)-1 commas, join y on it, and assign to b
  b: y J ',X#a-1
  ; For each item c in a
  F c a
    ; Concatenate to b the following expression
    b .:
      ; Is c integer or list?
      ; (If c is a positive integer, c>0 is true; but if c is a list, c>0 is false)
      c>0 ?
        ; If c is integer, concatenate space followed by c
        s.c
        ; If c is list, call function recursively on c and use the result to join y
        yJ(fc)
  ; Replace ") " with ")" in b and return the resulting string
  b R ") " ')
}
DLosc
fuente
2

JavaScript (ES6), 88 84 bytes

f=a=>a.reduce((s,e)=>s+=e[0]?`(${f(e)})`:/\)$/.test(s)?e:' '+e,`(${[...a].fill``})`)

Toma una matriz de enteros y matrices. Editar: se guardó 1 byte usando en s+=lugar de dos usos separados de s+. Ahorré otros 3 bytes ahora que puedo simplificar el ternario interno. Si robo las ideas de @ tsh, puedo reducirlo a 76 bytes:

f=a=>a.reduce((s,e)=>s+=t=1/e?1/t?' '+e:e:`(${f(e)})`,`(${t=a.map(_=>``)})`)
Neil
fuente
Your program should take either a tuple or a string representing a sugary tupleSupongo que una matriz de matrices / enteros debería estar bien.
JungHwan Min
1
Claro que está permitido
Wheat Wizard
1

R, 316 bytes?

(Tengo que salir y no estoy seguro de la forma correcta de contar bytes ... además, no es una gran solución, pero quería publicarlo ya que pasé el tiempo haciéndolo ...)

p=function(x){
x=eval(parse(text=gsub("\\(","list(",x)))
f=function(j,r=T){
p=paste
s=if(r){"("}else{"(("}
o=paste0(s,p(rep(",",length(j)-1),collapse=""),")")
n=lengths(j)
for(i in seq_along(n)){
v=j[[i]]
if(n[i]>1){v=f(v,F)}
o=p(o,v)}
if(!r){o=p(o,")")}
o=gsub(" *([()]) *","\\1",o)
return(o)}
f(x)
}

Casos de prueba:

> p("(1,2)")
[1] "(,)1 2"
> p("(1,2,3)")
[1] "(,,)1 2 3"
> p("((1,2),3)")
[1] "(,)((,)1 2)3"
> p("(1,2,3,4)")
[1] "(,,,)1 2 3 4"
> p("(1,(2,3))")
[1] "(,)1((,)2 3)"
> p("(10,1)")
[1] "(,)10 1"
Razón
fuente
Son 301 bytes: ¡ Pruébelo en línea!
Laikoni
2
Golfizado a 261 bytes . Dejaría una explicación de lo que cambié, pero irónicamente, también tengo que ir ... Pero +1, no pude entender esto en absoluto; ¡Buen trabajo!
Giuseppe
0

JavaScript (ES6), 72 bytes

f=(a,b="",c="")=>a.map?b+"("+a.map(x=>'')+")"+a.map(x=>f(x,"(",")"))+c:a

Entrada: matriz que contiene números y / o matrices

Salida: cadena

Uso: f ([...])

Completa todos los casos de prueba, las mejoras son bienvenidas

ES6_es_awesome
fuente
0

C, 308 o 339 bytes

#include <ctype.h>
#define p putchar
f(s,e,c,i,l)char*s,*e,*c;{i=1,l=40;if(*s++==l){p(l);for(c=s;i;i+=*c==l,i-=*c==41,i+*c==45&&p(44),c++);p(41);}for(;s<e;s=c){for(i=0;isdigit(*s);s+=*s==44)for(i&&p(32),i=1;isdigit(*s);s++)p(*s);*s==l&&p(l);for(c=s,i=1;++c,c<=e&&i;i+=*c==l)i-=*c==41;f(s,c-1);*s==l&&p(41);}}
#define g(x) f(x, x+strlen(x))

308 o 339 bytes, dependiendo de si se permite o no pasar un puntero al final de la cadena de entrada; la última línea solo está allí para permitir pasar un literal de cadena directamente sin tener que calcular su longitud.

Explicación

Un algoritmo bastante simple. Cuenta el número de comas en la profundidad actual, las imprime como un constructor de tuplas, luego sigue con los argumentos de la tupla, escapado (espacios entre números, tuplas anidadas entre paréntesis), recursivamente.

#include <stdio.h>
#include <ctype.h>
typedef enum { false, true } bool;

void tup2ptsfree(char *s, char *e)
{
  int depth;
  char *c;

  if (*s++ == '(') { /* If we are at the start of a tuple, write tuple function `(,,,)` (Otherwise, we are at a closing bracket or a comma) */
    putchar('(');
    /* do the search for comma's */
    c=s; /* probe without moving the original pointer */
    for (depth=1; depth != 0; c++) {
      if (*c == '(') depth++;
      if (*c == ')') depth--;
      if (*c == ',' && depth == 1) putchar(','); /* We have found a comma at the right depth, print it */
    }
    putchar(')');
  }
  while (s < e) { /* The last character is always ')', we can ignore it and save a character. */
    bool wroteNumber;
    for (wroteNumber=false; isdigit(*s); wroteNumber = true) {
      if (wroteNumber) p(' ');           /* If this is not the first number we are writing, add a space */
      while (isdigit(*s)) putchar(*s++); /* Prints the entire number */
      if (*s == ',') s++;                /* We found a ',' instead of a ')', so there might be more numbers following */
    }
    /* Add escaping parenthesis if we are expanding a tuple (Using a small if statement instead of a large branch to prevent doing the same thing twice, since the rest of the code is essentially the same for both cases). */
    if (*s == '(') putchar('(');
    /* Find a matching ')'... */
    c=s+1;
    for (depth=1; c <= e && depth != 0; c++) {
      if (*c == '(') depth++;
      if (*c == ')') depth--;
    }
    /* Found one */
    /* Note how we are looking for a matching paren twice, with slightly different parameters. */
    /* I couldn't find a way to golf this duplication away, though it might be possible. */
    /* Expand the rest of the tuple */
    tup2ptsfree(s, c-1);
    /* idem */
    if (*s == '(') putchar(')');
    /* Make the end of the last expansion the new start pointer. */
    s=c;
  }
}

#define h(x) tup2ptsfree(x, x+strlen(x))

Casos de prueba y aplicación

#include <stdio.h>

#define ARRAYSIZE(arr) (sizeof(arr)/sizeof(*arr))
static char *examples[] = {
  "(1,2)",
  "(10,1)",
  "(1,2,3)",
  "(1,2,3,4)",
  "((1,2),3)",
  "(1,(2,3))",
  "(1,(2,3),4)",
  "((1,2),(3,4))",
  "((1,(2,3)),4,(5,6))",
  "((1,((2,3), 4)),5,(6,7))",
  "(42,48)",
  "(1,2,3,4,5,6,7)"
};

int main(void)
{
  int i;
  for (i=0; i < ARRAYSIZE(examples); i++) {
    printf("%-32s | \"", examples[i]);
    g(examples[i]); /* Test with golfed version */
    printf("\"\n");
    printf("%-32s | \"", examples[i]);
    h(examples[i]); /* Test with original version */
    printf("\"\n");
  }
}
YoYoYonnY
fuente