Mari kita membuat Diet Haskell

21

Haskell memiliki tupel yang dapat ditulis sebagai

(a,b,c)

Namun ini hanya gula sintaksis

(,,)a b c

Secara umum n tupel dapat dibentuk dengan n-1 , s antara (... )diikuti oleh unsur-unsurnya dipisahkan oleh spasi. Misalnya 7-tuple, (1,2,3,4,5,6,7)dapat dibentuk oleh

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

Karena Haskell tidak memiliki 1-tupel, mereka tidak dapat dibentuk. Anda juga tidak akan dianggap bertanggung jawab atas tuple kosong.

Tuple bersarang dapat dibentuk menggunakan parens untuk mengesampingkan urutan operasi.

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

Sebagai bagian dari upaya kami untuk menghapus semua gula sintaksis dari Haskell, saya akan meminta Anda untuk menulis sebuah program yang menghilangkan gula sintaksis dari tupel Haskell juga.

Program Anda harus menggunakan tuple, array, atau string yang mewakili tuple manis dan harus menampilkan string yang mewakili tuple "bebas gula". Input tuple hanya akan berisi bilangan bulat positif atau tuple lainnya.

Karena kita bermain golf di sini, output Anda harus pendek. Seharusnya tidak mengandung yang tidak perlu

  • Spasi. Spasi harus digunakan hanya untuk memisahkan argumen dari fungsi tuple dan seharusnya tidak muncul setelah a )atau sebelum a(

  • Tanda kurung. Kurung harus digunakan hanya ketika membentuk fungsi tuple atau ketika tuple bersarang.

Ini adalah pertanyaan sehingga jawaban akan dinilai dalam byte dengan lebih sedikit byte yang lebih baik.

Uji kasus

(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
Wisaya Gandum
sumber
Jika saya tidak melewatkan sesuatu, Anda menutupi 1-tupel tetapi tidak tupel kosong ..? Apakah masukan kosong tuple valid?
totallyhuman
3
@totallyhuman Anda tidak perlu menangani tupel kosong.
Wheat Wizard
,
Kasing
2
Juga dengan "angka", maksud Anda "bilangan bulat positif"?
Erik the Outgolfer
2
Kasus uji yang disarankan: ((1,(2,3)),4,(5,6))dan (1,(2,3),4).
Ørjan Johansen

Jawaban:

17

Haskell , 169 148 byte

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

Cobalah online! Mengambil tuple sebagai string. init.tail.fst.([]%)adalah fungsi utama anonim. Ikatkan ke eg fdan gunakan like f "(3,(14,1),4,7)", yang menghasilkan "(,,,)3((,)14 1)4 7".

Mengapa input tidak disediakan sebagai tuple Haskell, Anda bertanya? Karena Haskell sangat diketik, tupel (1,2)memiliki tipe (Int,Int)1 dan tupel (1,(2,3))memiliki tipe (Int,(Int,Int)). Dengan demikian fungsi yang menerima jenis tuple pertama tidak dapat diterapkan ke jenis kedua, dan terutama tidak ada fungsi yang mengambil tuple 2 sewenang-wenang .

Penjelasan:

  • p:k="(,"adalah cara singkat untuk menetapkan pke '('dan kuntuk ",".
  • (%)adalah fungsi penguraian dan konversi rekursif. Argumen pertama adalah daftar entri tuple yang sudah diuraikan, argumen kedua adalah sisa dari string asli. Setiap panggilan mengembalikan satu tupel dari tupel yang dikonversi saat ini (sebagai string dan terlampir dalam tanda kurung) dan sisa dari string.
    • l%('(':r)Jika string dimulai dengan braket pembuka, kita perlu mengurai entri tuple baru.
      (y,x:s)<-[]%rKami menerapkan secara rekursif %dan mendapatkan entri tuple ydan string yang tersisa dipisah menjadi karakter berikutnya xdan seluruh string s.
      m<-y:lKami menambahkan entri baru yke daftar entri yang sudah ditemukan saat ini ldan memanggil hasilnya m.
    • Karakter selanjutnya xsekarang adalah koma ,atau braket penutup ). Ini last$ <B> :[ <A> |x<',']hanya cara penulisan yang lebih pendek if x == ')' then <A> else <B>.
    • Jadi, jika a ,adalah yang berikutnya, kita perlu mengurai entri berikutnya secara rekursif: m%(p:s)Kami menambahkan braket pembuka untuk berakhir di case yang tepat dan meneruskan daftar entri yang sudah ditemukan m.
    • Jika sebaliknya x == ')', kami menyelesaikan tuple saat ini dan perlu melakukan transformasi yang diperlukan:(p:p:(l>>k)++x:foldl(\r x->x++[' '|x>k,r>k]++r)[x]m,s)
      • p:p:(l>>k)++x:Jika kita telah menemukan n entri, maka mmemiliki n elemen dan y, daftar sebelum menambahkan elemen yang paling baru ditemukan, memiliki n-1 entri. Ini berguna karena kita membutuhkan n-1 , untuk nelemen tuple dan l>>kbekerja pada daftar sebagai "menyatukan daftar kdengan dirinya sendiri sebanyak yang ydimiliki elemen" . Jadi bagian pertama ini menghasilkan beberapa string seperti "((,,,)".
      • foldl(\r x->x++[' '|x>k,r>k]++r)[x]mmerangkai elemen-elemen m(dalam urutan terbalik, karena dengan menambahkan entri baru ke depan mitu sendiri dibangun dalam urutan terbalik) sambil menambahkan hanya ruang di antara dua elemen jika keduanya angka: [' '|x>k,r>k]kami memeriksa apakah entri saat ini xdan rangka dengan membandingkan secara leksikografis mereka ke ","- jika mereka bukan angka, mereka sudah representasi tuple terlampir dalam tanda kurung, dan '(' < ','memegang.
    • Jika pertandingan pola l%('(':r)yang tepat di awal gagal, maka kita berakhir di baris terakhir: l%r=lex r!!0. Ini berarti kita perlu mengurai angka dan mengembalikan nomor dan sisa string. Untungnya ada lexfungsi yang melakukan hal itu (Ini mem-parsing token Haskell valid berikutnya, bukan hanya angka). Namun tupel yang dihasilkan dibungkus ke dalam daftar, jadi kami gunakan !!0untuk mendapatkan elemen pertama dari daftar.
  • init.tail.fst.([]%)adalah fungsi utama yang mengambil string dan berlaku %dengan daftar kosong. Misalnya untuk input "(1,2)", menerapkan ([]%)hasil ("((,)1 2)",""), sehingga tupel luar dan kurung perlu dihapus. fstmendapatkan elemen pertama dari tuple, tailmenghapus braket penutup dan inityang membuka.

Sunting: Banyak terima kasih kepada @ Ørjan Johansen karena bermain golf total 21 byte !


1 Sebenarnya, tipenya adalah (Num t1, Num t) => (t, t1) , tapi itu cerita yang berbeda.

2 Mengabaikan fungsi polimorfik seperti id , yang sebenarnya tidak bisa bekerja dengan inputnya.

Laikoni
sumber
1
Seseorang dapat menulis fungsi polimorfik menggunakan typeclass Desugarable, tetapi kita harus mendeklarasikan instance untuk Int, dan semua tipe tuple.
Bergi
1
gdapat dipersingkat foldr1(\x r->x++[' '|x>k,r>k]++r)dan digariskan.
Ørjan Johansen
@Bergi: ... dan seseorang tidak dapat mendeklarasikan instance untuk semua tipe tuple . :-) (Coba: show (1,2,3,4,5,6,7,8,9,0,1,2,3,4,5)di GHCi, lalu tambahkan a ,6di akhir dan coba lagi.)
wchargin
1
Meningkatkan inlining untuk enam byte lagi: Gunakan m<-y:l, lipat kiri bukan kanan, dan gunakan [x]sebagai nilai awal. Cobalah online!
Ørjan Johansen
1
fbisa anonim: init.tail.fst.([]%).
Ørjan Johansen
11

