4

再帰関数が F# の強力な手法であることは知っています。私の質問は次のとおりです。命令型言語と同じように、再帰関数を飛び出すことができる exit ステートメントはありますか。たとえば、二分木にノードを挿入します。

type Tree<'a> when 'a :> IComparable<'a> =
           | Nil
           | Leaf of 'a
           | Node of Tree<'a> * 'a * Tree<'a>

let tt2 = Node(
              Node(Leaf "D", "B",Node(Leaf "G", "E", Leaf "H" )),
              "A",
              Node(Nil, "C", Node(Nil, "F", Leaf "I")))

let rec contains (x : #IComparable<'a>) = function
    | Nil -> false
    | Leaf y -> if x.CompareTo(y) = 0 then true else false
    | Node(l, y, r) -> 
         match l, y, r with
             | l, y, Nil -> if x.CompareTo(y) = 0 then true else contains x  l
             | Nil,y, r -> if x.CompareTo(y) = 0 then true else contains x r 
             | _ -> if x.CompareTo(y) = 0 then true
                    else contains x r |>ignore
                         contains x l

let xx = contains "C"  tt2  //It is wrong answer.
4

1 に答える 1

10

命令型言語と同じように、再帰関数を飛び出すことができる exit ステートメントはありますか。

いいえ。まさにその理由は、再帰関数とパターン マッチングによって命令型のブレーク/リターンをエンコードできるからです。中断したい場合は、値を返すだけです。それ以外の場合は、別の再帰呼び出しを呼び出します。

この質問は、高次関数を求めるのに適しています。高階関数で早期終了が必要な場合は、カスタム再帰関数を作成する方法があります。F# の命令型構造に興味がある場合は、 @Tomas による優れたシリーズをご覧ください。

条件が決定されると、関数はいくつかの分岐で終了します。contain x r唯一の問題は、最後から 2 番目の行で破棄しないことです。

if/else明確にするために余分なものを削除できます

let rec contains (x : #IComparable<'a>) = function
    | Nil -> false
    | Leaf y -> x.CompareTo(y) = 0
    | Node(l, y, r) -> 
         match l, y, r with
         | l, y, Nil -> x.CompareTo(y) = 0 || contains x l
         | Nil,y, r -> x.CompareTo(y) = 0 || contains x r 
         | _ -> x.CompareTo(y) = 0 || contains x l || contains x r
于 2013-04-16T13:56:04.490 に答える