Fork me on GitHub
Source file: parens.fut

# Matching parentheses

Consider finding pairs of balanced parentheses in a string such as `"()(()())((()))"` consisting entirely of open and closing parentheses. This problem has an elegant parallel solution. We’ll assume that the string is indeed balanced - checking whether that is the case, or also allowing non-parenthesis characters, is a fairly easy extension.

First we define a function for finding the nesting depth of each character.

``````def depths [n] (s: [n]u8) : [n]i32 =
let depth = scan (+) 0 (map (\c -> if c == '(' then 1 else -1) s)
in map2 (\c d -> d - if c == '(' then 1 else 0) s depth``````
``> depths "()(()())((()))"``
``[0i32, 0i32, 0i32, 1i32, 1i32, 1i32, 1i32, 0i32, 0i32, 1i32, 2i32, 2i32, 1i32, 0i32]``

Next, we define a function that gives the sorting order of an array of integers. Although we will use a previously defined radix sort as a building block, this is not the same as a sorted array! We use the name `grade` for this function, inspired by APL:

``````import "radix-sort-key"

zip (map u32.i32 xs) (indices xs)
|> map (.1)``````

For an array `A`, the result `grade A` tells us the order in which to index `A` to obtain the sorted array.

``> grade [5,0,1,3,2,4]``
``[1i64, 2i64, 4i64, 3i64, 5i64, 0i64]``

Finally, with the help of a small auxiliary function for permuting arrays, we can finish our implementation of parentheses matching.

``````def permute xs is = scatter (copy xs) is xs

def match_parens [n] (s: [n]u8) =
let depth = depths s
``> match_parens "()(()())((()))"``
``[1i64, 0i64, 7i64, 4i64, 3i64, 6i64, 5i64, 2i64, 13i64, 12i64, 11i64, 10i64, 9i64, 8i64]``