Справка в разработке древовидной структуры - Сила между функциональным и ООП

Когда дело доходит до «обновления дерева», я думаю, вы всегда можете сделать это довольно элегантно. используя катаморфизмы (складки над деревьями). У меня есть длинная серия блогов об этом, и большая часть приведенного ниже примера кода взята из части 4 серии .

При первом обучении я считаю, что лучше сосредоточиться на конкретном небольшом конкретном постановка задачи. Основываясь на вашем описании, я придумал следующую задачу:

У вас есть двоичное дерево, в котором каждый узел содержит «имя» и «количество» (может думайте об этом как о банковских счетах или о чем-то таком). И я хочу написать функцию который может сказать кому-то «украсть» определенную сумму у каждого из его прямых дети. Вот изображение, чтобы описать то, что я имею в виду:

альтернативный текст http://oljksa.bay.livefilestore.com/y1pNWjpCPP6MbI3rMfutskkTveCWVEns5xXaOf-NZlIz2Hs_CowykUmwtlVV7bP12MwEhmaxnGuwFreeGWGWhWhjs_s_s_s_c_s_s_CowykUmwtlVV7bPXRwE4Whjsg В среднем примере показан результат, который я хочу, если узел «D» просят украсть «10» у каждого из его детей. И правильный пример показывает желаемый результат, если вместо этого я попросил «F» украсть «30» в исходном примере.

type Tree<'T> =                          //'
    | Node of 'T * Tree<'T> * Tree<'T>   //'
    | Leaf

let origTree = Node(("D",1000),
                   Node(("B",1000),
                       Node(("A",1000),Leaf,Leaf),
                       Node(("C",1000),Leaf,Leaf)),
                   Node(("F",1000),
                       Node(("E",1000),Leaf,Leaf),
                       Leaf))

// have 'stealerName' take 'amount' from each of its children and
// add it to its own value
let Steal stealerName amount tree =
    let Subtract amount = function
        | Node((name,value),l,r) -> amount, Node((name,value-amount),l,r)
        | Leaf -> 0, Leaf
    tree |> XFoldTree 
        (fun (name,value) left right ->
            if name = stealerName then
                let leftAmt, newLeft = Subtract amount left
                let rightAmt, newRight = Subtract amount right
                XNode((name,value+leftAmt+rightAmt),newLeft,newRight)
            else
                XNode((name,value), left, right))
        XLeaf
// examples
let dSteals10 = Steal "D" 10 origTree
let fSteals30 = Steal "F" 30 origTree

Вот и все, готово, вы написали алгоритм, который "обновляет" уровни L и L + 1 неизменяемого дерева, просто создав основную логику. Вместо того, чтобы объяснять все это здесь, вы должны пойти прочитать мою серию блогов (по крайней мере, начало: части один два три четыре ).

Вот весь код (который нарисовал рисунок выше):

// Tree boilerplate
// See http://lorgonblog.spaces.live.com/blog/cns!701679AD17B6D310!248.entry
type Tree<'T> =
    | Node of 'T * Tree<'T> * Tree<'T>
    | Leaf
let (===) x y = obj.ReferenceEquals(x,y)    
let XFoldTree nodeF leafV tree =  
    let rec Loop t cont =  
        match t with  
        | Node(x,left,right) -> Loop left  (fun lacc ->   
                                Loop right (fun racc ->  
                                cont (nodeF x lacc racc t)))
        | Leaf -> cont (leafV t)
    Loop tree (fun x -> x)
let XNode (x,l,r) (Node(xo,lo,ro) as orig) = 
    if xo = x && lo === l && ro === r then  
        orig 
    else 
        Node(x,l,r) 
let XLeaf (Leaf as orig) = 
    orig
let FoldTree nodeF leafV tree =  
    XFoldTree (fun x l r _ -> nodeF x l r) (fun _ -> leafV) tree
// /////////////////////////////////////////
// stuff specific to this problem
let origTree = Node(("D",1000),
                   Node(("B",1000),
                       Node(("A",1000),Leaf,Leaf),
                       Node(("C",1000),Leaf,Leaf)),
                   Node(("F",1000),
                       Node(("E",1000),Leaf,Leaf),
                       Leaf))

// have 'stealerName' take 'amount' from each of its children and
// add it to its own value
let Steal stealerName amount tree =
    let Subtract amount = function
        | Node((name,value),l,r) -> amount, Node((name,value-amount),l,r)
        | Leaf -> 0, Leaf
    tree |> XFoldTree 
        (fun (name,value) left right ->
            if name = stealerName then
                let leftAmt, newLeft = Subtract amount left
                let rightAmt, newRight = Subtract amount right
                XNode((name,value+leftAmt+rightAmt),newLeft,newRight)
            else
                XNode((name,value), left, right))
        XLeaf
