3

これは私の脳を傷つけています！

ツリー構造を再帰して、フィルターに一致するすべてのインスタンスを 1 つのリストに収集したいと考えています。

ツリー構造のサンプルを次に示します。

type Tree =
| Node of int * Tree list

テスト サンプル ツリーは次のとおりです。

let test = 
    Node((1,
            [Node(2,
                    [Node(3,[]);
                    Node(3,[])]);
            Node(3,[])]))

int 値が 3 のノードを収集してフィルタリングすると、次のような出力が得られます。

[Node(3,[]);Node(3,[]);Node(3,[])]
4

6 に答える 6

6

次の再帰関数は、そのトリックを行う必要があります。

// The 'f' parameter is a predicate specifying 
// whether element should be included in the list or not 
let rec collect f (Node(n, children) as node) = 
  // Process recursively all children
  let rest = children |> List.collect (collect f)
  // Add the current element to the front (in case we want to)
  if (f n) then node::rest else rest

// Sample usage
let nodes = collect (fun n -> n%3 = 0) tree

この関数List.collectは、指定された関数をリストのすべての要素に適用しますchildren。各呼び出しは要素のリストを返し、List.collect 返されたすべてのリストを 1 つのリストに連結します。

別の方法として、次のように書くこともできます (これは、コードがどのように機能するかを理解するのに役立つ場合があります)。

let rest = 
   children |> List.map (fun n -> collect f n)
            |> List.concat

リスト内包表記を使って同じことを書くこともできます:

let rec collect f (Node(n, children) as node) = 
  [ for m in children do 
      // add all returned elements to the result
      yield! collect f m
    // add the current node if the predicate returns true
    if (f n) then yield node ]

編集: kvb によって指摘されたノードを返すようにコードを更新しました。

ところで: 一般的には、これまでに作成しようとしたコードを示すことをお勧めします。こうすることで、あなたが理解できなかった部分を人々が理解するのに役立ち、より役立つ回答を得ることができます (また、礼儀正しいと見なされます)。

于 2010-05-12T00:13:55.857 に答える
3

より複雑な末尾再帰ソリューション。

let filterTree (t : Tree) (predicate : int -> bool) =
    let rec filter acc = function
        | (Node(i, []) as n)::tail -> 
            if predicate i then filter (n::acc) tail
            else filter acc tail
        | (Node(i, child) as n)::tail -> 
            if predicate i then filter (n::acc) (tail @ child)
            else filter acc (tail @ child)
        | [] -> acc

    filter [] [t]
于 2010-05-12T01:18:40.070 に答える
2

の使用法を示すためだけにF# Sequences Expression（おそらく最良のアプローチではないかもしれませんが、Tomasのソリューションの方が良いと思います）：

type Tree =
  | Node of int * Tree list

let rec filterTree (t : Tree) (predicate : int -> bool) =
  seq {
    match t with
    | Node(i, tl) ->
        if predicate i then yield t
        for tree in tl do
          yield! filterTree tree predicate 
  }

let test = Node (1, [ Node(2, [ Node(3,[]); Node(3,[]) ]); Node(3,[]) ])

printfn "%A" (filterTree test (fun x -> x = 3))
于 2010-05-12T00:19:59.323 に答える
1

木が立ち往生しているので脳が痛いとき、私は自分が欲しいものをできるだけ簡単かつ明確に言おうとします。

  • 情報のツリーが与えられたら、述語に一致するすべてのサブツリーをリストします（この場合、info = 3）。

これを行う簡単な方法の1つは、ツリーのすべてのノードをリストしてから、述語でフィルター処理することです。

type 'info tree = Node of 'info * 'info tree list

let rec visit = function
    | Node( info, [] )  as node -> [ node ]
    | Node( info, children ) as node -> node :: List.collect visit children

let filter predicate tree = 
    visit tree
    |> List.filter (fun (Node(info,_)) -> predicate info)

OPのサンプルデータに対して実行されたツリーフィルターは次のとおりです。

let result = filter (fun info -> info = 3) test

私を驚かせたのは、適切な述語を持つ任意の情報タイプに対してコードがいかに簡単に機能するかということです。

let test2 = 
    Node(("One",
            [Node("Two",
                    [Node("Three",[Node("Five",[]);Node("Three",[])]);
                    Node("Three",[])]);
            Node("Three",[])]))

let res2 = filter  (fun info -> info = "Three") test2

または、サブツリーではなく情報を一覧表示する場合、コードは驚くほど単純です。

let rec visit = function
    | Node( info, [] )  -> [ info ]
    | Node( info, children ) -> info :: List.collect visit children

let filter predicate tree = 
    visit tree
    |> List.filter predicate

これは同じクエリをサポートしますが、ツリー構造ではなく、'infoレコードのみを返します。

let result = filter (fun info -> info = 3) test

> val result : int list = [3; 3; 3; 3]
于 2010-05-14T06:18:50.053 に答える
0

トーマスのアプローチは標準に見えますが、あなたの例とは完全には一致しません。値ではなく一致するノードのリストが実際に必要な場合は、次のようにします。

let rec filter f (Node(i,l) as t) =
  let rest = List.collect (filter f) l
  if f t then t::rest
  else rest

let filtered = filter (fun (Node(i,_)) -> i=3) test
于 2010-05-12T00:17:30.723 に答える
0

これは過度に設計されたソリューションですが、 Partial Active Patternsによる懸念の分離を示しています。これは部分的にアクティブなパターンの最良の例ではありませんが、それでも楽しい演習でした。Match ステートメントは順番に評価されます。

let (|EqualThree|_|) = function
    | Node(i, _) as n when i = 3 -> Some n
    | _ -> None

let (|HasChildren|_|) = function
    | Node(_, []) -> None
    | Node(_, children) as n -> Some children
    | _ -> None

let filterTree3 (t : Tree) (predicate : int -> bool) =
    let rec filter acc = function
        | EqualThree(n)::tail & HasChildren(c)::_ -> filter (n::acc) (tail @ c)
        | EqualThree(n)::tail -> filter (n::acc) tail
        | HasChildren(c)::tail -> filter acc (tail @ c)
        | _::tail -> filter acc tail
        | [] -> acc

    filter [] [t]
于 2010-05-12T05:07:58.570 に答える