Faisons Diet Haskell

21

Haskell a des tuples qui peuvent être écrits comme

(a,b,c)

Mais ce n'est que du sucre syntaxique pour

(,,)a b c

En général, un n tuple peut être formé avec n-1 , s entre (... )suivi de ses éléments séparés par des espaces. Par exemple, le 7-tuple, (1,2,3,4,5,6,7)peut être formé par

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

Étant donné que Haskell n'a pas de tuples 1, ils ne peuvent pas être formés. Vous ne serez pas non plus tenu responsable des tuples vides.

Les tuples imbriqués peuvent être formés à l'aide de parens pour remplacer l'ordre des opérations.

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

Dans le cadre de notre quête pour supprimer tout le sucre syntaxique de Haskell, je vais vous demander d'écrire un programme qui supprime également le sucre syntaxique des tuples de Haskell.

Votre programme doit prendre un tuple, un tableau ou une chaîne représentant un tuple sucré et doit produire une chaîne représentant un tuple "sans sucre". Les tuples en entrée ne contiendront que des entiers positifs ou d'autres tuples.

Puisque nous jouons ici, votre sortie devrait être courte. Il ne doit pas contenir de

  • Les espaces. Les espaces doivent être utilisés uniquement pour séparer les arguments d'une fonction de tuple et ne doivent pas apparaître après a )ou avant a(

  • Parenthèses. Les parenthèses ne doivent être utilisées que lors de la création de fonctions de tuple ou lors de l'imbrication de tuples.

C'est une question de donc les réponses seront notées en octets avec moins d'octets étant mieux.

Cas de test

