翻译简单势在必行算法功能的风格

Question

我最近做了一个小的算法来从一个代码片段剔除函数参数和只保留最外层的功能。
我发现这个算法是非常容易设计的一种必要的方式。
但是，我真的对函数式编程感兴趣，我想知道如何以功能的方式完成同样的事情。

这将是对我很大的帮助，如果你能告诉我这种算法可能是如何工作的，所以我可能会如何函数式编程作品一个更好的主意。另外，我想知道您在设计算法时的思维过程。

我在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

一个窍门做这样conversin时正在收尾，我喜欢称作为一种转到+变量赋值：

sumn n = addn n 0 

addn i acc = 
    if i == 0 then 
     acc 
    else 
     addn (i-1) (acc + i) 

def sumn(n): 
    #lets pretend Python has gotos for now... 
    i, acc = n, 0 
acc: 
    if i == 0: 
    return acc 
    else: 
    i, acc = (i-1), (acc + i) 
    goto acc 

在你的情况，这将转化有点像

--Haskell pseudocode w/ string slicing 
get_rid xs = go 0 0 0 0 "" 
    where 
    -- "go" is a common name for these tail-recursive loop functions. 
    go i j start end result = 
     if j < length xs then 
     case xs !! j of 
      '(' -> 
       if i == 0 then 
       go (i+1) (j+1) j end (result ++ (text[end:start])) 
       else 
       go (i+1) (j+1) start end result 
      ')' -> 
       if i == 1 then 
       go (i-1) (j+1) start (j+1) (result ++ "()") 
       else 
       go (i-1) (j+1) start end result 
      _ -> 
       go i (j+1) start end result 
     else 
     result ++ text[end:] 

最终的结果是超级丑陋的，因为这仍然是一个基本上势在必行的算法，有很多变量赋值正在进行。此外，功能版本明确表示所有变量都处于可用的最大范围（“去”循环）：我想你应该能够通过使用内部循环找到“开始”和“结束”来找到下一个“）”，而不是在主循环中做所有事情（这对原始Python程序也是有效的）。

还有一些小样式的问题，例如仍然在链表上使用索引和切片（它在O（N）中的Haskell而不是O（1））和使用尾递归循环（gotos）而不是更多结构折叠（for循环）。也就是说，重要的一点是，如果你真的想要的话，你仍然可以编写算法的原始版本。

Answer 3

一种方式来做到这一点是从迭代转换为递归风格。换句话说，代替使用for循环多次执行某些代码，您可以通过自己调用函数来实现同样的目的。

在Haskell一个例子：

get_rid_of_arguments [] = [] 
get_rid_of_arguments ('(':xs) = "()" ++ (get_rid_of_arguments $ dropper xs) 
get_rid_of_arguments (x:xs) = x : get_rid_of_arguments xs 

dropper [] = [] 
dropper (')':xs) = xs 
dropper ('(':xs) = dropper $ dropper xs 
dropper (_:xs) = dropper xs 

main = do 
    print $ get_rid_of_arguments "foo(a.d, b.e.fi()).go(sd, ds())" == "foo().go()" 
    print $ get_rid_of_arguments "foo(a, b).bar().fuu" == "foo().bar().fuu" 
    print $ get_rid_of_arguments "foo.bar" == "foo.bar" 

P.S.您的原始python代码和这个Haskell代码都不是正确的方法，“从一段代码中去掉函数参数”，我只是回答“我该如何翻译这段代码”的问题。

Answer 4

好吧，我宁愿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) 

这使得通过我们的过滤函数运行的状态，我们只是返回当前是否价值是真实的，我们的新状态。那么你的代码只是

-- # 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 

现在，这是很好的功能，整个事情归结为折叠字符串。有一些管道跟踪状态，但一旦你开始对Haskell进行更多的研究，它会很好地消失。

Answer 5

已经有很多答案，但只是添加到列表中，这里是一个非常简单的功能风格。

它使用一个帮助函数，它需要一个嵌套计数。所以，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