5

関数の下で閉じられた集合、つまりフィボナッチ数列の加算を伴う整数に対して、バイナリ再帰を末尾再帰に変換する明確な方法があります。

(ハスケルを使用)

fib :: Int -> Int
fib n = fib' 0 1 n

fib' :: Int -> Int -> Int
fib' x y n
    | n < 1 = y  
    | otherwise = fib' y (x + y) (n - 1)

これが機能するのは、目的の値yと演算x + yがありx + y、整数と同じように整数を返すからyです。

しかし、関数の下で閉じられていないセットを使用したい場合はどうすればよいでしょうか? リストを 2 つのリストに分割し、その 2 つのリストに対して同じことを行う関数を使用したいと考えています (つまり、バイナリ ツリーを再帰的に作成するようなものです)。別の関数が魔法のように、結果の分割を見ていつ停止するかを指示したときに停止します。 :

[1, 2, 3, 4, 5] -> [[1, 3, 4], [2, 5]] -> [[1, 3], [4], [2], [5]]

あれは、

splitList :: [Int] -> [[Int]]
splitList intList
    | length intList < 2    = [intList]
    | magicFunction x y > 0 = splitList x ++ splitList y
    | otherwise             = [intList]
  where
    x = some sublist of intList
    y = the other sublist of intList

では、この二項再帰を末尾再帰に変換するにはどうすればよいでしょうか。Int + Int -> Int(は入力と同じ) しかし ( は入力と同じではない) であるため、前の方法は明示的に機能しSplit [Int] -/> [[Int]]ません。そのため、アキュムレータを変更する必要があります (私は推測します)。

4

2 に答える 2

2

通常、Haskell では末尾再帰は必要ありません。あなたが望むのは、 SICPで反復プロセスと呼ばれるものを説明する、生産的なコアカージョン(これも参照)です。

初期入力をリストで囲むことにより、関数の型の不一致を修正できます。あなたの例では

[1, 2, 3, 4, 5] -> [[1, 3, 4], [2, 5]] -> [[1, 3], [4], [2], [5]]

最初の矢印だけが矛盾しているので、に変更します

[[1, 2, 3, 4, 5]] -> [[1, 3, 4], [2, 5]] -> [[1, 3], [4], [2], [5]]

これは、 を繰り返し適用するプロセスを示していますconcatMap splitList1。

   splitList1 xs 
      | null $ drop 1 xs = [xs]
      | magic a b > 0    = [a,b]    -- (B)
      | otherwise        = [xs]
     where (a,b) = splitSomeHow xs

(B)特定の反復でケースが発生しなかった場合は停止したいと考えています。

（編集：中間バージョンを削除）

しかし、出力の準備ができている部分をできるだけ早く生成する方がはるかに優れています。

splitList :: [Int] -> [[Int]]
splitList xs = g [xs]   -- explicate the stack
  where
    g []                  = []
    g (xs : t)
       | null $ drop 1 xs = xs : g t
       | magic a b > 0    = g (a : b : t)
       | otherwise        = xs : g t
     where (a,b) = splitSomeHow xs 
           -- magic a b = 1
           -- splitSomeHow = splitAt 2

-O2フラグを付けてコンパイルすることを忘れないでください。

于 2013-05-12T10:48:27.550 に答える