帮助设计树结构 - 功能和OOP之间的张力

Question

我在前几天一直在学习f#,写了一个小项目,最后工作(当然是在SO的帮助下).

我正在努力学习尽可能惯用,这基本上意味着我试图不改变我的数据结构.这让我付出了很多努力:-)在我寻找惯用函数式编程时,我一直在尝试使用尽可能多的列表,元组和记录,而不是对象.但随后"praticality打败纯度",所以这次我用对象改写我的小项目.

我认为你可以给我一些建议,当然我对"良好的函数式编程设计"的想法还没有很好地定义.

例如,我必须修改树的节点,同时修改两个不同级别(L和L + 1)的状态.我已经能够在不改变数据的情况下做到这一点,但我需要很多"内部"和"辅助"功能,有累加器等等.由于需要以涉及的方式修改我的数据结构,因此能够清楚地表达算法的美妙感觉已经丢失.这在命令式语言中非常容易,例如:只需取消引用指向相关节点的指针,修改它们的状态并进行迭代.当然我没有正确设计我的结构,因此我现在正在尝试OOP方法.

我看过SICP,如何设计程序,并找到了C. Okasaki的论文("纯功能数据结构"),但SICP和HTDP的例子与我的做法相似,或者我可能不能完全理解它们.另一方面,论文对我来说有点太难了:-)

您如何看待我所经历的这种"紧张"？我是否过于严格地解释"永不变异数据"？你能给我一些资源吗？

在此先感谢Francesco

Answer 1

当谈到'树更新'时,我认为你总是可以使用catamorphisms(折叠在树上)非常优雅.我有一个关于此的长篇博客系列,下面的大多数示例代码都来自该系列的第4部分.

在第一次学习时,我发现最好关注一个特定的小的,具体的问题陈述.根据您的描述,我发明了以下问题:

你有一个二叉树,每个节点都包含一个"名称"和一个"金额"(可以把它想象成银行账户或其他一些).我想写一个功能,可以告诉别人从他的每个直接孩子那里"窃取"一定数量的东西.这是描述我的意思的图片:

alt text http://oljksa.bay.livefilestore.com/y1pNWjpCPP6MbI3rMfutskkTveCWVEns5xXaOf-NZlIz2Hs_CowykUmwtlVV7bPXRwh4WHJMT-5hSuGVZEhmAIPuw/FunWithTrees.png

在左边我有一棵原始树.中间的例子显示了我想要的节点'D'从他的每个孩子那里偷'10'的结果.正确的例子显示了期望的结果是什么,而不是我要求'F'在原始示例中窃取'30'.

请注意,我使用的树结构将是不可变的,并且图中的红色相对于原始树指定"新树节点".即黑色节点与原始树结构共享(Object.ReferenceEquals彼此).

现在,假设一个典型的树结构

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级别.不是都在这里解释一下,你应该去阅读我的博客系列(至少开始:零件一个 2 3 4).

这是所有代码(如上图所示):

// 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