-5

私は助けが必要です。私はその形の機能を持っています

myFunction = case myFunction of
    (Nothing) -> (Just)
    (Just) -> (Just)

末尾再帰にしたい。どうやってそれをしますか？再帰呼び出しの戻りに応じて別のステートメントを使用しているという事実が難しいことを理解しています (助けが必要な理由 ^^)。元の機能を与えることはできますが、より一般的な解決策を探しています。前もって感謝します

編集:実際のコード:

myFunction :: MyTree x -> (x, Maybe(MyTree x))
myFunction = (x, Nothing)
myFunction (MyNode left right) = case myFunction left of
                                      (x, Nothing)    -> (x, Just right)
                                      (x, Just left2) -> (x, Just (Node left2 right))
4

2 に答える 2

1

私はあなたが定義したと仮定します

data MyTree x = MyLeaf x | MyNode (MyTree x) (MyTree x)

と意味

myFunction :: MyTree x -> (x, Maybe(MyTree x))
myFunction (MyLeaf x) = (x, Nothing)
myFunction (MyNode left right) = case myFunction left of
                                      (x, Nothing)    -> (x, Just right)
                                      (x, Just left2) -> (x, Just (MyNode left2 right))

これは、一番左の葉を引き出し、対応する右の枝を元の場所に縫い付ける機能です。

この末尾を再帰的にする方法を尋ねます。何故ですか？一部の (厳密な) 言語では、末尾再帰コードの方が効率的ですが、Haskell では遅延評価が使用されます。つまり、再帰呼び出しが発生するのが遅いかどうかではなく、出力がどれだけ早く生成されるかが問題になります。この場合、head 再帰case myFunction left ofは、一番左のリーフが見つかるまでツリーを右にズームします。これ以上速く到達することはできません。ただし、戻る途中で、xすぐに戻るのではなく、少し迂回しますが、簿記を行わずに適切なすべてのブランチを適切なプレイブに縫い付けます。これは、再帰的なデータ構造で再帰を使用する喜びです。 .

Haskell の効率にとって末尾再帰が最も重要でない理由については、この質問を参照してください。

ノードにデータがあるバイナリ ツリーに対して行う 3 つの古典的なことは次のとおりです。次に現在のノード、次に右) - 先頭と末尾の再帰 3. 後順トラバーサル (現在のノードの前の左と右のサブツリーにアクセス) - 二重に先頭の再帰。

ポスト オーダーは、遅延評価に慣れていない人にとっては心配そうにヘッド再帰的に聞こえますが、たとえば、特にコンパイラがそれが厳密であることを確実に認識している場合は、ツリー内の値を合計する効率的な方法です。

いつものように、最良のアルゴリズムは最速の結果をもたらします。最適化を有効にしたい場合は、-O2 でコンパイルする必要があります。

于 2012-11-22T02:42:32.003 に答える
0

これらは一致する必要があります。

myFunction = ...
myFunction (MyNode left right) = ...

それらは一致しません。それらを一緒に使用することはできません。なんで？そのうちの 1 つは引数を取りませんが、もう 1 つは引数を 1 つ取ります。同じ数の引数を取る必要があります。引数を無視する必要がある場合は、 を使用します_。_を使用するバージョンは、使用しないバージョンより後でなければならないことに注意してください_。

myFunction :: MyTree x -> Maybe (MyTree x)
myFunction (MyNode left right) =
  case myFunction left of
    Nothing -> Just right
    Just left2 -> Just (MyNode left2 right)
myFunction _ = Nothing

x関数の本体に何があるべきかわかりません。それは何にも縛られていません。

これは末尾再帰ではありません。すべての関数を末尾再帰関数にできるわけではありません。

ヒント

関数が何をするべきかを説明していただければ、それを行うお手伝いができるかもしれません。

于 2012-11-21T23:28:28.297 に答える