4

私は最近、コードのスニペットから関数の引数を取り除き、最も外側の関数のみを保持する小さなアルゴリズムを作成しました。
このアルゴリズムは、命令型の方法で設計するのが非常に簡単であることがわかりました。
しかし、私は関数型プログラミングに非常に興味があり、関数型の方法で同じことをどのように達成するのか疑問に思っていました.

そのようなアルゴリズムがどのように機能するかを教えていただければ、非常に役に立ちます。関数型プログラミングがどのように機能するかについて、より良いアイデアが得られるかもしれません。また、アルゴリズムを設計する際の思考プロセスについても知りたいです。

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:]
4

5 に答える 5

7

これが私のバージョンです：

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開閉カウントの配管を抽象化できます。

上記の仕組みについて詳しく知りたい場合はお知らせください。

于 2013-10-04T15:03:01.643 に答える
3

よし、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

これは素晴らしく機能的です。要するに、ひもを折りたたむだけです。状態を追跡するために少し配管が行われていますが、Haskell をもう少し理解し始めると、これはうまくいきます。

于 2013-10-04T16:16:48.183 に答える
2

すでに多くの回答がありますが、リストに追加するだけで、非常に単純化された機能的なスタイルの回答が 1 つあります。

ネスト数を取るヘルパー関数を使用します。したがって、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
于 2013-10-05T07:57:16.143 に答える
1

これを行う 1 つの方法は、反復スタイルから再帰スタイルに変換することです。つまり、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"

PS元のpythonコードもこのHaskellコードも、「コードのスニペットから関数の引数を取り除く」正しい方法ではありません。「このコードをどのように翻訳するのですか」という質問に答えているだけです。

于 2013-10-04T16:06:38.733 に答える
0

この種のコンバーシンを行うときに私が気に入っているトリックの 1 つは、末尾の呼び出しを一種の goto + 変数代入として調べることです。

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:]

最終結果は非常に醜いものです。なぜなら、これは依然として基本的に必須のアルゴリズムであり、多くの変数の割り当てが行われているからです。さらに、機能バージョンでは、すべての変数が利用可能な最大のスコープ (「go」ループ) にあることが明示されます。メインループですべてを実行する代わりに、次の ")" を使用します (これは元の Python プログラムでも有効です)。

また、リンクされたリスト (Haskell では O(1) ではなく O(N)) でインデックス作成とスライスを使用し続けていることや、より構造化された折り畳み (for ループ）。そうは言っても、重要な点は、本当に必要な場合は、アルゴリズムの元の命令型バージョンを引き続き作成できるということです。

于 2013-10-04T15:59:56.900 に答える