21
\$\begingroup\$

Haskell has tuples that can be written as

(a,b,c)

However this is just syntactic sugar for

(,,)a b c

In general an n tuple can be formed with n-1 ,s between (...) followed by its elements separated by spaces. For example the 7-tuple, (1,2,3,4,5,6,7) can be formed by

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

Since Haskell does not have 1-tuples they cannot be formed. You will also not be held responsible for empty tuples.

Nested tuples can be formed using parens to override the order of operations.

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

As part of our pursuit to remove all syntactic sugar from Haskell I am going to ask you to write a program that removes syntactic sugar from Haskell's tuples as well.

Your program should take a tuple, an array, or a string representing a sugary tuple and should output a string representing a "sugar-free" tuple. Input tuples will only ever contain positive integers or other tuples.

Since we are golfing here your output should be short. It should not contain unnecessary

  • Spaces. Spaces should be used only to separate arguments of a tuple functions and should not appear after a ) or before a (

  • Parentheses. Parentheses should be used only when forming tuple functions or when nesting tuples.

This is a question so answers will be scored in bytes with fewer bytes being better.

Test cases

(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
\$\endgroup\$
  • \$\begingroup\$ If I'm not missing anything, you cover 1-tuples but not empty tuples..? Are empty tuples valid input? \$\endgroup\$ – totallyhuman Sep 4 '17 at 17:06
  • 3
    \$\begingroup\$ @totallyhuman You do not have to handle empty tuples. \$\endgroup\$ – Sriotchilism O'Zaic Sep 4 '17 at 17:07
  • \$\begingroup\$ The 5th test-case has an extra , \$\endgroup\$ – H.PWiz Sep 4 '17 at 17:25
  • 2
    \$\begingroup\$ Also by "numbers" do you mean "positive integers"? \$\endgroup\$ – Erik the Outgolfer Sep 4 '17 at 17:52
  • 2
    \$\begingroup\$ Suggested test cases: ((1,(2,3)),4,(5,6)) and (1,(2,3),4). \$\endgroup\$ – Ørjan Johansen Sep 5 '17 at 6:55

12 Answers 12

17
\$\begingroup\$

Haskell, 169 148 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

Try it online! Takes the tuple as a string. init.tail.fst.([]%) is the anonymous main function. Bind it to e.g. f and use like f "(3,(14,1),4,7)", which yields "(,,,)3((,)14 1)4 7".

Why is the input not provided as a Haskell tuple, you ask? Because Haskell is strongly typed, a tuple (1,2) has type (Int,Int)1 and a tuple (1,(2,3)) has type (Int,(Int,Int)). Thus a function which accepts the first kind of tuple can not be applied to the second kind, and especially there can be no function which takes an arbitrary tuple2.

Explanation:

  • p:k="(," is a short way to assign p to '(' and k to ",".
  • (%) is the recursive parsing and converting function. The first argument is a list of already parsed tuple entries, the second argument is the remainder of the original string. Each call returns a tuple of the current converted tuple (as a string and enclosed in brackets) and the remainder of the string.
    • l%('(':r) If the string starts with an opening bracket, we need to parse a new tuple entry.
      (y,x:s)<-[]%r We recursively apply % and get a tuple entry y and the remaining string splitted into the next character x and the rest of the string s.
      m<-y:l We add the new entry y to the current list of already found entries l and call the result m.
    • The next character x is now either a comma , or a closing bracket ). The last$ <B> :[ <A> |x<','] is just a shorter way of writing if x == ')' then <A> else <B>.
    • So if a , is next, we need to recursively parse the next entry: m%(p:s) We prepend an opening bracket in order to end up in the right case and pass the list of already found entries m.
    • If otherwise x == ')', we finished the current tuple and need to do the required transformation: (p:p:(l>>k)++x:foldl(\r x->x++[' '|x>k,r>k]++r)[x]m,s)
      • p:p:(l>>k)++x: If we have found n entries, then m has n elements and y, the list before adding the most recently found element, has n-1 entries. This comes in handy as we need n-1 , for an n element tuple and l>>k works on lists as "concatenate the list k with itself as many times as y has elements". Thus this first part yields some string like "((,,,)".
      • foldl(\r x->x++[' '|x>k,r>k]++r)[x]m concatenates the elements of m (in reverse order, because by adding new entries to the front m itself was constructed in reverse order) while adding only spaces in between two elements if they are both numbers: [' '|x>k,r>k] we check if the current entries x and r are numbers by lexicographically comparing them to "," - if they are not numbers, they are already a tuple representation enclosed in brackets, and '(' < ',' holds.
    • If the pattern match l%('(':r) right at the beginning fails, then we end up on the last line: l%r=lex r!!0. This means we need to parse a number and return the number and the remainder of the string. Luckily there is the lex function which does exactly that (It parses the next valid Haskell token, not just numbers). However the resulting tuple is wrapped into a list, so we use !!0 to get the first element of the list.
  • init.tail.fst.([]%) is the main function which takes a string and applies % with an empty list to it. E.g. for an input "(1,2)", , applying ([]%) yields ("((,)1 2)",""), so the outer tuple and brackets need to be removed. fst gets the first element of the tuple, tail removes the closing bracket and init the opening one.

Edit: Many thanks to @Ørjan Johansen for golfing a total of 21 bytes!


1 Actually, the type is (Num t1, Num t) => (t, t1), but that's a diferent story.

2 Ignoring polymorphic functions like id, which cannot actually work with their input.

\$\endgroup\$
  • 1
    \$\begingroup\$ One could write a polymorphic function using a typeclass Desugarable, but one would have to declare instances for Int, and all tuple types. \$\endgroup\$ – Bergi Sep 4 '17 at 22:32
  • 1
    \$\begingroup\$ g can be shortened to foldr1(\x r->x++[' '|x>k,r>k]++r) and inlined. \$\endgroup\$ – Ørjan Johansen Sep 5 '17 at 1:40
  • \$\begingroup\$ @Bergi: …and one cannot declare instances for truly all tuple types. :-) (Try: show (1,2,3,4,5,6,7,8,9,0,1,2,3,4,5) in GHCi, then add a ,6 at the end and try again.) \$\endgroup\$ – wchargin Sep 5 '17 at 1:54
  • 1
    \$\begingroup\$ Improving the inlining for six more bytes: Use m<-y:l, fold left instead of right, and use [x] as initial value. Try it online! \$\endgroup\$ – Ørjan Johansen Sep 5 '17 at 6:07
  • 1
    \$\begingroup\$ f can be anonymous: init.tail.fst.([]%). \$\endgroup\$ – Ørjan Johansen Sep 5 '17 at 6:19