(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
Assistant de blé
la source
Si rien ne me manque, vous couvrez 1-tuples mais pas des tuples vides ..? Les tuples vides sont-ils une entrée valide?
2017 totalement humain
3
@totallyhuman Vous n'avez pas à gérer de tuples vides.
Wheat Wizard
Le 5ème cas de test a un supplément,
H.PWiz
2
Par «nombres», voulez-vous également dire «entiers positifs»?
Erik the Outgolfer le
2
Cas de test suggérés: ((1,(2,3)),4,(5,6))et (1,(2,3),4).
Ørjan Johansen

Réponses:

17

Haskell , 169 148 octets

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

Essayez-le en ligne! Prend le tuple sous forme de chaîne. init.tail.fst.([]%)est la fonction principale anonyme. Liez-le à eg fet utilisez like f "(3,(14,1),4,7)", qui donne "(,,,)3((,)14 1)4 7".

Pourquoi l'entrée n'est-elle pas fournie en tant que tuple Haskell, demandez-vous? Haskell étant fortement typé, un tuple (1,2)a le type (Int,Int)1 et un tuple (1,(2,3))a le type (Int,(Int,Int)). Ainsi une fonction qui accepte le premier type de tuple ne peut pas être appliquée au second type, et surtout il ne peut y avoir de fonction qui prend un tuple arbitraire 2 .

Explication:

  • p:k="(,"est un moyen court d’affecter pà '('et kà ",".
  • (%)est la fonction d'analyse et de conversion récursive. Le premier argument est une liste d'entrées de tuple déjà analysées, le deuxième argument est le reste de la chaîne d'origine. Chaque appel renvoie un tuple du tuple converti actuel (sous forme de chaîne et placé entre crochets) et le reste de la chaîne.
    • l%('(':r)Si la chaîne commence par une parenthèse ouvrante, nous devons analyser une nouvelle entrée de tuple.
      (y,x:s)<-[]%rNous appliquons %et obtenons récursivement une entrée de tuple yet la chaîne restante divisée en le caractère suivant xet le reste de la chaîne s.
      m<-y:lNous ajoutons la nouvelle entrée yà la liste actuelle des entrées déjà trouvées let appelons le résultat m.
    • Le caractère suivant xest maintenant soit une virgule, ,soit une parenthèse fermante ). C'est last$ <B> :[ <A> |x<',']juste une façon plus courte d'écrire if x == ')' then <A> else <B>.
    • Donc, si a ,est le suivant, nous devons analyser récursivement la prochaine entrée: m%(p:s)nous ajoutons une parenthèse ouvrante afin de nous retrouver dans le bon cas et de passer la liste des entrées déjà trouvées m.
    • Sinon x == ')', nous avons terminé le tuple actuel et devons effectuer la transformation requise:(p:p:(l>>k)++x:foldl(\r x->x++[' '|x>k,r>k]++r)[x]m,s)
      • p:p:(l>>k)++x:Si nous avons trouvé n entrées, il ma alors n éléments et y, la liste avant d'ajouter l'élément le plus récemment trouvé, a n-1 entrées. Cela est pratique car nous avons besoin de n-1 , pour un ntuple d'élément et l>>kfonctionne sur des listes comme "concaténer la liste kavec elle-même autant de fois que yd'éléments" . Ainsi, cette première partie donne une chaîne comme "((,,,)".
      • foldl(\r x->x++[' '|x>k,r>k]++r)[x]mconcatène les éléments de m(dans l'ordre inverse, car en ajoutant de nouvelles entrées au front mlui-même a été construit dans l'ordre inverse) tout en n'ajoutant que des espaces entre deux éléments s'ils sont tous deux des nombres: [' '|x>k,r>k]nous vérifions si les entrées actuelles xet rsont des nombres en comparant lexicographiquement les à ","- s'ils ne sont pas des nombres, ils sont déjà une représentation de tuple entre crochets, et '(' < ','détient.
    • Si le match de modèle l%('(':r)dès le début échoue, nous nous retrouvons sur la dernière ligne: l%r=lex r!!0. Cela signifie que nous devons analyser un nombre et renvoyer le nombre et le reste de la chaîne. Heureusement, il y a la lexfonction qui fait exactement cela (elle analyse le prochain jeton Haskell valide, pas seulement les nombres). Cependant, le tuple résultant est encapsulé dans une liste, nous utilisons donc !!0pour obtenir le premier élément de la liste.
  • init.tail.fst.([]%)est la fonction principale qui prend une chaîne et s'applique %avec une liste vide. Par exemple, pour une entrée "(1,2)", appliquer des ([]%)rendements ("((,)1 2)",""), de sorte que le tuple externe et les supports doivent être supprimés. fstrécupère le premier élément du tuple, tailsupprime le crochet de fermeture et initle crochet d' ouverture.

Edit: Un grand merci à @ Ørjan Johansen pour avoir joué au golf 21 octets au total !


1 En fait, le type est (Num t1, Num t) => (t, t1) , mais c'est une histoire différente.

2 Ignorer les fonctions polymorphes comme id , qui ne peuvent pas réellement fonctionner avec leur entrée.

Laikoni
la source
1
On pourrait écrire une fonction polymorphe en utilisant une classe de types Desugarable, mais il faudrait déclarer des instances pour Int, et tous les types de tuple.
Bergi
1
gpeut être raccourci foldr1(\x r->x++[' '|x>k,r>k]++r)et intégré.
Ørjan Johansen
@Bergi:… et on ne peut pas déclarer d'instances pour vraiment tous les types de tuple . :-) (Essayez: show (1,2,3,4,5,6,7,8,9,0,1,2,3,4,5)dans GHCi, puis ajoutez un ,6à la fin et réessayez.)
wchargin
1
Amélioration de l'inline pour six octets supplémentaires: utilisez m<-y:l, repliez vers la gauche au lieu de la droite et utilisez [x]comme valeur initiale. Essayez-le en ligne!
Ørjan Johansen
1
fpeut être anonyme: init.tail.fst.([]%).
Ørjan Johansen
11

Haskell, 141 octets138 octets (Merci à Ø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
_%[]=[]

fa un type Exp -> String.

  • Entrée: une ression de modèle HaskellExp (c'est-à-dire la représentation AST standard des valeurs Haskell de type arbitraire - en gros, le code Haskell analysé avant la vérification de type); doit représenter un tuple contenant uniquement des nombres entiers non négatifs et d'autres tuples de ce type.

  • Sortie: une chaîne contenant la syntaxe desugared pour cette expression de tuple.

Démo:

$ 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"
a cessé de tourner dans le sens antihoraire
la source
2
Vous pouvez passer ")"++à ')':deux endroits et économiser l'espace après le tailen le déplaçant hors des parenthèses.
Ørjan Johansen
7

Haskell , 119 octets

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

Essayez-le en ligne! Cela utilise un type de données personnalisé Tpour représenter les tuples, c'est-à-dire qu'un tuple ((1,2),3)est représenté par U[U[I 1,I 2],I 3]. Exemple d'utilisation: init.tail.f $ U[U[I 1,I 2],I 3]rendements (,)((,)1 2)3.

Laikoni
la source
6

Python 2 , 110 octets

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

Essayez-le en ligne!

Prend a tuple.

Erik le Outgolfer
la source
4

GNU sed, 149 82 + 2 = 84 octets

+2 octets pour l' -rindicateur.

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

Essayez-le en ligne!

Explication

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
Jordan
la source
Cela échoue dans certains cas plus compliqués: ((1,(2,3)),4,(5,6))et (1,(2,3),4).
Ørjan Johansen
@ ØrjanJohansen Bonne prise. Je vais regarder après le petit déjeuner.
Jordan
3

JavaScript, 75 octets

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

Tableau d'entrée de nombre | tableau, chaîne de sortie.

Merci à Neil, économisez 2 octets

tsh
la source
(1/t?' ':0)+vpeut être 1/t?' '+v:v.
Neil
2

Mathematica, 94 octets

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

Contient un non imprimable U+F4A1Function fonction intégrée non imprimable .

Prend un Listentier Strings. Si cela n'est pas autorisé, cela peut être corrigé en ajoutant 10 octets supplémentaires (cette version prend un Listde Lists / Integers):

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

Pip , 45 octets

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

Il s'agit d'une fonction qui prend une liste en argument. Essayez-le en ligne!

Version commentée

; 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
la source
2

JavaScript (ES6), 88 84 octets

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

Prend un tableau d'entiers et de tableaux. Modifier: enregistré 1 octet en utilisant s+=au lieu de deux utilisations distinctes de s+. Sauvegardé encore 3 octets maintenant que je peux simplifier le ternaire interne. Si je vole les idées de @ tsh, je peux le ramener à 76 octets:

f=a=>a.reduce((s,e)=>s+=t=1/e?1/t?' '+e:e:`(${f(e)})`,`(${t=a.map(_=>``)})`)
Neil
la source
Your program should take either a tuple or a string representing a sugary tupleJe suppose qu'un tableau de tableaux / entiers devrait convenir.
JungHwan Min
1
Bien sûr, cela est autorisé
Wheat Wizard
1

R, 316 octets?

(Je dois sortir et je ne suis pas sûr de la bonne façon de compter les octets ... en plus, ce n'est pas une excellente solution, mais je voulais le poster car j'ai passé le temps à le faire ...)

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

Cas de test:

> 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"
Dason
la source
C'est 301 octets: essayez-le en ligne!
Laikoni
2
Golfé à 261 octets . Je laisserais une explication pour ce que j'ai changé, mais ironiquement, je dois aussi y aller ... Mais +1, je ne pouvais pas du tout m'envelopper la tête; bon travail!
Giuseppe
0

JavaScript (ES6), 72 octets

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

Entrée: tableau contenant des nombres et / ou des tableaux

Sortie: chaîne

Utilisation: f ([...])

Complète tous les cas de test, améliorations bienvenues

ES6_is_awesome
la source
0

C, 308 ou 339 octets

#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 ou 339 octets, selon que le passage d'un pointeur à la fin de la chaîne d'entrée est autorisé ou non; la dernière ligne n'est là que pour permettre de passer directement un littéral de chaîne sans avoir à calculer sa longueur.

Explication

Un algorithme assez simple. Il compte le nombre de virgules à la profondeur actuelle, les imprime en tant que constructeur de tuple, puis suit les arguments du tuple, échappés (espaces entre les nombres, tuples imbriqués entre parenthèses), récursivement.

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

Cas de test et application

#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
la source