再帰的データ構造のフラット化

Question

私は、コメントスレッドのリストの形で再帰的なデータ構造を持っています。各コメントには0個以上の返信（コメント）を含めることができ、各返信には0個以上の返信を含めることができます。私はコメントスレッドのこのリストをフラット化する関数を書こうとしています。つまり、コメントスレッドのリストが与えられていると、すべてのコメントは返信なしに "トップレベル"のコメントとして返されます。私はこれのための関数を書いたが、それは動作しません、それは空のリストを返します。

type Comment = 
    { Text : string 
    Score : int 
    Replies : Comment list } 

let flattenReplies ({ Comments = cs }) = 
    let rec flatten st = 
    match st with 
    | [] -> 
     st 
    | hd::tl -> 
     { hd with Replies = [] } 
     :: tl 
     |> List.collect (fun c -> flatten c.Replies) 
    cs 
    |> Seq.toList 
    |> flatten 

Answer 1

あなたは基本的にDFS/BFSアルゴリズムを実装する必要があります。 また、この種の操作を実行すると、最初のデータ構造がユーザーのニーズに合わないことが示唆される場合があります。

あなたの質問は宿題の問題のように聞こえるので、私はシンプルなDFSの実装を作った、確かにあなたは残りの部分を把握することができます：

type Comment = 
    { Text : string 
    Replies : Comment list } 

let replies = function {Text = _; Replies = rs} -> rs 

let flattenReplies (cs : Comment list) = 
    let rec flatten q res = 
    match q with 
    | [] -> res 
    | h::t -> flatten <| (replies h) @ t <| {h with Replies = []}::res 
    flatten cs []