F# 搜索数据树并更新

Question

>更新：

帕维尔正确地回答了最初的问题，让我意识到我遗漏了一个重要的细节——搜索是在第 n 个父母身上。 我很好奇是否有更优雅的解决方案，但至少我得到了一些有用的东西。

type searchf = 
| None of None: unit
| CountUp of CountUp: int
| ParentNode of ParentNode: Node
let search (nthParent: int) (tree: Node) (child: Node): Node = 
if (nthParent = -1) //-1 Top, 0 Current, 1 Parent, 2 Grandparent
then tree
else
let rec f (t: Node): searchf = 
match t = child with
| true when nthParent = 0 -> ParentNode t
| true  -> CountUp nthParent
| _ -> 
let foldSubs (acc: searchf) (xy: Node): searchf = 
match acc with 
| CountUp i -> CountUp i
| _ -> f xy
let acc =
match t.ChildNode with
| [] -> None ()
| x -> x |> List.fold foldSubs (None ())
match acc with
| CountUp x when x = 1 -> ParentNode t //parent found in sub list, so this is it
| CountUp x -> CountUp (x - 1)
| _ -> acc
match (f tree) with 
| ParentNode t -> t
| _ -> tree  

原始问题：

我有一棵小树，通常每个分支 2-5 个节点，最大深度为 4。我一直在试图找出在树中搜索节点并返回更新树的功能方式。

//I'm not opposed to adding a key field, but my tree does not have one naturally.
type Node = { Name: string; ChildNode: Node list; }
let newNode (name: string)(childNode: Node list) = 
{Name=name; ChildNode=childNode;}
let tree = 
newNode 
"Main" [
newNode "File" [
newNode "Open" [];
newNode "Close" [];
newNode "Print" [
newNode "Preview" [];
newNode "Settings" [];
]
];
newNode "Edit" [
newNode "Cut" [];
newNode "Copy" [];
newNode "Paste" [];
newNode "Preferences" [
newNode "User" [];
newNode "System" [];
]
]
]
let updateTree (tree: Node ) (oldNode: Node ) (newNode: Node ): Node =
//??
tree
let randomNode = tree.ChildNode.[1].ChildNode.[3]
let newRandomNode = { randomNode with Name = "Options"}
let updatedTree = updateTree tree randomNode newRandomNode

Answer 1

下面是一个简单的例子。

let rec updateTree tree oldNode newNode =
if tree = oldNode
then newNode
else { tree with ChildNode = [for a in tree.ChildNode -> updateTree a oldNode newNode]}

上级： 随着问题的更新，这是另一种解决方案。 要找到节点的第 n 个父节点，您可以使用这样的东西。

type SearchResult =
| Failure
| Incomplete of int
| Complete of Node
let searchNthParent nthParent node target = 
if nthParent < 0
then Complete node
else 
// You can just use this function if you 
// don't need check on nthParent < 0
let rec inFunc left node target =
if node = target 
then
if left > 0 
then Incomplete left 
else Complete node
else
let rec iterateWhileFailure f list =
match list with
| [] -> Failure
| h::t ->
match f left h target with
| Failure -> iterateWhileFailure f t
| a -> a
match iterateWhileFailure inFunc node.ChildNode with
| Incomplete left when left > 1 -> Incomplete (left - 1)
| Incomplete _ -> Complete node
| a -> a
inFunc nthParent node target