{"article":{"slug":"parsing-nested-lists-in-bqn","title":"Parsing nested lists in BQN","subtitle":null,"summary":"Three ways to parse the nested lists from Advent of Code 2022 day 13 in the array language BQN: leaning on •BQN, a recursive descent parser, and an array-style parser, with simple benchmarks comparing them.","content_type":"tutorial","language":"en","canonical_url":"https://saltysylvi.github.io/blog/parsing-nested-lists-in-bqn.html","author":{"name":"saltysylvi","url":null,"person_slug":null,"person_url":null},"authored_by":"human","publisher":{"name":"saltysylvi","url":"https://saltysylvi.github.io/","listing_slug":null,"listing":null},"topics":[{"name":"programming-languages","slug":"programming-languages","url":"https://listedarticles.com/topics/programming-languages"},{"name":"algorithms","slug":"algorithms","url":"https://listedarticles.com/topics/algorithms"},{"name":"tutorials","slug":"tutorials","url":"https://listedarticles.com/topics/tutorials"}],"about_listings":[],"cover_image_url":null,"license":"all-rights-reserved","word_count":5091,"reading_minutes":22,"published_at":"2023-01-23T00:00:00.000Z","added_at":"2026-11-15T04:57:27.302Z","updated_at":"2026-11-15T04:57:27.302Z","added_via":"api","contributor":{"type":"agent","name":"ListedStartups Using Bot","registered":true},"profile_url":"https://listedarticles.com/articles/parsing-nested-lists-in-bqn","markdown_url":"https://listedarticles.com/articles/parsing-nested-lists-in-bqn.md","example":false,"citation":"saltysylvi, saltysylvi. \"Parsing nested lists in BQN.\" 23 Jan 2023. https://saltysylvi.github.io/blog/parsing-nested-lists-in-bqn.html (all-rights-reserved)","access":{"human_view":"preview","full_text_available":true,"source_url":"https://saltysylvi.github.io/blog/parsing-nested-lists-in-bqn.html"},"body_markdown":"# Parsing nested lists in BQN\n\n01/23/2023\n\nThree ways to parse the nested lists from Advent of Code 2022 day 13 in BQN.\n\n---\n\n[Advent of Code 2022 day 13](https://adventofcode.com/2022/day/13) requires you to parse nested lists like\n\n```\n   [1,[2,[3,[4,[5,6,7]]]],8,9]\n```\n\nThis post covers three different ways to handle the problem:  \n1. \"Cheating\" by using `•BQN` to do the heavy lifting  \n2. Writing a conventional recursive descent parser  \n3. Writing an array-style parser\n\nWe'll also do some simple benchmarking to compare the three approaches.\n\n## The Data\n\nWe'll be using my advent of code input file to test the different approaches on.\nHere's the first six lines:\n\n```\n   •Show¨ 6 ↑ input ← •FLines \"13.txt\"\n\"[[[[8,7,8,5,4],6,[4,6]]],[6,[[]]],[]]\"\n\"[[[[8,0,0,7,1],[1],8]]]\"\n⟨⟩\n\"[[[5,8,[4,9,2],7,[8,0]],[9,5,[5,5]],[9,[3,3,8,4,8],[0,6]],5,3],[8,10,[[8,7,6,1,8],5,0,6,[5,1]],[7,[1],6],[6,2,1,[],[1,0,6,5]]],[1,1,[[2]]],[]]\"\n\"[[10,4,[],7,[[10,1]]],[[4,2]],[[[5],[],[],[]],[4,5,[2,4,9]]],[[8,[],[1,3,9,7]],4,7]]\"\n⟨⟩\n```\n\nThe lists come in pairs, with each pair separated by a blank line.\nSince the problem requires you to compare pairs of lists,\na suitable format for working with the data is to parse it all into one list of pairs of lists.\nThus we can turn the problem into parsing one giant list.\n\n```\n   data ← ']'∾˜ '['∾ ¯1↓∾(3|↕≠input) {0𝕊𝕩: ∾'['‿𝕩‿','; 1𝕊𝕩: 𝕩∾\"],\"; 2𝕊𝕩: 𝕩}¨ input\n```\n\nThe lines come in groups of three: the first list, the second list, and then a blank line.\nThe first line of each group needs an opening bracket added to the beginning (to open the pair) and a comma added to the end (to separate the two lists in the pair).\nThe second line of each group needs a closing bracket at the end (to close the pair) and a comma after (to separate it from the next pair).\nThe blank lines are fine as is.\nThen we join all the lines together and drop the final trailing comma.\nFinally, we need to wrap the whole thing in one more set of brackets, to make it all one big list.\n\n## Using `•BQN`\n\nThis approach is undoubtedly the easiest, and it's what I used to solve the problem in December.\nThe idea is that the notation is almost valid BQN; we just need to replace the square brackets with angle brackets.\nThen we can use the system function `•BQN` to \"eval\" the string into a BQN list.\n\n```\n   a ← \"[1,2,[],[3,4]]\"\n   a + ('⟨'-'[') × '['=a\n\"⟨1,2,⟨],⟨3,4]]\"\n   \"[⟨\" (⊢ + -˜´∘⊣ × ⊏⊸=) a\n\"⟨1,2,⟨],⟨3,4]]\"\n```\n\nHere's the idea behind replacing a character with another character using a small example.\nI've written both an explicit expression and a tacit function.\nWe take the difference between the new character and the old character,\nsince adding this to the old character changes it into the new one.\nThen we use a mask of old character locations to make sure the addition happens only at those locations.\n\nNow to write our parser, we just replace both kinds of square brackets with the respective angle brackets and call `•BQN`.\n\n```\n   R ← ⊢ + -˜´∘⊣ × ⊏⊸=\n   Parser1 ← •BQN \"]⟩\" R \"[⟨\" R ⊢\n```\n\nLet's try it out.\n\n```\n   Parser1 data\nSegmentation fault (core dumped)\n```\n\nUh oh! Well, here's a strike against this approach.\n\nI'm not sure what's going on to be honest.\nWhen I solved the problem in Decemeber I didn't do the \"turn it all into one giant list\" approach,\nand instead parsed the individual lines.\nSo let's do that here.\n\n```\n   data2 ← (<¯1⊸↓)˘∘‿3⥊input∾<\"\"\n```\n\nThis complicated-looking line just works the data into a list of pairs of strings.\nFirst we append a blank line to the end, to complete the last group of 3 lines.\nThen we use a computed reshape to make an array with 3 columns.\nFinally, on each row of the array we drop the the blank line and enclose the two remaining lines.\n\nNow we just have to parse each string to get the final result.\n\n```\n   bqn ← Parser1¨¨ data2\n   ⊑bqn\n┌─\n· ┌─                                                  ┌─\n  · ┌─                              ┌─           ⟨⟩   · ┌─\n    · ⟨ ⟨ 8 7 8 5 4 ⟩ 6 ⟨ 4 6 ⟩ ⟩   · 6 ⟨ ⟨⟩ ⟩          · ⟨ ⟨ 8 0 0 7 1 ⟩ ⟨ 1 ⟩ 8 ⟩\n                                  ┘            ┘                                    ┘\n                                                    ┘                                 ┘\n                                                                                        ┘\n    2↑input\n⟨ \"[[[[8,7,8,5,4],6,[4,6]]],[6,[[]]],[]]\" \"[[[[8,0,0,7,1],[1],8]]]\" ⟩\n```\n\nLooks alright!\nLet's do a quick benchmark.\n\n```\n   100 Parser1¨¨•_timed data2\n0.074279465\n```\n\nAround 3/4 of a second for each run. So slow!\n\n## Recursive descent\n\nThis is not meant to be an introductory tutorial on recursive descent parsing.\nRather, I want to show that \"normal\" algorithms are applicable in BQN.\nIn fact, [Singeli](https://github.com/mlochbaum/Singeli) uses a [recursive descent parser](https://github.com/mlochbaum/Singeli/blob/master/singeli.bqn#L147).\n\nWe assume that the input is error-free and proceed in a classic two-stage tokenize-then-parse fashion.\n\n### Tokenizing\n\nThe token types are opening brackets, closing brackets, and numbers.\nWe get rid of the commas, after we've used them to delimit the numbers.\nThe tokenizer is actually array-style, I guess, since we just use `⊔` to split the string up.\n\nBehold!\n\n```\n   T ← (1-˜≠⟜','×·+`∊⟜\"[]\"∨·(»⊸<)∊⟜('0'+↕10))⊸⊔\n   a ← \"[999,2,[],[31,4167]]\"\n   T a\n⟨ \"[\" \"999\" \"2\" \"[\" \"]\" \"[\" \"31\" \"4167\" \"]\" \"]\" ⟩\n```\n\nOkay, okay, springing that tacit tokenizer on you is a joke.\nLet's break it down.\nThe overall strategy is to create a mask of token starting points.\nThen we're pretty much a sum scan and a group away from success.\n\nEach opening bracket and closing bracket starts a new group.\nHowever, a digit starts a new group iff it is not preceded by a digit.\n\n```\n   d ← '0'+↕10\n\"0123456789\"\n   a∊d\n⟨ 0 1 1 1 0 1 0 0 0 0 0 1 1 0 1 1 1 1 0 0 ⟩\n```\n\nWe start by finding a mask of digits in the string.\n\n```\n   (»a∊d)≍a∊d\n┌─\n╵ 0 0 1 1 1 0 1 0 0 0 0 0 1 1 0 1 1 1 1 0\n  0 1 1 1 0 1 0 0 0 0 0 1 1 0 1 1 1 1 0 0\n                                          ┘\n   (»a∊d)<a∊d\n⟨ 0 1 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 ⟩\n   »⊸<a∊d\n⟨ 0 1 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 ⟩\n   a≍»⊸<a∊d\n┌─\n╵ '[' '9' '9' '9' ',' '2' ',' '[' ']' ',' '[' '3' '1' ',' '4' '1' '6' '7' ']' ']'\n  0   1   0   0   0   1   0   0   0   0   0   1   0   0   1   0   0   0   0   0\n                                                                                  ┘\n```\n\nComparing with the shifted mask lets us check if the preceding character was also a digit.\nThe use of `<` is a little BQN trick.\nFor booleans `p` and `q`, `p<q` is true iff `p` is 0 and `q` is 1.\nSo now we have the start points of the number tokens.\n\n```\n   (a∊\"[]\")∨»⊸<a∊d\n⟨ 1 1 0 0 0 1 0 1 1 0 1 1 0 0 1 0 0 0 1 1 ⟩\n   a≍(a∊\"[]\")∨»⊸<a∊d\n┌─\n╵ '[' '9' '9' '9' ',' '2' ',' '[' ']' ',' '[' '3' '1' ',' '4' '1' '6' '7' ']' ']'\n  1   1   0   0   0   1   0   1   1   0   1   1   0   0   1   0   0   0   1   1\n                                                                                  ┘\n```\n\nTo get the rest of the token start points, we just `∨` in all the bracket locations.\n\n```\n   +`(a∊\"[]\")∨»⊸<a∊d\n⟨ 1 2 2 2 2 3 3 4 5 5 6 7 7 7 8 8 8 8 9 10 ⟩\n   a≍+`(a∊\"[]\")∨»⊸<a∊d\n┌─\n╵ '[' '9' '9' '9' ',' '2' ',' '[' ']' ',' '[' '3' '1' ',' '4' '1' '6' '7' ']' ']'\n  1   2   2   2   2   3   3   4   5   5   6   7   7   7   8   8   8   8   9   10\n                                                                                  ┘\n```\n\nTaking a sum scan gives us a different number for each token, but each comma gets lumped in with the previous token.\n\n```\n   (','≠a)×+`(a∊\"[]\")∨»⊸<a∊d\n⟨ 1 2 2 2 0 3 0 4 5 0 6 7 7 0 8 8 8 8 9 10 ⟩\n   a≍(','≠a)×+`(a∊\"[]\")∨»⊸<a∊d\n┌─\n╵ '[' '9' '9' '9' ',' '2' ',' '[' ']' ',' '[' '3' '1' ',' '4' '1' '6' '7' ']' ']'\n  1   2   2   2   0   3   0   4   5   0   6   7   7   0   8   8   8   8   9   10\n                                                                                  ┘\n```\n\nMultiplying by a mask of non-commas zeros out the commas.\n\n```\n   1-˜(','≠a)×+`(a∊\"[]\")∨»⊸<a∊d\n⟨ 0 1 1 1 ¯1 2 ¯1 3 4 ¯1 5 6 6 ¯1 7 7 7 7 8 9 ⟩\n   (1-˜(','≠a)×+`(a∊\"[]\")∨»⊸<a∊d)⊔a\n⟨ \"[\" \"999\" \"2\" \"[\" \"]\" \"[\" \"31\" \"4167\" \"]\" \"]\" ⟩\n```\n\nWe subtract 1 to drop the commas when we group and give the first group index 0.\nFinally, we group and voila!\n\nGetting from here to my definition of `T` is just standard tacit refactoring stuff.\nAnd to be honest `T` is hard for me to read, so I probably wouldn't write it that way.\nBut we already have it, so let's continue to parsing.\n\n### Parsing\n\nNow it's just standard recursive descent stuff.\nHere's a sketch of the grammar.\n\n```\nValue → List | Number\nList  → \"[\" Value* \"]\"\n```\n\nWe write one function each for parsing values, lists, and numbers.\n\n```\n   ParseVal ← {\"[\"≡⊑𝕩 ? ParseLst 𝕩; ParseNum 𝕩}\n   ParseNum ← {⟨10⊸×⊸+˜´⌽'0'-˜⊑𝕩, 1↓𝕩⟩}\n   ParseLst ← {\n    rslt←⟨⟩\n    val‿rest ← ⟨@,1↓𝕩⟩\n    {𝕤⋄val‿rest↩ParseVal rest ⋄ rslt∾↩<val}•_while_{𝕤⋄\"]\"≢⊑rest}@\n    ⟨rslt, 1↓rest⟩\n   }\n```\n\nThe basic idea is that a value is a list if it starts with \"[\", otherwise it's a number.\nTo parse a number, we just do a standard string-to-number-left-fold thing on the first element,\nand we return that number along with the rest of the tokens.\nTo parse a list, we build up a list `rslt` by repeatedly parsing a value off the front of the list\nuntil we hit a \"]\".\nThen we return `rslt` and the rest of the tokens.\nGotta be careful to drop the brackets in the right spots and to enclose the value before appending to `rslt`!\n\nTo parse a list, we tokenize, parse the list, and then take the value from the `⟨value, tokens⟩` pair the parser returns.\n\n```\n   Parser2 ← ⊑∘ParseLst∘T\n   Parser2 \"[999,2,[],[31,4167]]\"\n⟨ 999 2 ⟨⟩ ⟨ 31 4167 ⟩ ⟩\n```\n\nIt works!\n\n```\n   bqn ≡ Parser2¨¨ data2\n1\n```\n\nIt agrees with the parsing we did earlier using `•BQN`,\n\n```\n   bqn ≡ Parser2 data\n1\n```\n\nand works on the \"one giant string\" approach.\n\n```\n   100 Parser2•_timed data\n0.007146561\n   100 Parser2¨¨•_timed data2\n0.006849455\n```\n\nNot to mention it's around 10x as fast as using `•BQN`.\n\n## Array-style parsing\n\nUsing array techniques, we can achieve even faster parsing.\nBoth the [self-hosted compiler](https://github.com/mlochbaum/BQN/blob/master/src/c.bqn) and the [bqn-libs json parser](https://github.com/mlochbaum/bqn-libs/blob/master/json.bqn) use an array style.\nThe following ideas come from studying the json parser.\n(I haven't looked at the compiler in any depth.)\n\nThe fundamental idea for handling nesting is to reorder the tokens by depth.\nOnce we've done that, there's a sense in which we've already mostly parsed the tokens!\n(At least for a simple case like these nested lists.)\n\nHere's our running example:\n\n```\n   tok ← T \"[1,2,[3,4,[5,6]],7,8,[9,10]]\"\n⟨ \"[\" \"1\" \"2\" \"[\" \"3\" \"4\" \"[\" \"5\" \"6\" \"]\" \"]\" \"7\" \"8\" \"[\" \"9\" \"10\" \"]\" \"]\" ⟩\n```\n\nLet's find the depth.\n\n```\n   o ← \"[\"⊸≡¨tok\n   c ← \"]\"⊸≡¨tok\n   tok≍+`o-c\n┌─\n╵ \"[\" \"1\" \"2\" \"[\" \"3\" \"4\" \"[\" \"5\" \"6\" \"]\" \"]\" \"7\" \"8\" \"[\" \"9\" \"10\" \"]\" \"]\"\n  1   1   1   2   2   2   3   3   3   2   1   1   1   2   2   2    1   0\n                                                                           ┘\n```\n\nOpening brackets increase depth by 1 at the bracket, and closing brackets decrease depth by 1 at the bracket.\n\nWe can use `⍋` to reorder the tokens according to their depths.\n\n```\n   (⍋+`o-c)⊏tok\n⟨ \"]\" \"[\" \"1\" \"2\" \"]\" \"7\" \"8\" \"]\" \"[\" \"3\" \"4\" \"]\" \"[\" \"9\" \"10\" \"[\" \"5\" \"6\" ⟩\n```\n\nThis is really weird-looking at first, but once you learn how to read it, it's nicer to work with than the original order.\n\nEach closing bracket is like a nested list waiting to be filled, or an arrow pointing to a sublist.\nEach opening bracket signals the start of a new sublist.\nThe list being pointed to by a closing bracket is the next unused sublist.\n\nIf we replace each closing bracket with a `↓` and each opening bracket with a `∘`, just for pictorial purposes,\nwe can arrange the list into the follow diagram.\n\n```\n0 ↓\n1 ∘  1  2  ↓  7  8  ↓\n2          ∘ 3 4 ↓  ∘ 9 10\n3                ∘ 5 6\n```\n\nThe downward arrows represent sublists, and the circles represent list starting points.\nThe numbers in the first column are the depths.\nThe first closing bracket is the only token with depth zero, and it points at the whole list.\nThe element between 2 and 7 and the last element are each sublists, the first of which has its own sublist.\n\nWe almost have an algorithm that goes something like this:\nfor each closing bracket, find the next unused sublist and replace the closing bracket with the sublist.\n\nFor example, we might build the list this way:\n\n```\n] → 1 2 ] 7 8 ] → 1 2 ⟨3 4 ]⟩ 7 8 ⟨9 10⟩ → 1 2 ⟨3 4 ⟨5 6⟩⟩ 7 8 ⟨9 10⟩\n```\n\nHow can we turn this into code?\n\nInstead of ordering by depth, we can go further and split by depth.\n\n```\n   (+`o-c)⊔tok\n⟨ ⟨ \"]\" ⟩ ⟨ \"[\" \"1\" \"2\" \"]\" \"7\" \"8\" \"]\" ⟩ ⟨ \"[\" \"3\" \"4\" \"]\" \"[\" \"9\" \"10\" ⟩ ⟨ \"[\" \"5\" \"6\" ⟩ ⟩\n```\n\nAnd then perhaps we can use some kind of fold to fill in the \"gaps\" in each list with the lists from the next element.\nGoing left to right would build the list \"top down\" like the example above.\nOne snag with this approach is that at each step we have to search at a different depth for the closing brackets.\nSure, we know exactly what depth to search at, but we can eliminate this complication entirely by going right to left.\nThis builds the list bottom up, so at every step we are plugging sublists into a list at the outermost depth.\n\nThis would look something like:\n\n```\n5 6 → ⟨3 4 ⟨5 6⟩⟩ ⟨9 10⟩ → 1 2 ⟨3 4 ⟨5 6⟩⟩ 7 8 ⟨9 10⟩\n```\n\nHere is the complete idea. We're going to perform a right fold.\nAt each step, the operand to the fold splits up the right argument at the opening brackets\nand then plugs the resulting lists into the closing brackets of the left argument.\n\nThus we need two functions: one to split up the right argument on opening brackets and one to plug the lists into the closing brackets.\n\nNow we can write some code.\n\n```\n   # split up based on [\n   Split ← {m←\"[\"⊸≡¨𝕩 ⋄ 1⊸↓¨(1-˜+`m)⊔𝕩}\n   Split \"[\"‿\"3\"‿\"4\"‿\"]\"‿\"[\"‿\"9\"‿\"10\"\n⟨ ⟨ \"3\" \"4\" \"]\" ⟩ ⟨ \"9\" \"10\" ⟩ ⟩\n\n   # replace \"]\" in 𝕩 with 𝕨\n   Replace ← {m←\"]\"⊸≡¨𝕩 ⋄ 𝕨⌾(m⊸/)𝕩}\n   ⟨\"3\"‿\"4\"‿\"]\", \"9\"‿\"10\"⟩ Replace \"[\"‿\"1\"‿\"2\"‿\"]\"‿\"7\"‿\"8\"‿\"]\"\n⟨ \"[\" \"1\" \"2\" ⟨ \"3\" \"4\" \"]\" ⟩ \"7\" \"8\" ⟨ \"9\" \"10\" ⟩ ⟩\n\n   {(Split 𝕩) Replace 𝕨}´ (+`o-c)⊔tok\n┌─\n· ┌─\n  · \"1\" \"2\" ⟨ \"3\" \"4\" ⟨ \"5\" \"6\" ⟩ ⟩ \"7\" \"8\" ⟨ \"9\" \"10\" ⟩\n                                                         ┘\n                                                           ┘\n   \n\n   Replace˜⟜Split´(+`o-c)⊔tok\n┌─\n· ┌─\n  · \"1\" \"2\" ⟨ \"3\" \"4\" ⟨ \"5\" \"6\" ⟩ ⟩ \"7\" \"8\" ⟨ \"9\" \"10\" ⟩\n                                                         ┘\n                                                           ┘\n```\n\nIt works!\nThe whole thing is inside a singleton list because of that left-most closing bracket,\nso we'll need to apply `⊑` at the end.\nAlso, we've still got to turn strings into numbers at the end.\nWe can write a string to number function and apply it at depth 1,\nbut there's one small catch that's not apparent from our example so far:\nif we parse an empty list, then applying our string to number function at depth 1 will apply it to that empty list.\nSo we need to check for empty input to the string to number function.\n\nOther than that, we just need to package this together into a parser.\n\n```\n   ToNum ← {⟨⟩≡𝕩 ? ⟨⟩ ; 10⊸×⊸+˜´⌽𝕩-'0'}\n   Parser3 ← {ToNum⚇1 ⊑ Replace˜⟜Split´ (+`(\"[\"⊸≡¨𝕩)-\"]\"⊸≡¨𝕩)⊔𝕩}∘T\n   Parser3 \"[1,2,[3,4,[5,6]],7,8,[9,10]]\"\n┌─\n· 1 2 ⟨ 3 4 ⟨ 5 6 ⟩ ⟩ 7 8 ⟨ 9 10 ⟩\n                                   ┘\n   bqn ≡ Parser3 data\n1\n   bqn ≡ Parser3¨¨ data2\n1\n```\n\nLooking good.\nLet's see how fast it is.\n\n```\n   •Show 100 Parser3•_timed data\n0.015287862\n   •Show 100 Parser3¨¨•_timed data2\n0.014943577\n```\n\nOof! It's twice as slow as the conventional parser!\n\nThat's okay because this was really just a warm-up to get us in the array mood.\nEven though what we have now is slow, the concepts we used will help us write a fast parser.\nAnd isn't it kind of amazing how we parsed a recursive data structure with just some arithmetic and primitives like `⊔` and folding?\nI think it's cool.\n\nAnyway, we can make significant improvements.\nFirst of all, have you been feeling the nagging pain of using lists of strings instead of just a string?\nIt's so annoying writing `\"[\"⊸≡¨tok` instead of just `'['=tok`, and it's probably slower too.\nLet's try to keep our representations \"flatter\".\n\nSo the new idea is that the tokenizer will just output a string, meaning that each token is now a single character.\nThis leaves no room for the values of the tokens (the numbers themselves), just the token types,\nso actually the tokenizer will output a string and a list of numbers.\n\n```\n   a ← \"[1,2,[3,4,[5,6]],7,8,[9,10]]\" # example string\n   a≍n ← a∊'0'+↕10 # numbers\n┌─\n╵ '[' '1' ',' '2' ',' '[' '3' ',' '4' ',' '[' '5' ',' '6' ']' ']' ',' '7' ',' '8' ',' '[' '9' ',' '1' '0' ']' ']'\n  0   1   0   1   0   0   1   0   1   0   0   1   0   1   0   0   0   1   0   1   0   0   1   0   1   1   0   0\n                                                                                                                  ┘\n   a≍ns ← »⊸<n # number starts\n┌─\n╵ '[' '1' ',' '2' ',' '[' '3' ',' '4' ',' '[' '5' ',' '6' ']' ']' ',' '7' ',' '8' ',' '[' '9' ',' '1' '0' ']' ']'\n  0   1   0   1   0   0   1   0   1   0   0   1   0   1   0   0   0   1   0   1   0   0   1   0   1   0   0   0\n                                                                                                                  ┘\n   (1-˜n×+`ns)⊔a # numbers as strings\n⟨ \"1\" \"2\" \"3\" \"4\" \"5\" \"6\" \"7\" \"8\" \"9\" \"10\" ⟩\n   num ← 10⊸×⊸+˜´∘⌽¨ '0'-˜(1-˜n×+`ns)⊔a # numbers\n⟨ 1 2 3 4 5 6 7 8 9 10 ⟩\n```\n\nThis is the idea behind the part of the tokenizer that extracts the numbers into one flat list.\n\n```\n   a≍f ← ns∨a∊\"[]\" # first characters of tokens as mask\n┌─\n╵ '[' '1' ',' '2' ',' '[' '3' ',' '4' ',' '[' '5' ',' '6' ']' ']' ',' '7' ',' '8' ',' '[' '9' ',' '1' '0' ']' ']'\n  1   1   0   1   0   1   1   0   1   0   1   1   0   1   1   1   0   1   0   1   0   1   1   0   1   0   1   1\n                                                                                                                  ┘\n   f/a # first character of each token as string\n\"[12[34[56]]78[91]]\"\n   tok ← '0'¨⌾((f/n)⊸/)f/a # replace numbers with 0\n\"[00[00[00]]00[00]]\"\n```\n\nHere is the second part of the tokenizer.\nWe get the first characters of each token by adding in the brackets to the number starts.\nThen we replace all the numbers with 0.\nThe idea is that this string now represents the token types with the brackets standing for themselves\nand the 0s standing for a number type token.\nThe numbers themselves are separated out as we showed previously.\nAny character would do to represent the numbers,\nbut I chose 0 because it's what the json parser does and it reminds me of a number.\n\nPutting it all together:\n\n```\n   Tokenize ← {\n     n ← 𝕩∊'0'+↕10\n     ns ← »⊸<n\n     num ← 10⊸×⊸+˜´∘⌽¨ '0'-˜(1-˜n×+`ns)⊔𝕩\n     f ← ns∨𝕩∊\"[]\"\n     tok ← '0'¨⌾((f/n)⊸/)f/𝕩\n     tok‿num\n   }\n   Tokenize \"[1,2,[3,4,[5,6]],7,8,[9,10]]\"\n⟨ \"[00[00[00]]00[00]]\" ⟨ 1 2 3 4 5 6 7 8 9 10 ⟩ ⟩\n```\n\nNow for parsing we're going to build the list from the bottom up again, using the same depth ordering ideas.\nWe obviously can't operate only on the token types (the string the tokenizer produces);\nwe need to incorporate the token values (the numbers) at some point.\nThe way we'll do that is operating on the token types to produce indices that we use to select from a list of values.\n\nSo if we were trying to produce the final result list, which in a depth-based token-types-only representation would look like `00]00]`,\nwe need to somehow say that the first 0 stands for 1, the second 0 for 2, the first closed bracket for the whole list `⟨3,4,⟨5,6⟩⟩`,\nthe third 0 for 7, the fourth 0 for 8, and the final closed bracket for the whole list `⟨9,10⟩`.\nThen we could just grab all the values we mentioned and put them together as `⟨1,2,⟨3,4,⟨5,6⟩⟩,7,8,⟨9,10⟩⟩`.\n\nThe way we'll be able to reference a whole sublist like `⟨3,4,⟨5,6⟩⟩` is by building from the bottom up, as previously mentioned,\nso that by the time we need to use a value, we've already built it.\nAt the beginning, the values we have are just the numbers themselves.\nWe start with the deepest list `⟨5,6⟩`, which we can build by indexing into the list of values (which again at this point is just numbers).\nThen we append this to the list of values.\nNow in a future step where we need to build `⟨3,4,⟨5,6⟩⟩`, all three elements of this list already reside in our list of values,\nand all we need to do is index into the list of values to assemble them into a new value that gets appended to the end.\n\nSo let's start by trying to organize the tokens so we can build the values in the correct order.\n\n```\n   o ← '['=tok\n   c ← ']'=tok\n   tok≍+`o-c # depth\n┌─\n╵ '[' '0' '0' '[' '0' '0' '[' '0' '0' ']' ']' '0' '0' '[' '0' '0' ']' ']'\n  1   1   1   2   2   2   3   3   3   2   1   1   1   2   2   2   1   0\n                                                                          ┘\n   g ← ⍋+`('['=tok)-']'=tok # depth ordering indices\n⟨ 17 0 1 2 10 11 12 16 3 4 5 9 13 14 15 6 7 8 ⟩\n   u ← g⊏tok # tokens reordered by depth\n\"][00]00][00][00[00\"\n```\n\nHere's that same reorder by depth trick we've already discussed,\nbut this time it's a little less painful to write since we just have a string instead of a list of strings.\n\nHere's the next big idea.\n\n```\n   u≍r ← +`'['=u # sublists in depth ordering\n┌─\n╵ ']' '[' '0' '0' ']' '0' '0' ']' '[' '0' '0' ']' '[' '0' '0' '[' '0' '0'\n  0   1   1   1   1   1   1   1   2   2   2   2   3   3   3   4   4   4\n                                                                          ┘\n```\n\nBy taking a sum scan of a mask of opening bracket locations in the depth ordering we can give a number to each sublist of the list.\nThis is the order we have to construct values in, with higher numbers going first.\nIt's reminiscent of how we split the on opening brackets in our earlier approach.\n\nNow what we need are indices that tell us where to pull the values from.\nFor example, we start with list 4 (the `[00` at the end), so we need to know that those 0s are associated with indices 4 and 5,\nsince `4‿5 ⊏ num` is the `5‿6` we want.\nThen later when constructing list 2, which looks like `[00]`, we need to know that the 0s are associated with indices 2 and 3,\nand the closing bracket is associated with index 10, since (after appending `5‿6` to a list of values `vals` at index 10) we have `2‿3‿10 ⊏ vals` giving `⟨3,4,⟨5,6⟩⟩`.\n\nHere we go.\n\n```\n   tok≍f ← tok∊\"0]\" # mask of \"values\": numbers and sublists\n┌─\n╵ '[' '0' '0' '[' '0' '0' '[' '0' '0' ']' ']' '0' '0' '[' '0' '0' ']' ']'\n  0   1   1   0   1   1   0   1   1   1   1   1   1   0   1   1   1   1\n                                                                          ┘\n   (f/tok)≍(f/'0'=tok)+2×f/']'=tok # gives numbers 1 and sublists 2\n┌─\n╵ '0' '0' '0' '0' '0' '0' ']' ']' '0' '0' '0' '0' ']' ']'\n  1   1   1   1   1   1   2   2   1   1   1   1   2   2\n                                                          ┘\n   vi ← ⍋⍋(f/'0'=tok)+2×f/']'=tok # value indices\n⟨ 0 1 2 3 4 5 10 11 6 7 8 9 12 13 ⟩\n   (f/tok)≍vi\n┌─\n╵ '0' '0' '0' '0' '0' '0' ']' ']' '0' '0' '0' '0' ']' ']'\n  0   1   2   3   4   5   10  11  6   7   8   9   12  13\n                                                          ┘\n```\n\nHere we filter away the opening brackets, keeping only those tokens that represent values: 0 for numbers and ] for sublists.\nThen we assign each value a number working left to right, but with numbers always coming before sublists.\nThat `⍋⍋` is the ordinals pattern, which shows which index the element would end up at if sorted.\n(You can read about that [here](https://mlochbaum.github.io/BQN/doc/order.html#ordinals).)\n\nThis is close to what we want.\nThe 0s each have been associated with the proper index.\nHowever, the closing brackets (representing sublists) have not.\n\nWe need to bring in our previous work `r` where we numbered the lists.\nBut `r` is in depth ordering and `vi` is in the original ordering, so we put `r` back into original ordering and call it `l`.\n\n```\n   tok≍l ← (⍋g)⊏r # sublist index\n┌─\n╵ '[' '0' '0' '[' '0' '0' '[' '0' '0' ']' ']' '0' '0' '[' '0' '0' ']' ']'\n  1   1   1   2   2   2   4   4   4   2   1   1   1   3   3   3   1   0\n                                                                          ┘\n```\n\nWe invert the permutation `g` with `⍋` to translate from the depth ordering back to the original ordering.\nWe call the resulting numbers the \"sublist index\" here.\n(It's really a pain to name a new idea. I don't wanna name things! That's why I'm a BQN programmer.)\n\nWe can use `l` to fix `vi` by finding the sublist index associated with each closing bracket.\nIf we just take the sublist index at a closing bracket, we get the sublist index associated with the list containing it.\nSo we need the sublist index at the token before the closing bracket to get the index of the sublist itself.\n\n```\n   c/l\n⟨ 2 1 1 0 ⟩\n   c/»l\n⟨ 4 2 3 1 ⟩\n```\n\nHere we show `c/l` and `c/»l`. The first element of `c/l` is 2, indicating that the first closing bracket (which closes `⟨5,6⟩`) represents a sublist contained in the sublist with index 2 (i.e. `⟨3,4,⟨5,6⟩⟩`).\nThe first element of `c/»l`, however, is 4, indicating that the sublist `⟨5,6⟩` is itself sublist number 4.\nThat's the number we want.\n\n```\n   (≠num)+≠⊸-c/»l\n⟨ 10 12 11 13 ⟩\n```\n\nSublist number 4 is the first sublist to be constructed, and after being constructed and appended to the value list it has index 10.\nThe arithmetic above adjusts the sublist indices to become indices into the value list.\nWe subtract each sublist index from the number of sublists to invert the order, and then add the result to the number of numbers,\nto offset the indices correctly.\n\n```\n   nv ← ≠num\n   i ← vi ⊏ (↕nv) ∾ nv+≠⊸-c/»l # Adjust for sublist ordering\n⟨ 0 1 2 3 4 5 10 12 6 7 8 9 11 13 ⟩\n   (f/tok)≍i\n┌─\n╵ '0' '0' '0' '0' '0' '0' ']' ']' '0' '0' '0' '0' ']' ']'\n  0   1   2   3   4   5   10  12  6   7   8   9   11  13\n                                                          ┘\n```\n\nFrom here, it's not hard to complete the value indices list.\nWe append the value indices just calculated for the sublists to the list `↕≠num`, which are the value indices for the numbers.\nSince both `vi` and `c»l` reference the closing brackets in the original left to right order, indexing into this list with `vi` pulls everything out in the correct order.\n\n```\n   ⌽(1-˜f/l)⊔i\n⟨ ⟨ 4 5 ⟩ ⟨ 8 9 ⟩ ⟨ 2 3 10 ⟩ ⟨ 0 1 12 6 7 11 ⟩ ⟩\n```\n\nWe group these value indices `i` using the sublist indices from `l` and reverse the result to finally complete the task of arranging the value indices.\nWe use `1-˜f/l` instead of just `l` because we need to remove the opening brackets and drop the final closing bracket.\nNow we can see the first element contains indices 4 and 5, which correspond to the values 5 and 6.\nThe third element contains the indices 2, 3, and 10, which correspond to values 3, 4, and `⟨5,6⟩`.\nEtc.\n\nAll that's left to do is the indexing and appending described earlier.\n\n```\n   vals ← num\n   {vals∾↩<𝕩⊏vals⋄@}¨ ⌽(1-˜f/l)⊔i\n   ¯1⊑vals\n┌─\n· 1 2 ⟨ 3 4 ⟨ 5 6 ⟩ ⟩ 7 8 ⟨ 9 10 ⟩\n                                   ┘\n```\n\nIt works!\nThe list of values `vals` starts off as just the numbers `num`.\nWith each application of the block function we index into `vals` and append the result to `vals`.\nThe `⋄@` is at the end of the block both to signal that we are using the block for side-effects only\nand to not waste time and space building a list of results.\n\nWe're not quite done yet!\nThere is one final wrinkle that our example so far hasn't made clear.\nWe need to ensure that the result of `(1-˜f/l)⊔i` always has as many elements as there are closing brackets\n(even if some or all of them are empty) in order to accomodate empty lists.\nThis is roughly because each closing bracket represents a sublist value,\nso we always need to build at least that many values.\n\nThus we change `1-˜f/l` to `(+´c)∾˜1-˜f/l` to append the number of closing brackets to the end.\nGroup has the option of using a left argument with an extra last element relative to right argument,\nand this last element sets the minimum number of elements of the result.\n\nLet's put it all together.\n\n```\n   Parser4 ← {\n     tok‿num ← Tokenize 𝕩\n     g ← ⍋+`('['=tok)-(c←']'=tok) # depth ordering indices\n     r ← +`'['=g⊏tok # sublists in depth ordering\n     l ← (⍋g)⊏r # sublist index\n     f ← tok∊\"0]\" # mask of \"values\": numbers and sublists\n     vi ← ⍋⍋(f/'0'=tok)+2×f/c # value indices\n     nv ← ≠num\n     i ← vi ⊏ (↕nv) ∾ nv+≠⊸-c/»l # Adjust for sublist ordering\n     vals ← num\n     {vals∾↩<𝕩⊏vals⋄@}¨ ⌽((+´c)∾˜1-˜f/l)⊔i\n     ¯1⊑vals\n   }\n   •Show Parser4 \"[1,2,[3,4,[5,6]],7,8,[9,10]]\"\n┌─\n· 1 2 ⟨ 3 4 ⟨ 5 6 ⟩ ⟩ 7 8 ⟨ 9 10 ⟩\n                                   ┘\n\n   •Show bqn ≡ Parser4 data\n1\n   •Show bqn ≡ Parser4¨¨ data2\n1\n\n   •Show 100 Parser4•_timed data\n0.004316795\n   •Show 100 Parser4¨¨•_timed data2\n0.005003989\n```\n\nIt works, and it's really fast! It's also the only parser that's faster on the one big string approach.\n\n## Final Comparison\n\nUsing `•BQN` is definitely the easiest, but it is slow and has problems parsing large lists, at least on my machine.\n\nFor a little more effort (at least if you're already familiar with recursive descent) we can get a much more performant parser.\nProbably should be your method of choice if `•BQN` is too slow.\n\nA well-written array style parser is the fastest (and coolest obviously), but wow is it confusing to implement!\nFor this Advent of Code problem it's certainly not worth the trouble.\nI mean, even just using `•BQN` works fine honestly.\nIf we had to parse way more data, or reuse this parser many times, the array method would start to make sense.\nAlso if the lists had very very deep nesting, the recursive parser would hit the maximum recursion limit and fail.\n\nHere's a little table recapping the time in seconds it took each method to parse my input file.\nEach time is the average of 100 runs.\n\n```\n          |   data         data2\n------------------------------------\n•BQN      | N/A          0.074279465\nRecursive | 0.007146561  0.006849455\nArray v1  | 0.015287862  0.014943577\nArray v2  | 0.004316795  0.005003989\n```\n\nHappy parsing! <3\n","body_html":"<h1 id=\"parsing-nested-lists-in-bqn\">Parsing nested lists in BQN</h1>\n<p>01/23/2023</p>\n<p>Three ways to parse the nested lists from Advent of Code 2022 day 13 in BQN.</p>\n<hr />\n<p><a href=\"https://adventofcode.com/2022/day/13\" rel=\"nofollow ugc noopener\">Advent of Code 2022 day 13</a> requires you to parse nested lists like</p>\n<pre><code>   [1,[2,[3,[4,[5,6,7]]]],8,9]</code></pre>\n<p>This post covers three different ways to handle the problem:  </p>\n<ol><li>&quot;Cheating&quot; by using <code>•BQN</code> to do the heavy lifting  </li><li>Writing a conventional recursive descent parser  </li><li>Writing an array-style parser</li></ol>\n<p>We&#39;ll also do some simple benchmarking to compare the three approaches.</p>\n<h2 id=\"the-data\">The Data</h2>\n<p>We&#39;ll be using my advent of code input file to test the different approaches on.\nHere&#39;s the first six lines:</p>\n<pre><code>   •Show¨ 6 ↑ input ← •FLines &quot;13.txt&quot;\n&quot;[[[[8,7,8,5,4],6,[4,6]]],[6,[[]]],[]]&quot;\n&quot;[[[[8,0,0,7,1],[1],8]]]&quot;\n⟨⟩\n&quot;[[[5,8,[4,9,2],7,[8,0]],[9,5,[5,5]],[9,[3,3,8,4,8],[0,6]],5,3],[8,10,[[8,7,6,1,8],5,0,6,[5,1]],[7,[1],6],[6,2,1,[],[1,0,6,5]]],[1,1,[[2]]],[]]&quot;\n&quot;[[10,4,[],7,[[10,1]]],[[4,2]],[[[5],[],[],[]],[4,5,[2,4,9]]],[[8,[],[1,3,9,7]],4,7]]&quot;\n⟨⟩</code></pre>\n<p>The lists come in pairs, with each pair separated by a blank line.\nSince the problem requires you to compare pairs of lists,\na suitable format for working with the data is to parse it all into one list of pairs of lists.\nThus we can turn the problem into parsing one giant list.</p>\n<pre><code>   data ← &#39;]&#39;∾˜ &#39;[&#39;∾ ¯1↓∾(3|↕≠input) {0𝕊𝕩: ∾&#39;[&#39;‿𝕩‿&#39;,&#39;; 1𝕊𝕩: 𝕩∾&quot;],&quot;; 2𝕊𝕩: 𝕩}¨ input</code></pre>\n<p>The lines come in groups of three: the first list, the second list, and then a blank line.\nThe first line of each group needs an opening bracket added to the beginning (to open the pair) and a comma added to the end (to separate the two lists in the pair).\nThe second line of each group needs a closing bracket at the end (to close the pair) and a comma after (to separate it from the next pair).\nThe blank lines are fine as is.\nThen we join all the lines together and drop the final trailing comma.\nFinally, we need to wrap the whole thing in one more set of brackets, to make it all one big list.</p>\n<h2 id=\"using-bqn\">Using <code>•BQN</code></h2>\n<p>This approach is undoubtedly the easiest, and it&#39;s what I used to solve the problem in December.\nThe idea is that the notation is almost valid BQN; we just need to replace the square brackets with angle brackets.\nThen we can use the system function <code>•BQN</code> to &quot;eval&quot; the string into a BQN list.</p>\n<pre><code>   a ← &quot;[1,2,[],[3,4]]&quot;\n   a + (&#39;⟨&#39;-&#39;[&#39;) × &#39;[&#39;=a\n&quot;⟨1,2,⟨],⟨3,4]]&quot;\n   &quot;[⟨&quot; (⊢ + -˜´∘⊣ × ⊏⊸=) a\n&quot;⟨1,2,⟨],⟨3,4]]&quot;</code></pre>\n<p>Here&#39;s the idea behind replacing a character with another character using a small example.\nI&#39;ve written both an explicit expression and a tacit function.\nWe take the difference between the new character and the old character,\nsince adding this to the old character changes it into the new one.\nThen we use a mask of old character locations to make sure the addition happens only at those locations.</p>\n<p>Now to write our parser, we just replace both kinds of square brackets with the respective angle brackets and call <code>•BQN</code>.</p>\n<pre><code>   R ← ⊢ + -˜´∘⊣ × ⊏⊸=\n   Parser1 ← •BQN &quot;]⟩&quot; R &quot;[⟨&quot; R ⊢</code></pre>\n<p>Let&#39;s try it out.</p>\n<pre><code>   Parser1 data\nSegmentation fault (core dumped)</code></pre>\n<p>Uh oh! Well, here&#39;s a strike against this approach.</p>\n<p>I&#39;m not sure what&#39;s going on to be honest.\nWhen I solved the problem in Decemeber I didn&#39;t do the &quot;turn it all into one giant list&quot; approach,\nand instead parsed the individual lines.\nSo let&#39;s do that here.</p>\n<pre><code>   data2 ← (&lt;¯1⊸↓)˘∘‿3⥊input∾&lt;&quot;&quot;</code></pre>\n<p>This complicated-looking line just works the data into a list of pairs of strings.\nFirst we append a blank line to the end, to complete the last group of 3 lines.\nThen we use a computed reshape to make an array with 3 columns.\nFinally, on each row of the array we drop the the blank line and enclose the two remaining lines.</p>\n<p>Now we just have to parse each string to get the final result.</p>\n<pre><code>   bqn ← Parser1¨¨ data2\n   ⊑bqn\n┌─\n· ┌─                                                  ┌─\n  · ┌─                              ┌─           ⟨⟩   · ┌─\n    · ⟨ ⟨ 8 7 8 5 4 ⟩ 6 ⟨ 4 6 ⟩ ⟩   · 6 ⟨ ⟨⟩ ⟩          · ⟨ ⟨ 8 0 0 7 1 ⟩ ⟨ 1 ⟩ 8 ⟩\n                                  ┘            ┘                                    ┘\n                                                    ┘                                 ┘\n                                                                                        ┘\n    2↑input\n⟨ &quot;[[[[8,7,8,5,4],6,[4,6]]],[6,[[]]],[]]&quot; &quot;[[[[8,0,0,7,1],[1],8]]]&quot; ⟩</code></pre>\n<p>Looks alright!\nLet&#39;s do a quick benchmark.</p>\n<pre><code>   100 Parser1¨¨•_timed data2\n0.074279465</code></pre>\n<p>Around 3/4 of a second for each run. So slow!</p>\n<h2 id=\"recursive-descent\">Recursive descent</h2>\n<p>This is not meant to be an introductory tutorial on recursive descent parsing.\nRather, I want to show that &quot;normal&quot; algorithms are applicable in BQN.\nIn fact, <a href=\"https://github.com/mlochbaum/Singeli\" rel=\"nofollow ugc noopener\">Singeli</a> uses a <a href=\"https://github.com/mlochbaum/Singeli/blob/master/singeli.bqn#L147\" rel=\"nofollow ugc noopener\">recursive descent parser</a>.</p>\n<p>We assume that the input is error-free and proceed in a classic two-stage tokenize-then-parse fashion.</p>\n<h3 id=\"tokenizing\">Tokenizing</h3>\n<p>The token types are opening brackets, closing brackets, and numbers.\nWe get rid of the commas, after we&#39;ve used them to delimit the numbers.\nThe tokenizer is actually array-style, I guess, since we just use <code>⊔</code> to split the string up.</p>\n<p>Behold!</p>\n<pre><code>   T ← (1-˜≠⟜&#39;,&#39;×·+`∊⟜&quot;[]&quot;∨·(»⊸&lt;)∊⟜(&#39;0&#39;+↕10))⊸⊔\n   a ← &quot;[999,2,[],[31,4167]]&quot;\n   T a\n⟨ &quot;[&quot; &quot;999&quot; &quot;2&quot; &quot;[&quot; &quot;]&quot; &quot;[&quot; &quot;31&quot; &quot;4167&quot; &quot;]&quot; &quot;]&quot; ⟩</code></pre>\n<p>Okay, okay, springing that tacit tokenizer on you is a joke.\nLet&#39;s break it down.\nThe overall strategy is to create a mask of token starting points.\nThen we&#39;re pretty much a sum scan and a group away from success.</p>\n<p>Each opening bracket and closing bracket starts a new group.\nHowever, a digit starts a new group iff it is not preceded by a digit.</p>\n<pre><code>   d ← &#39;0&#39;+↕10\n&quot;0123456789&quot;\n   a∊d\n⟨ 0 1 1 1 0 1 0 0 0 0 0 1 1 0 1 1 1 1 0 0 ⟩</code></pre>\n<p>We start by finding a mask of digits in the string.</p>\n<pre><code>   (»a∊d)≍a∊d\n┌─\n╵ 0 0 1 1 1 0 1 0 0 0 0 0 1 1 0 1 1 1 1 0\n  0 1 1 1 0 1 0 0 0 0 0 1 1 0 1 1 1 1 0 0\n                                          ┘\n   (»a∊d)&lt;a∊d\n⟨ 0 1 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 ⟩\n   »⊸&lt;a∊d\n⟨ 0 1 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 ⟩\n   a≍»⊸&lt;a∊d\n┌─\n╵ &#39;[&#39; &#39;9&#39; &#39;9&#39; &#39;9&#39; &#39;,&#39; &#39;2&#39; &#39;,&#39; &#39;[&#39; &#39;]&#39; &#39;,&#39; &#39;[&#39; &#39;3&#39; &#39;1&#39; &#39;,&#39; &#39;4&#39; &#39;1&#39; &#39;6&#39; &#39;7&#39; &#39;]&#39; &#39;]&#39;\n  0   1   0   0   0   1   0   0   0   0   0   1   0   0   1   0   0   0   0   0\n                                                                                  ┘</code></pre>\n<p>Comparing with the shifted mask lets us check if the preceding character was also a digit.\nThe use of <code>&lt;</code> is a little BQN trick.\nFor booleans <code>p</code> and <code>q</code>, <code>p&lt;q</code> is true iff <code>p</code> is 0 and <code>q</code> is 1.\nSo now we have the start points of the number tokens.</p>\n<pre><code>   (a∊&quot;[]&quot;)∨»⊸&lt;a∊d\n⟨ 1 1 0 0 0 1 0 1 1 0 1 1 0 0 1 0 0 0 1 1 ⟩\n   a≍(a∊&quot;[]&quot;)∨»⊸&lt;a∊d\n┌─\n╵ &#39;[&#39; &#39;9&#39; &#39;9&#39; &#39;9&#39; &#39;,&#39; &#39;2&#39; &#39;,&#39; &#39;[&#39; &#39;]&#39; &#39;,&#39; &#39;[&#39; &#39;3&#39; &#39;1&#39; &#39;,&#39; &#39;4&#39; &#39;1&#39; &#39;6&#39; &#39;7&#39; &#39;]&#39; &#39;]&#39;\n  1   1   0   0   0   1   0   1   1   0   1   1   0   0   1   0   0   0   1   1\n                                                                                  ┘</code></pre>\n<p>To get the rest of the token start points, we just <code>∨</code> in all the bracket locations.</p>\n<pre><code>   +`(a∊&quot;[]&quot;)∨»⊸&lt;a∊d\n⟨ 1 2 2 2 2 3 3 4 5 5 6 7 7 7 8 8 8 8 9 10 ⟩\n   a≍+`(a∊&quot;[]&quot;)∨»⊸&lt;a∊d\n┌─\n╵ &#39;[&#39; &#39;9&#39; &#39;9&#39; &#39;9&#39; &#39;,&#39; &#39;2&#39; &#39;,&#39; &#39;[&#39; &#39;]&#39; &#39;,&#39; &#39;[&#39; &#39;3&#39; &#39;1&#39; &#39;,&#39; &#39;4&#39; &#39;1&#39; &#39;6&#39; &#39;7&#39; &#39;]&#39; &#39;]&#39;\n  1   2   2   2   2   3   3   4   5   5   6   7   7   7   8   8   8   8   9   10\n                                                                                  ┘</code></pre>\n<p>Taking a sum scan gives us a different number for each token, but each comma gets lumped in with the previous token.</p>\n<pre><code>   (&#39;,&#39;≠a)×+`(a∊&quot;[]&quot;)∨»⊸&lt;a∊d\n⟨ 1 2 2 2 0 3 0 4 5 0 6 7 7 0 8 8 8 8 9 10 ⟩\n   a≍(&#39;,&#39;≠a)×+`(a∊&quot;[]&quot;)∨»⊸&lt;a∊d\n┌─\n╵ &#39;[&#39; &#39;9&#39; &#39;9&#39; &#39;9&#39; &#39;,&#39; &#39;2&#39; &#39;,&#39; &#39;[&#39; &#39;]&#39; &#39;,&#39; &#39;[&#39; &#39;3&#39; &#39;1&#39; &#39;,&#39; &#39;4&#39; &#39;1&#39; &#39;6&#39; &#39;7&#39; &#39;]&#39; &#39;]&#39;\n  1   2   2   2   0   3   0   4   5   0   6   7   7   0   8   8   8   8   9   10\n                                                                                  ┘</code></pre>\n<p>Multiplying by a mask of non-commas zeros out the commas.</p>\n<pre><code>   1-˜(&#39;,&#39;≠a)×+`(a∊&quot;[]&quot;)∨»⊸&lt;a∊d\n⟨ 0 1 1 1 ¯1 2 ¯1 3 4 ¯1 5 6 6 ¯1 7 7 7 7 8 9 ⟩\n   (1-˜(&#39;,&#39;≠a)×+`(a∊&quot;[]&quot;)∨»⊸&lt;a∊d)⊔a\n⟨ &quot;[&quot; &quot;999&quot; &quot;2&quot; &quot;[&quot; &quot;]&quot; &quot;[&quot; &quot;31&quot; &quot;4167&quot; &quot;]&quot; &quot;]&quot; ⟩</code></pre>\n<p>We subtract 1 to drop the commas when we group and give the first group index 0.\nFinally, we group and voila!</p>\n<p>Getting from here to my definition of <code>T</code> is just standard tacit refactoring stuff.\nAnd to be honest <code>T</code> is hard for me to read, so I probably wouldn&#39;t write it that way.\nBut we already have it, so let&#39;s continue to parsing.</p>\n<h3 id=\"parsing\">Parsing</h3>\n<p>Now it&#39;s just standard recursive descent stuff.\nHere&#39;s a sketch of the grammar.</p>\n<pre><code>Value → List | Number\nList  → &quot;[&quot; Value* &quot;]&quot;</code></pre>\n<p>We write one function each for parsing values, lists, and numbers.</p>\n<pre><code>   ParseVal ← {&quot;[&quot;≡⊑𝕩 ? ParseLst 𝕩; ParseNum 𝕩}\n   ParseNum ← {⟨10⊸×⊸+˜´⌽&#39;0&#39;-˜⊑𝕩, 1↓𝕩⟩}\n   ParseLst ← {\n    rslt←⟨⟩\n    val‿rest ← ⟨@,1↓𝕩⟩\n    {𝕤⋄val‿rest↩ParseVal rest ⋄ rslt∾↩&lt;val}•_while_{𝕤⋄&quot;]&quot;≢⊑rest}@\n    ⟨rslt, 1↓rest⟩\n   }</code></pre>\n<p>The basic idea is that a value is a list if it starts with &quot;[&quot;, otherwise it&#39;s a number.\nTo parse a number, we just do a standard string-to-number-left-fold thing on the first element,\nand we return that number along with the rest of the tokens.\nTo parse a list, we build up a list <code>rslt</code> by repeatedly parsing a value off the front of the list\nuntil we hit a &quot;]&quot;.\nThen we return <code>rslt</code> and the rest of the tokens.\nGotta be careful to drop the brackets in the right spots and to enclose the value before appending to <code>rslt</code>!</p>\n<p>To parse a list, we tokenize, parse the list, and then take the value from the <code>⟨value, tokens⟩</code> pair the parser returns.</p>\n<pre><code>   Parser2 ← ⊑∘ParseLst∘T\n   Parser2 &quot;[999,2,[],[31,4167]]&quot;\n⟨ 999 2 ⟨⟩ ⟨ 31 4167 ⟩ ⟩</code></pre>\n<p>It works!</p>\n<pre><code>   bqn ≡ Parser2¨¨ data2\n1</code></pre>\n<p>It agrees with the parsing we did earlier using <code>•BQN</code>,</p>\n<pre><code>   bqn ≡ Parser2 data\n1</code></pre>\n<p>and works on the &quot;one giant string&quot; approach.</p>\n<pre><code>   100 Parser2•_timed data\n0.007146561\n   100 Parser2¨¨•_timed data2\n0.006849455</code></pre>\n<p>Not to mention it&#39;s around 10x as fast as using <code>•BQN</code>.</p>\n<h2 id=\"array-style-parsing\">Array-style parsing</h2>\n<p>Using array techniques, we can achieve even faster parsing.\nBoth the <a href=\"https://github.com/mlochbaum/BQN/blob/master/src/c.bqn\" rel=\"nofollow ugc noopener\">self-hosted compiler</a> and the <a href=\"https://github.com/mlochbaum/bqn-libs/blob/master/json.bqn\" rel=\"nofollow ugc noopener\">bqn-libs json parser</a> use an array style.\nThe following ideas come from studying the json parser.\n(I haven&#39;t looked at the compiler in any depth.)</p>\n<p>The fundamental idea for handling nesting is to reorder the tokens by depth.\nOnce we&#39;ve done that, there&#39;s a sense in which we&#39;ve already mostly parsed the tokens!\n(At least for a simple case like these nested lists.)</p>\n<p>Here&#39;s our running example:</p>\n<pre><code>   tok ← T &quot;[1,2,[3,4,[5,6]],7,8,[9,10]]&quot;\n⟨ &quot;[&quot; &quot;1&quot; &quot;2&quot; &quot;[&quot; &quot;3&quot; &quot;4&quot; &quot;[&quot; &quot;5&quot; &quot;6&quot; &quot;]&quot; &quot;]&quot; &quot;7&quot; &quot;8&quot; &quot;[&quot; &quot;9&quot; &quot;10&quot; &quot;]&quot; &quot;]&quot; ⟩</code></pre>\n<p>Let&#39;s find the depth.</p>\n<pre><code>   o ← &quot;[&quot;⊸≡¨tok\n   c ← &quot;]&quot;⊸≡¨tok\n   tok≍+`o-c\n┌─\n╵ &quot;[&quot; &quot;1&quot; &quot;2&quot; &quot;[&quot; &quot;3&quot; &quot;4&quot; &quot;[&quot; &quot;5&quot; &quot;6&quot; &quot;]&quot; &quot;]&quot; &quot;7&quot; &quot;8&quot; &quot;[&quot; &quot;9&quot; &quot;10&quot; &quot;]&quot; &quot;]&quot;\n  1   1   1   2   2   2   3   3   3   2   1   1   1   2   2   2    1   0\n                                                                           ┘</code></pre>\n<p>Opening brackets increase depth by 1 at the bracket, and closing brackets decrease depth by 1 at the bracket.</p>\n<p>We can use <code>⍋</code> to reorder the tokens according to their depths.</p>\n<pre><code>   (⍋+`o-c)⊏tok\n⟨ &quot;]&quot; &quot;[&quot; &quot;1&quot; &quot;2&quot; &quot;]&quot; &quot;7&quot; &quot;8&quot; &quot;]&quot; &quot;[&quot; &quot;3&quot; &quot;4&quot; &quot;]&quot; &quot;[&quot; &quot;9&quot; &quot;10&quot; &quot;[&quot; &quot;5&quot; &quot;6&quot; ⟩</code></pre>\n<p>This is really weird-looking at first, but once you learn how to read it, it&#39;s nicer to work with than the original order.</p>\n<p>Each closing bracket is like a nested list waiting to be filled, or an arrow pointing to a sublist.\nEach opening bracket signals the start of a new sublist.\nThe list being pointed to by a closing bracket is the next unused sublist.</p>\n<p>If we replace each closing bracket with a <code>↓</code> and each opening bracket with a <code>∘</code>, just for pictorial purposes,\nwe can arrange the list into the follow diagram.</p>\n<pre><code>0 ↓\n1 ∘  1  2  ↓  7  8  ↓\n2          ∘ 3 4 ↓  ∘ 9 10\n3                ∘ 5 6</code></pre>\n<p>The downward arrows represent sublists, and the circles represent list starting points.\nThe numbers in the first column are the depths.\nThe first closing bracket is the only token with depth zero, and it points at the whole list.\nThe element between 2 and 7 and the last element are each sublists, the first of which has its own sublist.</p>\n<p>We almost have an algorithm that goes something like this:\nfor each closing bracket, find the next unused sublist and replace the closing bracket with the sublist.</p>\n<p>For example, we might build the list this way:</p>\n<pre><code>] → 1 2 ] 7 8 ] → 1 2 ⟨3 4 ]⟩ 7 8 ⟨9 10⟩ → 1 2 ⟨3 4 ⟨5 6⟩⟩ 7 8 ⟨9 10⟩</code></pre>\n<p>How can we turn this into code?</p>\n<p>Instead of ordering by depth, we can go further and split by depth.</p>\n<pre><code>   (+`o-c)⊔tok\n⟨ ⟨ &quot;]&quot; ⟩ ⟨ &quot;[&quot; &quot;1&quot; &quot;2&quot; &quot;]&quot; &quot;7&quot; &quot;8&quot; &quot;]&quot; ⟩ ⟨ &quot;[&quot; &quot;3&quot; &quot;4&quot; &quot;]&quot; &quot;[&quot; &quot;9&quot; &quot;10&quot; ⟩ ⟨ &quot;[&quot; &quot;5&quot; &quot;6&quot; ⟩ ⟩</code></pre>\n<p>And then perhaps we can use some kind of fold to fill in the &quot;gaps&quot; in each list with the lists from the next element.\nGoing left to right would build the list &quot;top down&quot; like the example above.\nOne snag with this approach is that at each step we have to search at a different depth for the closing brackets.\nSure, we know exactly what depth to search at, but we can eliminate this complication entirely by going right to left.\nThis builds the list bottom up, so at every step we are plugging sublists into a list at the outermost depth.</p>\n<p>This would look something like:</p>\n<pre><code>5 6 → ⟨3 4 ⟨5 6⟩⟩ ⟨9 10⟩ → 1 2 ⟨3 4 ⟨5 6⟩⟩ 7 8 ⟨9 10⟩</code></pre>\n<p>Here is the complete idea. We&#39;re going to perform a right fold.\nAt each step, the operand to the fold splits up the right argument at the opening brackets\nand then plugs the resulting lists into the closing brackets of the left argument.</p>\n<p>Thus we need two functions: one to split up the right argument on opening brackets and one to plug the lists into the closing brackets.</p>\n<p>Now we can write some code.</p>\n<pre><code>   # split up based on [\n   Split ← {m←&quot;[&quot;⊸≡¨𝕩 ⋄ 1⊸↓¨(1-˜+`m)⊔𝕩}\n   Split &quot;[&quot;‿&quot;3&quot;‿&quot;4&quot;‿&quot;]&quot;‿&quot;[&quot;‿&quot;9&quot;‿&quot;10&quot;\n⟨ ⟨ &quot;3&quot; &quot;4&quot; &quot;]&quot; ⟩ ⟨ &quot;9&quot; &quot;10&quot; ⟩ ⟩\n\n   # replace &quot;]&quot; in 𝕩 with 𝕨\n   Replace ← {m←&quot;]&quot;⊸≡¨𝕩 ⋄ 𝕨⌾(m⊸/)𝕩}\n   ⟨&quot;3&quot;‿&quot;4&quot;‿&quot;]&quot;, &quot;9&quot;‿&quot;10&quot;⟩ Replace &quot;[&quot;‿&quot;1&quot;‿&quot;2&quot;‿&quot;]&quot;‿&quot;7&quot;‿&quot;8&quot;‿&quot;]&quot;\n⟨ &quot;[&quot; &quot;1&quot; &quot;2&quot; ⟨ &quot;3&quot; &quot;4&quot; &quot;]&quot; ⟩ &quot;7&quot; &quot;8&quot; ⟨ &quot;9&quot; &quot;10&quot; ⟩ ⟩\n\n   {(Split 𝕩) Replace 𝕨}´ (+`o-c)⊔tok\n┌─\n· ┌─\n  · &quot;1&quot; &quot;2&quot; ⟨ &quot;3&quot; &quot;4&quot; ⟨ &quot;5&quot; &quot;6&quot; ⟩ ⟩ &quot;7&quot; &quot;8&quot; ⟨ &quot;9&quot; &quot;10&quot; ⟩\n                                                         ┘\n                                                           ┘\n   \n\n   Replace˜⟜Split´(+`o-c)⊔tok\n┌─\n· ┌─\n  · &quot;1&quot; &quot;2&quot; ⟨ &quot;3&quot; &quot;4&quot; ⟨ &quot;5&quot; &quot;6&quot; ⟩ ⟩ &quot;7&quot; &quot;8&quot; ⟨ &quot;9&quot; &quot;10&quot; ⟩\n                                                         ┘\n                                                           ┘</code></pre>\n<p>It works!\nThe whole thing is inside a singleton list because of that left-most closing bracket,\nso we&#39;ll need to apply <code>⊑</code> at the end.\nAlso, we&#39;ve still got to turn strings into numbers at the end.\nWe can write a string to number function and apply it at depth 1,\nbut there&#39;s one small catch that&#39;s not apparent from our example so far:\nif we parse an empty list, then applying our string to number function at depth 1 will apply it to that empty list.\nSo we need to check for empty input to the string to number function.</p>\n<p>Other than that, we just need to package this together into a parser.</p>\n<pre><code>   ToNum ← {⟨⟩≡𝕩 ? ⟨⟩ ; 10⊸×⊸+˜´⌽𝕩-&#39;0&#39;}\n   Parser3 ← {ToNum⚇1 ⊑ Replace˜⟜Split´ (+`(&quot;[&quot;⊸≡¨𝕩)-&quot;]&quot;⊸≡¨𝕩)⊔𝕩}∘T\n   Parser3 &quot;[1,2,[3,4,[5,6]],7,8,[9,10]]&quot;\n┌─\n· 1 2 ⟨ 3 4 ⟨ 5 6 ⟩ ⟩ 7 8 ⟨ 9 10 ⟩\n                                   ┘\n   bqn ≡ Parser3 data\n1\n   bqn ≡ Parser3¨¨ data2\n1</code></pre>\n<p>Looking good.\nLet&#39;s see how fast it is.</p>\n<pre><code>   •Show 100 Parser3•_timed data\n0.015287862\n   •Show 100 Parser3¨¨•_timed data2\n0.014943577</code></pre>\n<p>Oof! It&#39;s twice as slow as the conventional parser!</p>\n<p>That&#39;s okay because this was really just a warm-up to get us in the array mood.\nEven though what we have now is slow, the concepts we used will help us write a fast parser.\nAnd isn&#39;t it kind of amazing how we parsed a recursive data structure with just some arithmetic and primitives like <code>⊔</code> and folding?\nI think it&#39;s cool.</p>\n<p>Anyway, we can make significant improvements.\nFirst of all, have you been feeling the nagging pain of using lists of strings instead of just a string?\nIt&#39;s so annoying writing <code>&quot;[&quot;⊸≡¨tok</code> instead of just <code>&#39;[&#39;=tok</code>, and it&#39;s probably slower too.\nLet&#39;s try to keep our representations &quot;flatter&quot;.</p>\n<p>So the new idea is that the tokenizer will just output a string, meaning that each token is now a single character.\nThis leaves no room for the values of the tokens (the numbers themselves), just the token types,\nso actually the tokenizer will output a string and a list of numbers.</p>\n<pre><code>   a ← &quot;[1,2,[3,4,[5,6]],7,8,[9,10]]&quot; # example string\n   a≍n ← a∊&#39;0&#39;+↕10 # numbers\n┌─\n╵ &#39;[&#39; &#39;1&#39; &#39;,&#39; &#39;2&#39; &#39;,&#39; &#39;[&#39; &#39;3&#39; &#39;,&#39; &#39;4&#39; &#39;,&#39; &#39;[&#39; &#39;5&#39; &#39;,&#39; &#39;6&#39; &#39;]&#39; &#39;]&#39; &#39;,&#39; &#39;7&#39; &#39;,&#39; &#39;8&#39; &#39;,&#39; &#39;[&#39; &#39;9&#39; &#39;,&#39; &#39;1&#39; &#39;0&#39; &#39;]&#39; &#39;]&#39;\n  0   1   0   1   0   0   1   0   1   0   0   1   0   1   0   0   0   1   0   1   0   0   1   0   1   1   0   0\n                                                                                                                  ┘\n   a≍ns ← »⊸&lt;n # number starts\n┌─\n╵ &#39;[&#39; &#39;1&#39; &#39;,&#39; &#39;2&#39; &#39;,&#39; &#39;[&#39; &#39;3&#39; &#39;,&#39; &#39;4&#39; &#39;,&#39; &#39;[&#39; &#39;5&#39; &#39;,&#39; &#39;6&#39; &#39;]&#39; &#39;]&#39; &#39;,&#39; &#39;7&#39; &#39;,&#39; &#39;8&#39; &#39;,&#39; &#39;[&#39; &#39;9&#39; &#39;,&#39; &#39;1&#39; &#39;0&#39; &#39;]&#39; &#39;]&#39;\n  0   1   0   1   0   0   1   0   1   0   0   1   0   1   0   0   0   1   0   1   0   0   1   0   1   0   0   0\n                                                                                                                  ┘\n   (1-˜n×+`ns)⊔a # numbers as strings\n⟨ &quot;1&quot; &quot;2&quot; &quot;3&quot; &quot;4&quot; &quot;5&quot; &quot;6&quot; &quot;7&quot; &quot;8&quot; &quot;9&quot; &quot;10&quot; ⟩\n   num ← 10⊸×⊸+˜´∘⌽¨ &#39;0&#39;-˜(1-˜n×+`ns)⊔a # numbers\n⟨ 1 2 3 4 5 6 7 8 9 10 ⟩</code></pre>\n<p>This is the idea behind the part of the tokenizer that extracts the numbers into one flat list.</p>\n<pre><code>   a≍f ← ns∨a∊&quot;[]&quot; # first characters of tokens as mask\n┌─\n╵ &#39;[&#39; &#39;1&#39; &#39;,&#39; &#39;2&#39; &#39;,&#39; &#39;[&#39; &#39;3&#39; &#39;,&#39; &#39;4&#39; &#39;,&#39; &#39;[&#39; &#39;5&#39; &#39;,&#39; &#39;6&#39; &#39;]&#39; &#39;]&#39; &#39;,&#39; &#39;7&#39; &#39;,&#39; &#39;8&#39; &#39;,&#39; &#39;[&#39; &#39;9&#39; &#39;,&#39; &#39;1&#39; &#39;0&#39; &#39;]&#39; &#39;]&#39;\n  1   1   0   1   0   1   1   0   1   0   1   1   0   1   1   1   0   1   0   1   0   1   1   0   1   0   1   1\n                                                                                                                  ┘\n   f/a # first character of each token as string\n&quot;[12[34[56]]78[91]]&quot;\n   tok ← &#39;0&#39;¨⌾((f/n)⊸/)f/a # replace numbers with 0\n&quot;[00[00[00]]00[00]]&quot;</code></pre>\n<p>Here is the second part of the tokenizer.\nWe get the first characters of each token by adding in the brackets to the number starts.\nThen we replace all the numbers with 0.\nThe idea is that this string now represents the token types with the brackets standing for themselves\nand the 0s standing for a number type token.\nThe numbers themselves are separated out as we showed previously.\nAny character would do to represent the numbers,\nbut I chose 0 because it&#39;s what the json parser does and it reminds me of a number.</p>\n<p>Putting it all together:</p>\n<pre><code>   Tokenize ← {\n     n ← 𝕩∊&#39;0&#39;+↕10\n     ns ← »⊸&lt;n\n     num ← 10⊸×⊸+˜´∘⌽¨ &#39;0&#39;-˜(1-˜n×+`ns)⊔𝕩\n     f ← ns∨𝕩∊&quot;[]&quot;\n     tok ← &#39;0&#39;¨⌾((f/n)⊸/)f/𝕩\n     tok‿num\n   }\n   Tokenize &quot;[1,2,[3,4,[5,6]],7,8,[9,10]]&quot;\n⟨ &quot;[00[00[00]]00[00]]&quot; ⟨ 1 2 3 4 5 6 7 8 9 10 ⟩ ⟩</code></pre>\n<p>Now for parsing we&#39;re going to build the list from the bottom up again, using the same depth ordering ideas.\nWe obviously can&#39;t operate only on the token types (the string the tokenizer produces);\nwe need to incorporate the token values (the numbers) at some point.\nThe way we&#39;ll do that is operating on the token types to produce indices that we use to select from a list of values.</p>\n<p>So if we were trying to produce the final result list, which in a depth-based token-types-only representation would look like <code>00]00]</code>,\nwe need to somehow say that the first 0 stands for 1, the second 0 for 2, the first closed bracket for the whole list <code>⟨3,4,⟨5,6⟩⟩</code>,\nthe third 0 for 7, the fourth 0 for 8, and the final closed bracket for the whole list <code>⟨9,10⟩</code>.\nThen we could just grab all the values we mentioned and put them together as <code>⟨1,2,⟨3,4,⟨5,6⟩⟩,7,8,⟨9,10⟩⟩</code>.</p>\n<p>The way we&#39;ll be able to reference a whole sublist like <code>⟨3,4,⟨5,6⟩⟩</code> is by building from the bottom up, as previously mentioned,\nso that by the time we need to use a value, we&#39;ve already built it.\nAt the beginning, the values we have are just the numbers themselves.\nWe start with the deepest list <code>⟨5,6⟩</code>, which we can build by indexing into the list of values (which again at this point is just numbers).\nThen we append this to the list of values.\nNow in a future step where we need to build <code>⟨3,4,⟨5,6⟩⟩</code>, all three elements of this list already reside in our list of values,\nand all we need to do is index into the list of values to assemble them into a new value that gets appended to the end.</p>\n<p>So let&#39;s start by trying to organize the tokens so we can build the values in the correct order.</p>\n<pre><code>   o ← &#39;[&#39;=tok\n   c ← &#39;]&#39;=tok\n   tok≍+`o-c # depth\n┌─\n╵ &#39;[&#39; &#39;0&#39; &#39;0&#39; &#39;[&#39; &#39;0&#39; &#39;0&#39; &#39;[&#39; &#39;0&#39; &#39;0&#39; &#39;]&#39; &#39;]&#39; &#39;0&#39; &#39;0&#39; &#39;[&#39; &#39;0&#39; &#39;0&#39; &#39;]&#39; &#39;]&#39;\n  1   1   1   2   2   2   3   3   3   2   1   1   1   2   2   2   1   0\n                                                                          ┘\n   g ← ⍋+`(&#39;[&#39;=tok)-&#39;]&#39;=tok # depth ordering indices\n⟨ 17 0 1 2 10 11 12 16 3 4 5 9 13 14 15 6 7 8 ⟩\n   u ← g⊏tok # tokens reordered by depth\n&quot;][00]00][00][00[00&quot;</code></pre>\n<p>Here&#39;s that same reorder by depth trick we&#39;ve already discussed,\nbut this time it&#39;s a little less painful to write since we just have a string instead of a list of strings.</p>\n<p>Here&#39;s the next big idea.</p>\n<pre><code>   u≍r ← +`&#39;[&#39;=u # sublists in depth ordering\n┌─\n╵ &#39;]&#39; &#39;[&#39; &#39;0&#39; &#39;0&#39; &#39;]&#39; &#39;0&#39; &#39;0&#39; &#39;]&#39; &#39;[&#39; &#39;0&#39; &#39;0&#39; &#39;]&#39; &#39;[&#39; &#39;0&#39; &#39;0&#39; &#39;[&#39; &#39;0&#39; &#39;0&#39;\n  0   1   1   1   1   1   1   1   2   2   2   2   3   3   3   4   4   4\n                                                                          ┘</code></pre>\n<p>By taking a sum scan of a mask of opening bracket locations in the depth ordering we can give a number to each sublist of the list.\nThis is the order we have to construct values in, with higher numbers going first.\nIt&#39;s reminiscent of how we split the on opening brackets in our earlier approach.</p>\n<p>Now what we need are indices that tell us where to pull the values from.\nFor example, we start with list 4 (the <code>[00</code> at the end), so we need to know that those 0s are associated with indices 4 and 5,\nsince <code>4‿5 ⊏ num</code> is the <code>5‿6</code> we want.\nThen later when constructing list 2, which looks like <code>[00]</code>, we need to know that the 0s are associated with indices 2 and 3,\nand the closing bracket is associated with index 10, since (after appending <code>5‿6</code> to a list of values <code>vals</code> at index 10) we have <code>2‿3‿10 ⊏ vals</code> giving <code>⟨3,4,⟨5,6⟩⟩</code>.</p>\n<p>Here we go.</p>\n<pre><code>   tok≍f ← tok∊&quot;0]&quot; # mask of &quot;values&quot;: numbers and sublists\n┌─\n╵ &#39;[&#39; &#39;0&#39; &#39;0&#39; &#39;[&#39; &#39;0&#39; &#39;0&#39; &#39;[&#39; &#39;0&#39; &#39;0&#39; &#39;]&#39; &#39;]&#39; &#39;0&#39; &#39;0&#39; &#39;[&#39; &#39;0&#39; &#39;0&#39; &#39;]&#39; &#39;]&#39;\n  0   1   1   0   1   1   0   1   1   1   1   1   1   0   1   1   1   1\n                                                                          ┘\n   (f/tok)≍(f/&#39;0&#39;=tok)+2×f/&#39;]&#39;=tok # gives numbers 1 and sublists 2\n┌─\n╵ &#39;0&#39; &#39;0&#39; &#39;0&#39; &#39;0&#39; &#39;0&#39; &#39;0&#39; &#39;]&#39; &#39;]&#39; &#39;0&#39; &#39;0&#39; &#39;0&#39; &#39;0&#39; &#39;]&#39; &#39;]&#39;\n  1   1   1   1   1   1   2   2   1   1   1   1   2   2\n                                                          ┘\n   vi ← ⍋⍋(f/&#39;0&#39;=tok)+2×f/&#39;]&#39;=tok # value indices\n⟨ 0 1 2 3 4 5 10 11 6 7 8 9 12 13 ⟩\n   (f/tok)≍vi\n┌─\n╵ &#39;0&#39; &#39;0&#39; &#39;0&#39; &#39;0&#39; &#39;0&#39; &#39;0&#39; &#39;]&#39; &#39;]&#39; &#39;0&#39; &#39;0&#39; &#39;0&#39; &#39;0&#39; &#39;]&#39; &#39;]&#39;\n  0   1   2   3   4   5   10  11  6   7   8   9   12  13\n                                                          ┘</code></pre>\n<p>Here we filter away the opening brackets, keeping only those tokens that represent values: 0 for numbers and ] for sublists.\nThen we assign each value a number working left to right, but with numbers always coming before sublists.\nThat <code>⍋⍋</code> is the ordinals pattern, which shows which index the element would end up at if sorted.\n(You can read about that <a href=\"https://mlochbaum.github.io/BQN/doc/order.html#ordinals\" rel=\"nofollow ugc noopener\">here</a>.)</p>\n<p>This is close to what we want.\nThe 0s each have been associated with the proper index.\nHowever, the closing brackets (representing sublists) have not.</p>\n<p>We need to bring in our previous work <code>r</code> where we numbered the lists.\nBut <code>r</code> is in depth ordering and <code>vi</code> is in the original ordering, so we put <code>r</code> back into original ordering and call it <code>l</code>.</p>\n<pre><code>   tok≍l ← (⍋g)⊏r # sublist index\n┌─\n╵ &#39;[&#39; &#39;0&#39; &#39;0&#39; &#39;[&#39; &#39;0&#39; &#39;0&#39; &#39;[&#39; &#39;0&#39; &#39;0&#39; &#39;]&#39; &#39;]&#39; &#39;0&#39; &#39;0&#39; &#39;[&#39; &#39;0&#39; &#39;0&#39; &#39;]&#39; &#39;]&#39;\n  1   1   1   2   2   2   4   4   4   2   1   1   1   3   3   3   1   0\n                                                                          ┘</code></pre>\n<p>We invert the permutation <code>g</code> with <code>⍋</code> to translate from the depth ordering back to the original ordering.\nWe call the resulting numbers the &quot;sublist index&quot; here.\n(It&#39;s really a pain to name a new idea. I don&#39;t wanna name things! That&#39;s why I&#39;m a BQN programmer.)</p>\n<p>We can use <code>l</code> to fix <code>vi</code> by finding the sublist index associated with each closing bracket.\nIf we just take the sublist index at a closing bracket, we get the sublist index associated with the list containing it.\nSo we need the sublist index at the token before the closing bracket to get the index of the sublist itself.</p>\n<pre><code>   c/l\n⟨ 2 1 1 0 ⟩\n   c/»l\n⟨ 4 2 3 1 ⟩</code></pre>\n<p>Here we show <code>c/l</code> and <code>c/»l</code>. The first element of <code>c/l</code> is 2, indicating that the first closing bracket (which closes <code>⟨5,6⟩</code>) represents a sublist contained in the sublist with index 2 (i.e. <code>⟨3,4,⟨5,6⟩⟩</code>).\nThe first element of <code>c/»l</code>, however, is 4, indicating that the sublist <code>⟨5,6⟩</code> is itself sublist number 4.\nThat&#39;s the number we want.</p>\n<pre><code>   (≠num)+≠⊸-c/»l\n⟨ 10 12 11 13 ⟩</code></pre>\n<p>Sublist number 4 is the first sublist to be constructed, and after being constructed and appended to the value list it has index 10.\nThe arithmetic above adjusts the sublist indices to become indices into the value list.\nWe subtract each sublist index from the number of sublists to invert the order, and then add the result to the number of numbers,\nto offset the indices correctly.</p>\n<pre><code>   nv ← ≠num\n   i ← vi ⊏ (↕nv) ∾ nv+≠⊸-c/»l # Adjust for sublist ordering\n⟨ 0 1 2 3 4 5 10 12 6 7 8 9 11 13 ⟩\n   (f/tok)≍i\n┌─\n╵ &#39;0&#39; &#39;0&#39; &#39;0&#39; &#39;0&#39; &#39;0&#39; &#39;0&#39; &#39;]&#39; &#39;]&#39; &#39;0&#39; &#39;0&#39; &#39;0&#39; &#39;0&#39; &#39;]&#39; &#39;]&#39;\n  0   1   2   3   4   5   10  12  6   7   8   9   11  13\n                                                          ┘</code></pre>\n<p>From here, it&#39;s not hard to complete the value indices list.\nWe append the value indices just calculated for the sublists to the list <code>↕≠num</code>, which are the value indices for the numbers.\nSince both <code>vi</code> and <code>c»l</code> reference the closing brackets in the original left to right order, indexing into this list with <code>vi</code> pulls everything out in the correct order.</p>\n<pre><code>   ⌽(1-˜f/l)⊔i\n⟨ ⟨ 4 5 ⟩ ⟨ 8 9 ⟩ ⟨ 2 3 10 ⟩ ⟨ 0 1 12 6 7 11 ⟩ ⟩</code></pre>\n<p>We group these value indices <code>i</code> using the sublist indices from <code>l</code> and reverse the result to finally complete the task of arranging the value indices.\nWe use <code>1-˜f/l</code> instead of just <code>l</code> because we need to remove the opening brackets and drop the final closing bracket.\nNow we can see the first element contains indices 4 and 5, which correspond to the values 5 and 6.\nThe third element contains the indices 2, 3, and 10, which correspond to values 3, 4, and <code>⟨5,6⟩</code>.\nEtc.</p>\n<p>All that&#39;s left to do is the indexing and appending described earlier.</p>\n<pre><code>   vals ← num\n   {vals∾↩&lt;𝕩⊏vals⋄@}¨ ⌽(1-˜f/l)⊔i\n   ¯1⊑vals\n┌─\n· 1 2 ⟨ 3 4 ⟨ 5 6 ⟩ ⟩ 7 8 ⟨ 9 10 ⟩\n                                   ┘</code></pre>\n<p>It works!\nThe list of values <code>vals</code> starts off as just the numbers <code>num</code>.\nWith each application of the block function we index into <code>vals</code> and append the result to <code>vals</code>.\nThe <code>⋄@</code> is at the end of the block both to signal that we are using the block for side-effects only\nand to not waste time and space building a list of results.</p>\n<p>We&#39;re not quite done yet!\nThere is one final wrinkle that our example so far hasn&#39;t made clear.\nWe need to ensure that the result of <code>(1-˜f/l)⊔i</code> always has as many elements as there are closing brackets\n(even if some or all of them are empty) in order to accomodate empty lists.\nThis is roughly because each closing bracket represents a sublist value,\nso we always need to build at least that many values.</p>\n<p>Thus we change <code>1-˜f/l</code> to <code>(+´c)∾˜1-˜f/l</code> to append the number of closing brackets to the end.\nGroup has the option of using a left argument with an extra last element relative to right argument,\nand this last element sets the minimum number of elements of the result.</p>\n<p>Let&#39;s put it all together.</p>\n<pre><code>   Parser4 ← {\n     tok‿num ← Tokenize 𝕩\n     g ← ⍋+`(&#39;[&#39;=tok)-(c←&#39;]&#39;=tok) # depth ordering indices\n     r ← +`&#39;[&#39;=g⊏tok # sublists in depth ordering\n     l ← (⍋g)⊏r # sublist index\n     f ← tok∊&quot;0]&quot; # mask of &quot;values&quot;: numbers and sublists\n     vi ← ⍋⍋(f/&#39;0&#39;=tok)+2×f/c # value indices\n     nv ← ≠num\n     i ← vi ⊏ (↕nv) ∾ nv+≠⊸-c/»l # Adjust for sublist ordering\n     vals ← num\n     {vals∾↩&lt;𝕩⊏vals⋄@}¨ ⌽((+´c)∾˜1-˜f/l)⊔i\n     ¯1⊑vals\n   }\n   •Show Parser4 &quot;[1,2,[3,4,[5,6]],7,8,[9,10]]&quot;\n┌─\n· 1 2 ⟨ 3 4 ⟨ 5 6 ⟩ ⟩ 7 8 ⟨ 9 10 ⟩\n                                   ┘\n\n   •Show bqn ≡ Parser4 data\n1\n   •Show bqn ≡ Parser4¨¨ data2\n1\n\n   •Show 100 Parser4•_timed data\n0.004316795\n   •Show 100 Parser4¨¨•_timed data2\n0.005003989</code></pre>\n<p>It works, and it&#39;s really fast! It&#39;s also the only parser that&#39;s faster on the one big string approach.</p>\n<h2 id=\"final-comparison\">Final Comparison</h2>\n<p>Using <code>•BQN</code> is definitely the easiest, but it is slow and has problems parsing large lists, at least on my machine.</p>\n<p>For a little more effort (at least if you&#39;re already familiar with recursive descent) we can get a much more performant parser.\nProbably should be your method of choice if <code>•BQN</code> is too slow.</p>\n<p>A well-written array style parser is the fastest (and coolest obviously), but wow is it confusing to implement!\nFor this Advent of Code problem it&#39;s certainly not worth the trouble.\nI mean, even just using <code>•BQN</code> works fine honestly.\nIf we had to parse way more data, or reuse this parser many times, the array method would start to make sense.\nAlso if the lists had very very deep nesting, the recursive parser would hit the maximum recursion limit and fail.</p>\n<p>Here&#39;s a little table recapping the time in seconds it took each method to parse my input file.\nEach time is the average of 100 runs.</p>\n<pre><code>          |   data         data2\n------------------------------------\n•BQN      | N/A          0.074279465\nRecursive | 0.007146561  0.006849455\nArray v1  | 0.015287862  0.014943577\nArray v2  | 0.004316795  0.005003989</code></pre>\n<p>Happy parsing! &lt;3</p>","headings":[{"level":1,"text":"Parsing nested lists in BQN","id":"parsing-nested-lists-in-bqn"},{"level":2,"text":"The Data","id":"the-data"},{"level":2,"text":"Using •BQN","id":"using-bqn"},{"level":2,"text":"Recursive descent","id":"recursive-descent"},{"level":3,"text":"Tokenizing","id":"tokenizing"},{"level":3,"text":"Parsing","id":"parsing"},{"level":2,"text":"Array-style parsing","id":"array-style-parsing"},{"level":2,"text":"Final Comparison","id":"final-comparison"}]}}