Zróbmy Diet Haskell

21

Haskell ma krotki, które można zapisać jako

(a,b,c)

Jest to jednak tylko cukier syntaktyczny

(,,)a b c

Ogólnie przyjętą n krotka mogą być utworzone z n-1 , S pomiędzy (... )następnie jego elementów oddzielonych przestrzeni. Na przykład 7-krotkę (1,2,3,4,5,6,7)można utworzyć przez

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

Ponieważ Haskell nie ma 1-krotek, nie można ich utworzyć. Nie będziesz również ponosić odpowiedzialności za puste krotki.

Zagnieżdżone krotki można utworzyć za pomocą parens, aby zastąpić kolejność operacji.

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

W ramach naszego dążenia do usunięcia całego cukru syntaktycznego z Haskell poproszę cię o napisanie programu, który usunie również cukier syntaktyczny z krotek Haskella.

Twój program powinien pobrać krotkę, tablicę lub łańcuch reprezentujący krotkę cukrową i powinien wypisać łańcuch reprezentujący krotkę „bez cukru”. Krotki wejściowe zawsze zawierają tylko dodatnie liczby całkowite lub inne krotki.

Ponieważ tutaj gramy w golfa, twój wynik powinien być krótki. Nie powinien zawierać niepotrzebnych

  • Przestrzenie. Spacje powinny być używane tylko do oddzielania argumentów funkcji krotki i nie powinny pojawiać się po a )lub przed a(

  • Zdanie wtrącone. Nawiasów należy używać tylko podczas tworzenia funkcji krotek lub zagnieżdżania krotek.

To jest pytanie w więc odpowiedzi będą liczone w bajtach, przy czym mniej bajtów będzie lepszych.

Przypadki testowe

(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
Kreator pszenicy
źródło
Jeśli niczego mi nie brakuje, to pokrywasz 1-krotkę, ale nie pustą krotkę ..? Czy puste krotki są prawidłowe?
całkowicieludzki
3
@totallyhuman Nie musisz obsługiwać pustych krotek.
Wheat Wizard
Piąty przypadek testowy ma dodatkowy,
H.PWiz
2
Czy przez „liczby” masz na myśli „dodatnie liczby całkowite”?
Erik the Outgolfer,
2
Sugerowane przypadki testowe: ((1,(2,3)),4,(5,6))i (1,(2,3),4).
Ørjan Johansen

Odpowiedzi:

17

Haskell , 169 148 bajtów

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

Wypróbuj online! Bierze krotkę jako ciąg. init.tail.fst.([]%)to anonimowa główna funkcja. Powiąż go np. fI użyj like f "(3,(14,1),4,7)", który daje "(,,,)3((,)14 1)4 7".

Dlaczego dane wejściowe nie są dostarczane jako krotka Haskell? Ponieważ Haskell jest mocno wpisany, krotka (1,2)ma typ (Int,Int)1, a krotka (1,(2,3))ma typ (Int,(Int,Int)). Zatem funkcja, która akceptuje pierwszy rodzaj krotki, nie może być zastosowana do drugiego rodzaju, a zwłaszcza nie może być żadnej funkcji, która przyjmuje dowolną krotkę 2 .

Wyjaśnienie:

  • p:k="(,"to krótki sposób przypisania pdo '('i kdo ",".
  • (%)jest rekursywną funkcją analizującą i przetwarzającą. Pierwszy argument jest listą już przeanalizowanych wpisów krotek, drugi argument jest resztą oryginalnego ciągu. Każde wywołanie zwraca krotkę aktualnie przekonwertowanej krotki (jako ciąg i ujęte w nawiasy kwadratowe) oraz resztę ciągu.
    • l%('(':r)Jeśli ciąg zaczyna się od nawiasu otwierającego, musimy przeanalizować nowy wpis krotki.
      (y,x:s)<-[]%rStosujemy rekurencyjnie %i otrzymujemy krotkę, ya pozostały ciąg dzieli się na następny znak xi resztę ciągu s.
      m<-y:lDodajemy nowy wpis ydo bieżącej listy już znalezionych wpisówl i wywołujemy wynik m.
    • Następnym znakiem xjest teraz przecinek ,lub nawias zamykający ). To last$ <B> :[ <A> |x<',']tylko krótszy sposób pisaniaif x == ')' then <A> else <B> .
    • Więc jeśli a ,jest następne, musimy rekursywnie przeanalizować następny wpis: m%(p:s)przygotowujemy nawias otwierający, aby skończyć w odpowiednim przypadku i przekazać listę już znalezionych wpisówm .
    • Jeśli nie x == ')', zakończyliśmy bieżącą krotkę i musimy wykonać wymaganą transformację:(p:p:(l>>k)++x:foldl(\r x->x++[' '|x>k,r>k]++r)[x]m,s)
      • p:p:(l>>k)++x:Jeśli znaleźliśmy n pozycji, to mma n elementów y, a lista przed dodaniem ostatnio znalezionego elementu ma n-1 pozycji. Jest to przydatne, ponieważ potrzebujemy n-1 , dla nkrotki elementów i l>>kdziała na listach jako „łącząc listę kze sobą tyle razy, ile yma elementów” . W ten sposób pierwsza część daje ciąg znaków "((,,,)".
      • foldl(\r x->x++[' '|x>k,r>k]++r)[x]mkonkatenuje elementy m(w odwrotnej kolejności, ponieważ dodając nowe wpisy do samego frontu mskonstruowano w odwrotnej kolejności), dodając tylko spacje między dwoma elementami, jeśli są one liczbami: [' '|x>k,r>k]sprawdzamy, czy bieżące wpisy xi rliczby są porównywane leksykograficznie je do ","- jeśli nie są liczbami, są już reprezentacją krotki ujętą w nawiasach i '(' < ','zawiera.
    • Jeśli wzór mecz l%('(':r)na samym początku nie powiedzie, wtedy kończy się w ostatnim wierszu: l%r=lex r!!0. Oznacza to, że musimy przeanalizować liczbę i zwrócić liczbę oraz resztę ciągu. Na szczęście istnieje lexfunkcja, która właśnie to robi (analizuje następny prawidłowy token Haskell, a nie tylko liczby). Jednak wynikowa krotka jest zawijana w listę, więc używamy, !!0aby uzyskać pierwszy element listy.
  • init.tail.fst.([]%)jest główną funkcją, która pobiera ciąg znaków i stosuje %się do niego pustą listę. Np. Dla danych wejściowych "(1,2)", stosując ([]%)plony ("((,)1 2)",""), więc krotkę zewnętrzną i wsporniki należy usunąć. fstpobiera pierwszy element krotki, tailusuwa wspornik zamykający i initotwierający.

Edycja: Wielkie podziękowania dla @ Ørjan Johansen za grę w golfa w sumie 21 bajtów !


1 Właściwie jest to typ (Num t1, Num t) => (t, t1) , ale to inna historia.

2 Ignorowanie funkcji polimorficznych, takich jak id , które nie mogą faktycznie działać z ich danymi wejściowymi.

Laikoni
źródło
1
Można napisać funkcję polimorficzną przy użyciu klasy Desugarable, ale trzeba by zadeklarować instancje Inti wszystkie typy krotek.
Bergi
1
gmożna skrócić foldr1(\x r->x++[' '|x>k,r>k]++r)i wstawić.
Ørjan Johansen
@Bergi:… i nie można deklarować instancji dla naprawdę wszystkich typów krotek . :-) (Spróbuj: show (1,2,3,4,5,6,7,8,9,0,1,2,3,4,5)w GHCi, a następnie dodaj ,6na końcu i spróbuj ponownie.)
wchargin
1
Poprawianie wstawiania dla kolejnych sześciu bajtów: Użyj m<-y:l, złóż w lewo zamiast w prawo i użyj [x]jako wartości początkowej. Wypróbuj online!
Ørjan Johansen
1
fmoże być anonimowy: init.tail.fst.([]%).
Ørjan Johansen
11

