[Question]
  [
A void list is a list that at no level contains any non-list objects. Or if you prefer a recursive definition
* The empty list is void
* A list containing only other void lists is void
All void lists have a finite depth.
Here are some examples of void lists (using python syntax):
```
[]
[[]]
[[],[]]
[[[]]]
[[[]],[]]
[[],[[]]]
```
Here are some examples of things that are *not* void lists:
```
["a"]
[[...]]
[1]
2
[[],([],[])]
```
---
# Task
Write two separate functions (or programs if you prefer). One should take a positive integer (you may also include zero if you wish) as an argument and return a void list the other should take a void list and return it an integer. These two functions should always be inverses of each other. That is if you pass the output of `f` into `g` you should get the original input of `f` as the result of `g`. This means the mapping must be 1:1, i.e. for every integer, there may only exist **exactly one** void list for which `g` gives that integer and for every void list there should be exactly one integer for which `f` gives that void list.
You are essentially creating a Bijection
You may choose to use a string representation of a void list (with or without commas and spaces) instead of your languages native list type.
# Scoring
Your score will be the lengths of your two functions together. This is [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'") so you should aim to minimize this sum.
  
[Answer]
# Pyth, 27 + 29 = 56 bytes
`f`:
```
L?bol`NS{sm[d+d]Y]d)ytb]Y@y
```
[Test suite](https://pyth.herokuapp.com/?code=L%3Fbol%60NS%7Bsm%5Bd%2Bd%5DY%5Dd%29ytb%5DY%40y&test_suite=1&test_suite_input=0%0A1%0A2%0A3%0A4&debug=0)
`g`:
```
L?bol`NS{sm[d+d]Y]d)ytb]Yxyl`
```
[Test suite](https://pyth.herokuapp.com/?code=L%3Fbol%60NS%7Bsm%5Bd%2Bd%5DY%5Dd%29ytb%5DYxyl%60&test_suite=1&test_suite_input=%5B%5D%0A%5B%5B%5D%5D%0A%5B%5B%5B%5D%5D%5D%0A%5B%5B%5D%2C+%5B%5D%5D%0A%5B%5B%5B%5B%5D%5D%5D%5D&debug=0)
The system is very simple: I generate all possible lists with no more than a certain number of `[`'s. Then, I sort them in such a way that the lists I haven't generated yet would be near the end. This is all done by the function `y`, identical in both programs. It is written as
```
L?bol`NS{sm[d+d]Y]d)ytb]Y
```
Then, I index into this list for `f`, and search through it for `g`.
The number of lists I generate is chosen to be large enough that I have generated all possible lists which would appear at or before the desired location in the infinite sorted list.
The programs allow/return 0 as an option.
[Answer]
# [Python 2](https://docs.python.org/2/), 96 bytes
[Try it online!](https://tio.run/nexus/python2#NYzNCoQwDITP26foaUn8wb9b0ScpOUS0odDNiuz7uxb1MGG@mSFHmBJ/5oVtcmlVSMi62ADJt4RFX3bjmKFzhEaeqTotvNC59ALagL5rxaZHKgXykznqlWE94BG@u402qt1ZZYWhRWde2x71Z2MVQCAiVvkac6XG8OS9p8rTqdsQ3W0AxtsKZHiIjz8 "Python 2 – TIO Nexus") to test the bijection.
```
f=lambda l:len(l)and f(l[0])*2+1<<f(l[1:])
```
Takes void lists to non-negative integers. 42 bytes.
```
g=lambda n:n*[g]and[g(n/(n&-n)/2)]+g(len(bin(n&-n))-3)
```
Takes non-negative integers to void lists. 54 bytes. A more recursive attempt gave the same length.
```
g=lambda n,i=0:n*[g]and[g(n/2,i+1),[g(n/2)]+g(i)][n%2]
```
[Answer]
# Java 7, 725 bytes
`f(int)` (**325 bytes**):
```
String f(int i){String s="";for(int j=0,e=0;e<i;e+=v(s))s=Integer.toBinaryString(j++);return"["+s.replace("1","[").replace("0","]")+"]";}int v(String s){for(;!s.isEmpty();s=s.replaceFirst("1","").replaceFirst("0",""))if(s.replace("1","").length()!=s.replace("0","").length()|s.charAt(0)<49|s.endsWith("1"))return 0;return 1;}
```
`g(String)` (**75 + 325 bytes**):
```
int g(String s){int r=0;for(String i="10";!i.equals(s);i=f(++r));return r;}
```
Since method `g` uses method `f` to calculate it's result by looping over possible void-list until it founds the one equal to the one inputted, the bytes of `f` are counted twice (since both methods should be able to run without the other for this challenge).
**Explanation:**
In general, method `f` simply loops over all binary String-representations of integers, and increase a counter every time a valid one is found. Valid binary-Strings for this challenge comply to the following rules: They start with a `1`, and end with a `0`; they have an equal number of 1s and 0s; and every time you remove the first `1` and `0` and validate what is left again, these two rules still apply. After the counter equals the input, it converts that binary-String to a String void-list, by replacing all `1` with `[` and all `0` with `]`.
As for method `g`: We start with `"[]"` (representing void-list `0`), and then continue using method `f` while increasing an integer, until it matches the input-String.
```
String f(int i){         // Method `f` with integer parameter and String return-type
  String s="";           //  Start with an empty String
  for(int j=0,e=0;e<i;   //  Loop as long as `e` does not equal the input
      e+=v(s))           //    And append increase integer `e` if String `s` is valid
    s=Integer.toBinaryString(j++);
                         //   Change `s` to the next byte-String of integer `j`
                         //  End of loop (implicit / single-line body)
  return"["+             //  Return the result String encapsulated in "[" and "]"
    s.replace("1","[").replace("0","]")+"]";
                         //  after we've replaced all 1s with "[" and all 0s with "]"
}                        // End of method `f`
int v(String s){         // Separate method with String parameter and integer return-type
  for(;!s.isEmpty();     //  Loop as long as String `s` isn't empty
      s=s.replaceFirst("1","").replaceFirst("0",""))
                         //    After each iteration: Remove the first "1" and "0"
    if(s.replace("1","").length()!=s.replace("0","").length()
                         //   If there isn't an equal amount of 1s and 0s
       |s.charAt(0)<49   //   or the String doesn't start with a 1
       |s.endsWith("1")) //   or the String doesn't end with a 0
      return 0;          //    Return 0 (String is not valid)
                         //  End of loop (implicit / single-line body)
  return 1;              //  Return 1 (String is valid)
}                        // End of separate method
int g(String s){         // Method `g` with String parameter and integer return-type
  int r=0;               // Result integer
  for(String i="[]";!i.equals(s);
                         //  Loop as long as `i` does not equal the input String
      i=f(++r));         //   After each iteration: Set `i` to the next String in line
  return r;              //  Return the result integer
}                        // End of method `g`
```
**Example input & output cases:**
[Try it here.](https://tio.run/nexus/java-openjdk#pZJNb@IwEIbv@RWDTx6lioK0HLbGh11pK/XAqYceEIcsmHSqxFB7oEJsfjudkFBoqx5W5GBrXvt95sOZV0WMMNkfHjiQL2GpyTMQ7vs4WqXMchWO8rPNb5zNjRuTcand6ogY7b1nV7qQ8eo3@SLsOqd@TlM0wfEmeDVVacyCW1fF3Gk1VDei4FnIRZgpTGUxTZtoq0/pcd8mN4OYUfxTr3mn0UT7DrujELkjnoG9mB9FpKX@lFtuVs6X/KRxYOPHMi7O/sVs/lSEX6xzHP/4KaHzi/hIciYYxK43yPsmYWiapC2@vCi@jYNMrG2iV8mqqfQ5oMy9bIoqyhAN2aVO04CngUEwzQFgvflb0RwiFyzbdkULqAvyPWk6gwL3Ccg3gRosePcKE5nPUTq9GUl2oPFwJKu8SHcf4GEX2dXZasPZWmBceU2QgroFJVudyX@AbdyHpe4k7OlNknxDUaP8zBjlXyGitZTO342EpfjjUL6D8mVppeZTGZ1xOrvCeo1ZvNeYxd5v/49pkubwBg) (NOTE: It's pretty slow for the last few test cases. Will take around 10-15 sec for all of them.)
```
0   <-> []
1   <-> [[]]
2   <-> [[][]]
3   <-> [[[]]]
4   <-> [[][][]]
5   <-> [[][[]]]
6   <-> [[[]][]]
7   <-> [[[][]]]
8   <-> [[[[]]]]
9   <-> [[][][][]]
10  <-> [[][][[]]]
11  <-> [[][[]][]]
12  <-> [[][[][]]]
13  <-> [[][[[]]]]
14  <-> [[[]][][]]
50  <-> [[[][[[]]]]]
383 <-> [[[][]][[[][]]]]
```
[Answer]
# [K (ngn/k)](https://gitlab.com/n9n/k), 49 bytes
```
{$[#x;2/,/1,'&:'o'x;0]}
{$[x;o'|-1+-1-':&|2\x;()]}
```
[Try it online!](https://tio.run/##VYxNCoMwEIX3nmKkxUyof3HXzMYT9AKtYCGxiBJBXUTUXt3GIoUuhnmP9/E1kXmZbdNyPt9PlrIkTETIAsk6ZiktVk/ti6WOLZG4RCJiMliyhyXkxbqN@zi9e1mBpbJrCMvqWbdkaaLeAV4lVa5zmtObPzqLLVaGyCl0t3/kLn9LeLRjdQkSGPUwgkKNLedQD9A6n87Vv8/P0h@rUaFxbNX1YKA2kMaxuG4f "K (ngn/k) – Try It Online")
uses the formula from the example in [Bijection: tree-like lists - natural numbers](https://codegolf.stackexchange.com/questions/169623/bijection-tree-like-lists-natural-numbers?noredirect=1#MathJax-Element-1-Frame)
[Answer]
# [JavaScript (Node.js)](https://nodejs.org), 82 bytes
```
f=(n,i)=>n?n&1<<i?[f(i),...f(n>>-~i)]:f(n,-~i):[]
g=([a,...b])=>a?g(b)*2+1<<g(a):0
```
[Try it online!](https://tio.run/##TYvLCsMgEADvfkjZbY30cShI1A8RDyaNsiWspSk95teNORR6G2aYZ/zGZXzT69NxeUy1JgMsCY1lx4dL35PzCQilUioBW9uthEE3lDtpH0Q24OPeh9C26DIMeLye2pshoj7XsfBS5knNJUOC2x1R/KufRFE3 "JavaScript (Node.js) – Try It Online")
xnor's idea
[Answer]
# [Python 3](https://docs.python.org/3/) - sign/abs, 73 bytes
```
f=lambda n:[[[]]*(n<0),[[]]*abs(n)]
g=lambda l:[-1,1][not l[0]]*len(l[1])
```
[Try it online!](https://tio.run/##Nco7DgIhEADQfk8x3c4YSEA7ol5kQsHGBUlw2LA0nh5/sXvF2579XuU0RryU8FhuAcQxs/cHlLMh9WVYdhTyU/qf4lhbZT1L7VDYvE9ZBQtbTyPWBhmyQAuSVtRHZQ25CbaWpWNWs77OKmKmnxJ@TDRe "Python 3 – Try It Online")
Straight forward implementation, supports negative numbers.
Integer `i` is encoded `[sign(i), abs(i)]`, where `sign(i)=[] if i > 0 else [[]]` and `abs(i)=[[]] * i`, i.e. a list of empty lists with length abs(i).
# [Python 3](https://docs.python.org/3/) - binary, 126 bytes
This is a more elaborate version (and a lot longer...), where the absolute value is encoded in a binary list representation.
```
f=lambda n:[[[]]*(n<0),[[[]]*int(i)for i in f"{n:+b}"[1:]]]
g=lambda l:[-1,1][not l[0]]*int(''.join(map(str,map(len,l[1]))),2)
```
[Try it online!](https://tio.run/##PY5BDsIgFET3PQXpBr7@mlJ3RL0IYUFjqRj6aZCNMZ4drVVX8zZvZuZ7vkTal@KOwU792TJSWmtjNoIOLeDKnrLw4GJinnlirn6Q2vbPWktljKnGnxuUbiRKoylmFnT7VTnfXaMnMdlZ3HLCJcNAGLQ0AIAdlH93sjQOoulQtqAqNqfPNvLmxNG9T6w0ioUBygs "Python 3 – Try It Online")
[Answer]
# [Stax](https://github.com/tomtheisen/stax), 33 total bytes
These programs are inverses of each other. They convert to and from all void lists and all non-negative integers, so that includes 0. This seems like it's maybe a famous function from some kind of algebra I don't know. In order to wrap my head around it, I first implemented the programs as functions in python.
```
def convert_to_void(n):
    lst = []
    while n > 0:
        n -= 1
        choices = len(lst) + 1
        choice = n % choices
        cutpoint = len(lst) - choice
        n //= choices
        newgroup = lst[cutpoint:]
        del lst[cutpoint:]
        lst.append(newgroup)
    return lst
def convert_from_void(lst):
    n = 0
    while lst != []:
        newgroup = lst.pop()
        n *= len(lst) + len(newgroup) + 1
        n += len(newgroup) + 1
        lst.extend(newgroup)
    return n
```
The stax programs have the same behavior.
### Non-negative integer → Void list, 15 [bytes](https://github.com/tomtheisen/stax/blob/master/docs/packed.md#packed-stax)
```
ƒâ₧~└3BI─¿-rÅ;ì
```
[Run and debug it](https://staxlang.xyz/#p=9f839e7ec0334249c4a82d728f3b8d&i=0%0A1%0A2%0A3%0A123%0A54321&a=1&m=2)
### Void list → Non-negative integer, 18 [bytes](https://github.com/tomtheisen/stax/blob/master/docs/packed.md#packed-stax)
```
Çäê[!σ`c↑Ö§░NR╥ç=Æ
```
[Run and debug it](https://staxlang.xyz/#p=8084885b21e56063189915b04e52d2873d92&i=[]%0A[[]]%0A[[],+[]]%0A[[[]]]%0A[[[[]]],+[[]],+[],+[]]%0A[[[[[]],+[[],+[[]]]],+[[],+[]]]]&a=1&m=2)
]