Haskell, 141 byte138 byte (Terima kasih kepada Ø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
_%[]=[]

fmemiliki tipe Exp -> String.

  • Input: Templat HaskellExp ression (yaitu, representasi AST standar dari nilai Haskell tipe arbitrer - pada dasarnya, menguraikan kode Haskell sebelum memeriksa jenis); harus mewakili sebuah tuple yang hanya berisi angka integer non-negatif dan tuple lain semacam itu.

  • Output: string yang berisi sintaks yang diinginkan untuk ekspresi tuple itu.

Demo:

$ 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"
berhenti mengubah counterclockwis
sumber
2
Anda dapat mengubah ")"++ke ')':dalam dua tempat, dan menghemat ruang setelah taildengan bergerak kurung luar.
Ørjan Johansen
7

Haskell , 119 byte

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

Cobalah online! Ini menggunakan tipe data khusus Tuntuk mewakili tupel, yaitu tupel ((1,2),3)direpresentasikan sebagai U[U[I 1,I 2],I 3]. Contoh penggunaan: init.tail.f $ U[U[I 1,I 2],I 3]hasil (,)((,)1 2)3.

Laikoni
sumber
6

Python 2 , 110 byte

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

Cobalah online!

Mengambil a tuple.

Erik the Outgolfer
sumber
4

GNU sed, 149 82 + 2 = 84 byte

+2 byte untuk -rbendera.

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

Cobalah online!

Penjelasan

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
sumber
Ini gagal pada beberapa kasus yang lebih rumit: ((1,(2,3)),4,(5,6))dan (1,(2,3),4).
Ørjan Johansen
@ ØrjanJohansen Tangkapan bagus. Saya akan melihat setelah sarapan.
Jordan
3

JavaScript, 75 byte

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

Input array angka | array, string output.

Berkat Neil, simpan 2 byte

tsh
sumber
(1/t?' ':0)+vbisa 1/t?' '+v:v.
Neil
2

Mathematica, 94 byte

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

Berisi fungsi bawaan yang tidak patut U+F4A1dicetak Function.

Membawa Listbilangan bulat Strings. Jika ini tidak diperbolehkan, ini bisa diperbaiki dengan menambahkan 10 byte lagi (versi ini mengambil Listdari Lists / Integers):

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

Pip , 45 byte

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

Ini adalah fungsi yang mengambil daftar sebagai argumen. Cobalah online!

Versi yang dikomentari

; 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
sumber
2

JavaScript (ES6), 88 84 byte

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

Mengambil array bilangan bulat dan array. Sunting: Disimpan 1 byte dengan menggunakan s+=alih-alih dua penggunaan terpisah s+. Menyelamatkan 3 byte lebih lanjut sekarang sehingga saya dapat menyederhanakan bagian dalam batin. Jika saya mencuri ide @ tsh maka saya bisa mendapatkannya hingga 76 byte:

f=a=>a.reduce((s,e)=>s+=t=1/e?1/t?' '+e:e:`(${f(e)})`,`(${t=a.map(_=>``)})`)
Neil
sumber
Your program should take either a tuple or a string representing a sugary tupleSaya menduga bahwa array array / integer harus baik-baik saja.
JungHwan Min
1
Tentu itu diizinkan
Wheat Wizard
1

R, 316 byte?

(Harus keluar dan tidak yakin cara yang tepat untuk menghitung byte ... plus itu bukan solusi yang bagus tetapi ingin mempostingnya karena saya menghabiskan waktu membuatnya ...)

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

Kasus uji:

> 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"
Alasan
sumber
Ini 301 byte: Cobalah online!
Laikoni
2
Golf hingga 261 byte . Saya akan meninggalkan penjelasan untuk apa yang saya ubah, tetapi ironisnya, saya juga harus pergi ... Tapi +1, saya tidak bisa membungkus kepala sama sekali; kerja bagus!
Giuseppe
0

JavaScript (ES6), 72 byte

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

Input: Array yang berisi angka dan / atau array

Output: string

Penggunaan: f ([...])

Selesaikan semua kasus uji, selamat datang perbaikan

ES6_is_awesome
sumber
0

C, 308 atau 339 byte

#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 atau 339 byte, tergantung pada apakah atau tidaknya melewatkan pointer ke akhir string input diperbolehkan; baris terakhir hanya ada di sana untuk memungkinkan melewati string literal secara langsung tanpa harus menghitung panjangnya.

Penjelasan

Algoritma yang cukup sederhana. Ia menghitung jumlah koma pada kedalaman saat ini, mencetaknya sebagai konstruktor tuple, kemudian menindaklanjuti dengan argumen tuple, lolos (spasi di antara angka, tupel bersarang di antara kurung), secara rekursif.

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

Uji kasus dan aplikasi

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