Haskell, 141 bajtów 138 bajtów (dzięki Ø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
_%[]=[]

fma typ Exp -> String.

  • Dane wejściowe: szablonExp Reakcja Haskell (tj. Standardowa reprezentacja AST wartości Haskell dowolnego typu - w zasadzie przeanalizowany kod Haskell przed sprawdzeniem typu); musi reprezentować krotkę zawierającą tylko nieujemne liczby całkowite i inne takie krotki.

  • Dane wyjściowe: ciąg znaków zawierający zdezaktualizowaną składnię tego wyrażenia krotkowego.

Próbny:

$ 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"
przestał się obracać w lewo
źródło
2
Możesz zmienić ")"++na ')':w dwóch miejscach i zaoszczędzić miejsce po tail, przenosząc je poza nawiasy.
Ørjan Johansen
7

Haskell , 119 bajtów

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

Wypróbuj online! Używa niestandardowego typu danych Tdo reprezentowania krotek, czyli krotka ((1,2),3)jest reprezentowana jako U[U[I 1,I 2],I 3]. Przykładowe użycie: init.tail.f $ U[U[I 1,I 2],I 3]daje (,)((,)1 2)3.

Laikoni
źródło
6

Python 2 , 110 bajtów

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

Wypróbuj online!

Trwa tuple.

Erik the Outgolfer
źródło
4

GNU sed, 149 82 + 2 = 84 bajtów

+2 bajty dla -rflagi.

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

Wypróbuj online!

Wyjaśnienie

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
Jordania
źródło
Nie udaje się to w niektórych bardziej skomplikowanych przypadkach: ((1,(2,3)),4,(5,6))i (1,(2,3),4).
Ørjan Johansen
@ ØrjanJohansen Good catch. Zajmę się po śniadaniu.
Jordan
3

JavaScript, 75 bajtów

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

Tablica wejściowa liczba | tablica, ciąg wyjściowy.

Dzięki Neilowi ​​zaoszczędź 2 bajty

tsh
źródło
(1/t?' ':0)+vmoże być 1/t?' '+v:v.
Neil
2

Mathematica, 94 bajty

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

Zawiera U+F4A1wbudowaną Functionfunkcję niedrukowalną .

Przyjmuje Listliczbę całkowitą String. Jeżeli nie jest to dozwolone, to może być ustalone przez dodanie kolejnych 10 bajtów (Wersja ta trwa Listod Liste / Integere):

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

Pip , 45 bajtów

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

Jest to funkcja, która przyjmuje listę jako argument. Wypróbuj online!

Skomentowana wersja

; 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
źródło
2

JavaScript (ES6), 88 84 bajtów

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

Przyjmuje tablicę liczb całkowitych i tablic. Edycja: Zapisano 1 bajt, używając s+=zamiast dwóch osobnych zastosowań s+. Zaoszczędziłem kolejne 3 bajty teraz, gdy mogę uprościć wewnętrzny trójskładnik. Jeśli kradnę pomysły @ tsh, mogę sprowadzić je do 76 bajtów:

f=a=>a.reduce((s,e)=>s+=t=1/e?1/t?' '+e:e:`(${f(e)})`,`(${t=a.map(_=>``)})`)
Neil
źródło
Your program should take either a tuple or a string representing a sugary tupleZakładam, że tablica tablic / liczb całkowitych powinna być w porządku.
JungHwan Min
1
Pewnie, że jest to dozwolone
Wheat Wizard
1

R, 316 bajtów?

(Muszę wyjść i nie jestem pewien, jaki jest właściwy sposób liczenia bajtów ... plus nie jest to świetne rozwiązanie, ale chciałem to opublikować, ponieważ spędziłem czas na tworzeniu ...)

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

Przypadki testowe:

> 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
źródło
Ma 301 bajtów: wypróbuj online!
Laikoni
2
Grał w golfa do 261 bajtów . Zostawiłbym wyjaśnienie tego, co zmieniłem, ale jak na ironię, muszę też iść ... Ale +1, nie mogłem w ogóle owinąć głowy; dobra robota!
Giuseppe,
0

JavaScript (ES6), 72 bajty

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

Dane wejściowe: tablica zawierająca liczby i / lub tablice

Wyjście: ciąg

Zastosowanie: f ([...])

Wykonuje wszystkie przypadki testowe, mile widziane ulepszenia

ES6_is_awesome
źródło
0

C, 308 lub 339 bajtów

#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 lub 339 bajtów, w zależności od tego, czy dozwolone jest przekazywanie wskaźnika na koniec ciągu wejściowego; ostatnia linia jest tam tylko po to, aby pozwolić na przekazanie literału łańcucha bezpośrednio, bez konieczności obliczania jego długości.

Wyjaśnienie

Dość prosty algorytm. Zlicza przecinki na bieżącej głębokości, drukuje je jako konstruktor krotki, a następnie argumenty krotki, ucieka (spacje między liczbami, zagnieżdżone krotki między nawiasami), rekurencyjnie.

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

Przypadki testowe i zastosowanie

#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");
  }
}
Rrrrrr
źródło