将一个简单的命令式算法转换为函数式

Question

最近，我提出了一个小算法，从代码片段中删除函数参数，并且只保留最外层的函数。

我发现这个算法很容易设计成命令式的方式。

但是，我对函数式编程很感兴趣，我想知道如何以功能的方式完成同样的工作。

如果您能向我展示这样的算法是如何工作的，那么我可能会对函数式编程的工作方式有一个更好的了解，这将对我很有帮助。另外，我想知道你在设计算法时的思维过程是什么。

我用Python编写了命令式版本，但您的答案不必是用python；haskell或任何其他语言也可以。

下面是它所做的事情(以字符串作为输入并返回字符串)：

"foo(a.d, b.e.fi()).go(sd, ds())"     -- returns -->  "foo().go()"
"foo(a, b).bar().fuu"                 -- returns -->  "foo().bar().fuu"
"foo.bar"                             -- returns -->  "foo.bar"

下面是我的命令代码：

def get_rid_of_arguments(text):
    i, start, end = 0, 0, 0
    result = ""
    for j, c in enumerate(text):
        if c == '(':
            if i == 0:
                start = j
                result += text[end:start]
            i += 1
        elif c == ')':
            i -= 1
            if i == 0:
                end = j + 1
                result += '()'
    return result + text[end:]

Answer 1

这是我的版本：

import Control.Monad
import Control.Monad.State

-- filter `str` with the "stateful" monadic predicate function `handleChar`, 
-- with an initial state of 0
getRidOfArguments :: String -> String
getRidOfArguments str = filterM handleChar str `evalState` 0

handleChar :: Char -> State Int Bool
handleChar '(' = modify (+1) >> gets (<= 1)
handleChar ')' = modify (max 0 . subtract 1) >> gets (== 0)
handleChar _   = gets (== 0)

我的想法是:我们正在过滤一个列表，所以想到了filter；然而，我们是保留还是删除一个字符取决于某种状态(打开/关闭父母的计数)。因此，一元过滤函数filterM是合适的，我们可以使用State monad来抽象开/闭计数的管道。

如果您想了解更多关于上述操作的细节，请告诉我。

Answer 2

好吧，我更喜欢jberryman的解决方案，但如果你想避免单曲，试试这个

stateFilter :: (s -> a -> (s, Bool)) -> [a] -> s -> [a]
stateFilter f as state = snd $ foldr stepper (state, []) as
  where stepper (state, filtered) a =
          let (state', b) = f state a in
             if b then (state', a:filtered) else (state', filtered)

这使一个状态通过我们的过滤函数运行，我们只返回当前值是否为true和我们的新状态。那么你的代码就是

-- # Converted from jberrymans lovely answer
handleChar :: Int -> Char -> (Int, Bool)
handleChar s '(' = (max 0 (s - 1), s <= 1)
handleChar s ')' = (s +1, s <= 0)
handleChar s _   = (s, s == 0)

现在的状态是明确的(也不那么漂亮)，但也许更容易理解。

clean str = stateFilter handleChar str 0

这是好的和实用的，整个事情归结为折叠在绳子上。有一些管道正在进行跟踪状态，但一旦你开始摸索哈斯克尔更多，这是很好地消失了。

Answer 3

已经有很多答案了，但只是为了添加到列表中，这里有一个非常简单的函数样式。

它使用一个获得嵌套计数的助手函数。所以，0表示不在括号内，1表示在1对内等等，如果n>0，则删除字符。如果我们碰到一个括号，相应地增加/减少n。

辅助函数基本上是该算法的逐个案例描述。如果真的使用它，你会把它挂在"where“子句上。

skipBrackets :: String -> String
skipBrackets s = skipper s 0

skipper :: String -> Int -> String

skipper [] _ = []
skipper ('(':xs) 0 = '(' : skipper xs 1
skipper (')':xs) 1 = ')' : skipper xs 0

skipper ('(':xs) n = skipper xs (n + 1)
skipper (')':xs) n = skipper xs (n - 1)

skipper (x:xs) 0 = x : skipper xs 0
skipper (x:xs) n = skipper xs n