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" def grade xs = zip (map u32.i32 xs) (indices xs)0) |> radix_sort (.1) |> map (.
For an array
A, the result
grade A tells us the order in which
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 let rnk = grade depth let ret = tabulate n (\i -> if i % 2 == 0 then rnk[i+1] else rnk[i-1]) in permute ret rnk
The function returns, for each parenthesis in the input string, the index of its counterpart.
> match_parens "()(()())((()))"
[1i64, 0i64, 7i64, 4i64, 3i64, 6i64, 5i64, 2i64, 13i64, 12i64, 11i64, 10i64, 9i64, 8i64]