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 "()(()())((()))"

[0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 2, 2, 1, 0]

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)
  |> radix_sort (.0)
  |> 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]

[1, 2, 4, 3, 5, 0]

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 "()(()())((()))"

[1, 0, 7, 4, 3, 6, 5, 2, 13, 12, 11, 10, 9, 8]