11
\$\begingroup\$

Haskell, 141 bytes 138 bytes(Thanks to Ø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
_%[]=[]

f has type Exp -> String.

  • Input: a Template Haskell Expression (i.e., the standard AST representation of arbitrary-type Haskell values – basically, parsed Haskell code before type checking); must represent a tuple containing only nonnegative integer numbers and other such tuples.

  • Output: a string containing the desugared syntax for that tuple expression.

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"
\$\endgroup\$
  • 2
    \$\begingroup\$ You can change ")"++ to ')': in two places, and save the space after the tail by moving it outside parentheses. \$\endgroup\$ – Ørjan Johansen Sep 5 '17 at 18:36
7
\$\begingroup\$

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

Try it online! This uses a custom data type T to represent tuples, that is a tuple ((1,2),3) is represented as U[U[I 1,I 2],I 3]. Example usage: init.tail.f $ U[U[I 1,I 2],I 3] yields (,)((,)1 2)3.

\$\endgroup\$
6
\$\begingroup\$

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

Try it online!

Takes a tuple.

\$\endgroup\$
4
\$\begingroup\$

GNU sed, 149 82 + 2 = 84 bytes

+2 bytes for -r flag.

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

Try it online!

Explanation

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
\$\endgroup\$
  • \$\begingroup\$ This fails on some more complicated cases: ((1,(2,3)),4,(5,6)) and (1,(2,3),4). \$\endgroup\$ – Ørjan Johansen Sep 5 '17 at 6:52
  • \$\begingroup\$ @ØrjanJohansen Good catch. I'll take a look after breakfast. \$\endgroup\$ – Jordan Sep 5 '17 at 11:44
3
\$\begingroup\$

JavaScript, 75 bytes

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

Input array of number|array, output string.

Thanks to Neil, save 2 bytes

\$\endgroup\$
  • \$\begingroup\$ (1/t?' ':0)+v can be 1/t?' '+v:v. \$\endgroup\$ – Neil Sep 5 '17 at 9:20
2
\$\begingroup\$

Mathematica, 94 bytes

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

Contains an unprintable U+F4A1, a builtin Function function.

Takes a List of integer Strings. If this is not allowed, this can be fixed by adding 10 more bytes (this version takes a List of Lists/Integers):

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

Pip, 45 bytes

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

This is a function that takes a list as an argument. Try it online!

Commented version

; 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 ") " ')
}
\$\endgroup\$
2
\$\begingroup\$

JavaScript (ES6), 88 84 bytes

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

Takes an array of integers and arrays. Edit: Saved 1 byte by using s+= instead of two separate uses of s+. Saved a further 3 bytes now that I can simplify the inner ternary. If I steal @tsh's ideas then I can get it down to 76 bytes:

f=a=>a.reduce((s,e)=>s+=t=1/e?1/t?' '+e:e:`(${f(e)})`,`(${t=a.map(_=>``)})`)
\$\endgroup\$
  • \$\begingroup\$ Your program should take either a tuple or a string representing a sugary tuple I'd presume that an array of arrays/integers should be fine. \$\endgroup\$ – JungHwan Min Sep 4 '17 at 21:20
  • 1
    \$\begingroup\$ Sure that is allowed \$\endgroup\$ – Sriotchilism O'Zaic Sep 4 '17 at 21:24
1
\$\begingroup\$

R, 316 bytes?

(Have to head out and not sure the proper way to count bytes... plus it's not a great solution but wanted to post it since I spent the time making it...)

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

Test cases:

> 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"
\$\endgroup\$
  • \$\begingroup\$ It's 301 bytes: Try it online! \$\endgroup\$ – Laikoni Sep 5 '17 at 19:23
  • 2
    \$\begingroup\$ Golfed to 261 bytes. I'd leave an explanation for what I changed, but ironically, I also have to go...But +1, I couldn't wrap my head around this at all; nice work! \$\endgroup\$ – Giuseppe Sep 5 '17 at 21:44
0
\$\begingroup\$

JavaScript (ES6), 72 bytes

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

Input: Array containing numbers and/or arrays

Output:string

Usage: f([...])

Completes all test cases, improvements welcome

\$\endgroup\$
0
\$\begingroup\$

C, 308 or 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 or 339 bytes, depending on whether or not passing a pointer to the end of the input string is allowed; the last line is only there to allow passing a string literal directly without having to calculate its length.

Explanation

A pretty simple algorithm. It counts the number of commas at the current depth, prints them as a tuple constructor, then follows up with the tuple's arguments, escaped (spaces between numbers, nested tuples between parenthesis), recursively.

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

Test cases and 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");
  }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.