能否用Bird-Meertens形式化方法在Haskell中实现最长有效括号线性时间解法？

问题描述 #

给定仅由(和)组成的字符串，计算其中最长匹配/有效括号子串的长度。

朴素解法 #

isValid :: String -> Bool
isValid = go' (0 :: Int)
  where
    go' = memo2 go
    go 0 [] = True
    go 0 (')' : _ ) = False
    go n (')' : cs) = go' (n-1) cs
    go n ('(' : cs) = go' (n+1) cs
    go _ _ = False

solution :: String -> Int
solution = longest . valid . substrings
  where
    substrings = tails >>= inits
    valid      = filter isValid
    longest    = maximum . map length

我总能轻松写出这类低效的简单解法，但高效版本却很难构思。Bird-Meertens形式化方法的核心理念是：如果能写出慢版本，就能通过该演算推导出高效版本，所以我希望它能在这里发挥作用。

另外，这个问题和维基百科上Bird-Meertens形式化方法的示例表面相似——我们都需要遍历所有可能的子数组、执行映射操作，最终取最大值。

Bird-Meertens形式化方法能否在此处帮到我？

我尝试内联定义后得到了下面的代码：

solution = maximum . map length . concat . map (filter isValid . tails) . inits

但目前还没找到这里能适用的相关规则。

内容的提问来源于stack exchange，提问作者Brendan Langfield