let dSteals10 = Steal "D" 10 origTree
let fSteals30 = Steal "F" 30 origTree

// /////////////////////////////////////////
// once again,
// see http://lorgonblog.spaces.live.com/blog/cns!701679AD17B6D310!248.entry

// DiffTree: Tree<'T> * Tree<'T> -> Tree<'T * bool> 
// return second tree with extra bool 
// the bool signifies whether the Node "ReferenceEquals" the first tree 
let rec DiffTree(tree,tree2) = 
    XFoldTree (fun x l r t t2 ->  
        let (Node(x2,l2,r2)) = t2 
        Node((x2,t===t2), l l2, r r2)) (fun _ _ -> Leaf) tree tree2 

open System.Windows 
open System.Windows.Controls 
open System.Windows.Input 
open System.Windows.Media 
open System.Windows.Shapes 

// Handy functions to make multiple transforms be a more fluent interface 
let IdentT() = new TransformGroup() 
let AddT t (tg : TransformGroup) = tg.Children.Add(t); tg 
let ScaleT x y (tg : TransformGroup) = tg.Children.Add(new ScaleTransform(x, y)); tg 
let TranslateT x y (tg : TransformGroup) = tg.Children.Add(new TranslateTransform(x, y)); tg 

// Draw: Canvas -> Tree<'T * bool> -> unit 
let Draw (canvas : Canvas) tree = 
    // assumes canvas is normalized to 1.0 x 1.0 
    FoldTree (fun ((name,value),b) l r trans -> 
        // current node in top half, centered left-to-right 
        let tb = new TextBox(Width=100.0, Height=100.0, FontSize=30.0, Text=sprintf "%s:%d" name value, 
                             // the tree is a "diff tree" where the bool represents 
                             // "ReferenceEquals" differences, so color diffs Red 
                             Foreground=(if b then Brushes.Black else Brushes.Red),  
                             HorizontalContentAlignment=HorizontalAlignment.Center, 
                             VerticalContentAlignment=VerticalAlignment.Center) 
        tb.RenderTransform <- IdentT() |> ScaleT 0.005 0.005 |> TranslateT 0.25 0.0 |> AddT trans 
        canvas.Children.Add(tb) |> ignore 
        // left child in bottom-left quadrant 
        l (IdentT() |> ScaleT 0.5 0.5 |> TranslateT 0.0 0.5 |> AddT trans) 
        // right child in bottom-right quadrant 
        r (IdentT() |> ScaleT 0.5 0.5 |> TranslateT 0.5 0.5 |> AddT trans) 
    ) (fun _ -> ()) tree (IdentT()) 

let TreeToCanvas tree =
    let canvas = new Canvas(Width=1.0, Height=1.0, Background = Brushes.Blue, 
                            LayoutTransform=new ScaleTransform(400.0, 400.0)) 
    Draw canvas tree
    canvas

let TitledControl title control =
    let grid = new Grid()
    grid.ColumnDefinitions.Add(new ColumnDefinition())
    grid.RowDefinitions.Add(new RowDefinition())
    grid.RowDefinitions.Add(new RowDefinition())
    let text = new TextBlock(Text = title, HorizontalAlignment = HorizontalAlignment.Center)
    Grid.SetRow(text, 0)
    Grid.SetColumn(text, 0)
    grid.Children.Add(text) |> ignore
    Grid.SetRow(control, 1)
    Grid.SetColumn(control, 0)
    grid.Children.Add(control) |> ignore
    grid

let HorizontalGrid (controls:_[]) =
    let grid = new Grid()
    grid.RowDefinitions.Add(new RowDefinition())
    for i in 0..controls.Length-1 do
        let c = controls.[i]
        grid.ColumnDefinitions.Add(new ColumnDefinition())
        Grid.SetRow(c, 0)
        Grid.SetColumn(c, i)
        grid.Children.Add(c) |> ignore
    grid

type MyWPFWindow(content, title) as this = 
    inherit Window()

    do  
        this.Content <- content
        this.Title <- title
        this.SizeToContent <- SizeToContent.WidthAndHeight  

[<System.STAThread()>] 
do  
    let app =  new Application() 
    let controls = [|
        TitledControl "Original" (TreeToCanvas(DiffTree(origTree,origTree)))
        TitledControl "D steals 10" (TreeToCanvas(DiffTree(origTree,dSteals10)))
        TitledControl "F steals 30" (TreeToCanvas(DiffTree(origTree,fSteals30))) |]
    app.Run(new MyWPFWindow(HorizontalGrid controls, "Fun with trees")) |> ignore