Давайте сделаем диету Haskell

21

У Haskell есть кортежи, которые можно записать как

(a,b,c)

Однако это просто синтаксический сахар для

(,,)a b c

В общем случае n- кортеж может быть сформирован с n-1 , s между (..., )за которым следуют его элементы, разделенные пробелами. Например, 7-кортеж, (1,2,3,4,5,6,7)может быть сформирован

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

Поскольку в Haskell нет 1-кортежей, они не могут быть сформированы. Вы также не будете нести ответственность за пустые кортежи.

Вложенные кортежи могут быть сформированы с помощью паренов, чтобы переопределить порядок операций.

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

В рамках нашего стремления удалить весь синтаксический сахар из Haskell, я попрошу вас написать программу, которая также удаляет синтаксический сахар из кортежей Haskell.

Ваша программа должна принимать кортеж, массив или строку, представляющую сахарный кортеж, и выводить строку, представляющую кортеж «без сахара». Входные кортежи будут содержать только натуральные числа или другие кортежи.

Так как мы здесь играем в гольф, ваш результат должен быть коротким. Не должно содержать ненужных

  • Пространства. Пробелы должны использоваться только для разделения аргументов функций кортежа и не должны появляться после )или перед(

  • Круглые скобки. Скобки следует использовать только при формировании функций кортежей или при вложении кортежей.

Это вопрос поэтому ответы будут оцениваться в байтах, причем меньше байтов будет лучше.

Контрольные примеры

(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
Мастер пшеницы
источник
Если я ничего не пропускаю, вы покрываете 1-кортежи, но не пустые кортежи ..? Допустимы ли пустые кортежи?
полностью человек
3
@totallyhuman Вам не нужно обрабатывать пустые кортежи.
Пшеничный волшебник
У 5-го тестового случая есть дополнительный,
H.PWiz
2
Также под «числами» вы подразумеваете «положительные целые числа»?
Эрик Outgolfer
2
Предлагаемые тесты: ((1,(2,3)),4,(5,6))и (1,(2,3),4).
Орджан Йохансен,

Ответы:

17

Haskell , 169 148 байт

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

Попробуйте онлайн! Принимает кортеж как строку. init.tail.fst.([]%)это анонимная основная функция. Привязать его к например fи использовать как f "(3,(14,1),4,7)", что дает "(,,,)3((,)14 1)4 7".

Вы спрашиваете, почему вход не представлен как кортеж Haskell? Поскольку Haskell строго типизирован, кортеж (1,2)имеет тип (Int,Int)1, а кортеж (1,(2,3))имеет тип (Int,(Int,Int)). Таким образом, функция, которая принимает кортежи первого типа, не может быть применена ко второму типу, и, в особенности, не может быть функции, которая принимает произвольный кортеж 2 .

Объяснение:

  • p:k="(,"короткий путь , чтобы назначить pна '('и kна ",".
  • (%)является рекурсивной функцией анализа и преобразования. Первый аргумент - это список уже проанализированных записей кортежа, второй аргумент - остаток исходной строки. Каждый вызов возвращает кортеж текущего преобразованного кортежа (в виде строки и заключенного в скобки) и остаток строки.
    • l%('(':r)Если строка начинается с открывающей скобки, нам нужно проанализировать новую запись кортежа.
      (y,x:s)<-[]%rМы рекурсивно применяем %и получаем запись кортежа, yа оставшаяся строка разбивается на следующий символ xи остальную часть строки s.
      m<-y:lМы добавляем новую запись yв текущий список уже найденных записей lи вызываем результат m.
    • Следующий символ xтеперь является запятой ,или закрывающей скобкой ). Это last$ <B> :[ <A> |x<',']просто более короткий способ написания if x == ')' then <A> else <B>.
    • Поэтому, если a ,следующее, нам нужно рекурсивно проанализировать следующую запись: m%(p:s)мы добавляем открывающую скобку, чтобы оказаться в правильном регистре и пропустить список уже найденных записей m.
    • Если иначе x == ')', мы закончили текущий кортеж и должны выполнить требуемое преобразование:(p:p:(l>>k)++x:foldl(\r x->x++[' '|x>k,r>k]++r)[x]m,s)
      • p:p:(l>>k)++x:Если мы обнаружили , п записи, то mесть п элементов и y, список , прежде чем добавить самый последний найденный элемент, имеет п-1 записей. Это очень удобно, так как нам нужен n-1 , для nкортежа элемента, и он l>>kработает со списками как «объединяет список kс самим собой столько раз, сколько yимеет элементы» . Таким образом, эта первая часть дает строку вроде "((,,,)".
      • foldl(\r x->x++[' '|x>k,r>k]++r)[x]mобъединяет элементы m(в обратном порядке, потому что путем добавления новых записей к mсамому фронту был построен в обратном порядке), добавляя только пробелы между двумя элементами, если они оба являются числами: [' '|x>k,r>k]мы проверяем, являются ли текущие записи xи rявляются числами, путем лексикографического сравнения их ","- если они не являются числами, они уже являются представлением кортежа, заключенным в скобки, и '(' < ','содержат их.
    • Если сопоставление с образцом l%('(':r)в самом начале не удастся, то мы в конечном итоге на последней строке: l%r=lex r!!0. Это означает, что нам нужно проанализировать число и вернуть число и остаток строки. К счастью, есть lexфункция, которая делает именно это (она анализирует следующий действительный токен Haskell, а не только числа). Однако полученный кортеж обернут в список, поэтому мы используем, !!0чтобы получить первый элемент списка.
  • init.tail.fst.([]%)является основной функцией, которая принимает строку и применяет %к ней пустой список. Например, для ввода "(1,2)", применяя ([]%)выходы ("((,)1 2)",""), поэтому внешний кортеж и скобки должны быть удалены. fstполучает первый элемент кортежа, tailудаляет закрывающую скобку и initоткрывающую.

Редактировать: Большое спасибо @ Örjan Johansen за гольф в общей сложности 21 байт !


1 На самом деле тип (Num t1, Num t) => (t, t1) , но это другая история.

2 Игнорирование полиморфных функций, таких как id , которые фактически не могут работать с их вводом.

Laikoni
источник
1
Можно было бы написать полиморфный функцию , используя класс типов Desugarable, но один должен был бы заявить о случаях для Intи всех типов кортежей.
Берги
1
gможет быть сокращено до foldr1(\x r->x++[' '|x>k,r>k]++r)и встроено.
Орджан Йохансен,
@Bergi:… и нельзя объявлять экземпляры для действительно всех типов кортежей . :-) (Попробуйте: show (1,2,3,4,5,6,7,8,9,0,1,2,3,4,5)в GHCi, затем добавьте a ,6в конце и попробуйте снова.)
wchargin
1
Улучшение встраивания еще на шесть байтов: используйте m<-y:l, сверните влево вместо правого и используйте в [x]качестве начального значения. Попробуйте онлайн!
Орджан Йохансен,
1
fможет быть анонимным: init.tail.fst.([]%).
Орджан Йохансен,
11

Haskell, 141 байт138 байт (спасибо Эрджану Йохансену)

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

fимеет тип Exp -> String.

  • Входные данные: шаблонная версия HaskellExp (т. Е. Стандартное представление AST значений Haskell произвольного типа - в основном, анализ кода Haskell перед проверкой типа); должен представлять кортеж, содержащий только неотрицательные целые числа и другие подобные кортежи.

  • Выход: строка, содержащая синтаксис desugared для этого выражения кортежа.

Демо-версия:

$ 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"
перестал поворачиваться против часовой стрелки
источник
2
Вы можете изменить ")"++его ')':в двух местах и ​​сэкономить место после tail, переместив его за пределы скобок.
Орджан Йохансен,
7

Haskell , 119 байт

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

Попробуйте онлайн! Это использует пользовательский тип данных Tдля представления кортежей, то есть кортеж ((1,2),3)представляется как U[U[I 1,I 2],I 3]. Пример использования: init.tail.f $ U[U[I 1,I 2],I 3]доходность (,)((,)1 2)3.

Laikoni
источник
4

GNU sed, 149 82 + 2 = 84 байта

+2 байта за -rфлаг.

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

Попробуйте онлайн!

объяснение

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
Иордания
источник
Это не помогает в некоторых более сложных случаях: ((1,(2,3)),4,(5,6))и (1,(2,3),4).
Орджан Йохансен,
@ ØrjanJohansen Хороший улов. Я посмотрю после завтрака.
Джордан,
3

JavaScript, 75 байт

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

Входной массив номера | массив, выходная строка.

Благодаря Нилу, сэкономьте 2 байта

ТТГ
источник
(1/t?' ':0)+vможет быть 1/t?' '+v:v.
Нил
2

Mathematica, 94 байта

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

Содержит непечатную U+F4A1, встроенную Functionфункцию.

Принимает Listцелое число Strings. Если это не разрешено, это может быть исправлено путем добавления еще 10 байт (эта версия занимает Listот Lists / Integers):

{"(",","&/@Most@#,")",c=1>0;(xIf[j=ListQ@x,c=j;"("<>#0@x<>")",If[c,c=j;""," "]<>ToString@x])/@#}<>""&
Юнг Хван Мин
источник
2

Пип , 45 байт

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

Это функция, которая принимает список в качестве аргумента. Попробуйте онлайн!

Комментируемая версия

; 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
источник
2

JavaScript (ES6), 88 84 байта

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

Принимает массив целых чисел и массивов. Редактировать: 1 байт сохранен с использованием s+=вместо двух отдельных s+. Сохранено еще 3 байта теперь, когда я могу упростить внутреннюю троицу. Если я украду идеи @ tsh, то смогу уменьшить их до 76 байт:

f=a=>a.reduce((s,e)=>s+=t=1/e?1/t?' '+e:e:`(${f(e)})`,`(${t=a.map(_=>``)})`)
Нил
источник
Your program should take either a tuple or a string representing a sugary tupleЯ бы предположил, что массив массивов / целых чисел должен быть в порядке.
JungHwan Мин.
1
Конечно, это разрешено
Wheat Wizard
1

R, 316 байт?

(Нужно выходить на улицу и не знать, как правильно считать байты ... плюс, это не очень хорошее решение, но я хотел опубликовать его, так как я потратил время на его создание ...)

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

Тестовые случаи:

> 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
источник
Это 301 байт: попробуйте онлайн!
Лайкони
2
Гольф до 261 байта . Я бы оставил объяснение того, что я изменил, но по иронии судьбы мне тоже нужно идти ... Но +1, я вообще не мог обернуться вокруг этого; хорошо сделано!
Джузеппе
0

JavaScript (ES6), 72 байта

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

Ввод: массив, содержащий числа и / или массивы

Вывод: строка

Использование: f ([...])

Завершает все тестовые случаи, улучшения приветствуются

ES6_is_awesome
источник
0

C, 308 или 339 байтов

#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 или 339 байт, в зависимости от того, разрешен или нет указатель на конец входной строки; последняя строка предназначена только для прямой передачи строкового литерала без вычисления его длины.

объяснение

Довольно простой алгоритм. Он подсчитывает количество запятых на текущей глубине, печатает их как конструктор кортежа, затем рекурсивно проверяет аргументы кортежа (пробелы между числами, вложенные кортежи между скобками).

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

Тестовые случаи и применение

#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
источник