首页 > 代码库 > 8.4.2 F# 决策树

8.4.2 F# 决策树

8.4.2 F# 决策树

 

从规范的最后一句可以看出,链接既可以指向查询,也可以指向最终结果。在 F# 中,我们可以直接使用有两个选项的差别联合类型来写。规范还讲到了查询的详细信息,查询包含不同的字段,因此,可以用F# 的记录类型表示。

我们将定义一个 F# 的记录类型(QueryInfo),表示有关查询的信息,和一个差别联合类型(Decision),它既可以是另一个查询,也可以是最终的结果。这些数据类型相互引用。用函数术语,就是说,类型相互递归(mutually recursive)。清单 8.14 显示了这段 F# 源代码意味着什么。

 

清单 8.14 用相互递归类型描述决策树 (F#)

type QueryInfo =     [1]

  { Title : string 

    Check : Client ->bool   [2]

    Positive :Decision     | 引用第二个类型

    Negative : Decision }  |

and Decision =     [3]

  | Result of string 

  | Query of QueryInfo  <-- 引用第一个类型

 

用 F# 写类型声明,我们只能引用在文件中事先声明的类型(或者,在编译顺序中先指定的文件,或者位于 Visual Studio 解决方案位于前面文件的)。显然,在这种情况下,会导致问题,我们要定义两个的类型之间互相引用。为了解决这个问题,F# 提供了 and 关键字。在清单前面的类型声明像往常一样,用 type 关键字[1],但接着用了 and [3],表示这两个类型同时声明,彼此都可以看到对方。

QueryInfo 声明,把数据和行为组合在一个记录中了。检查的名字是简单的数据成员,但其余成员更有意义。Check 成员[2]是函数,即,是一种行为,它可以返回布尔值,我们将用来在两个后续的分支中选择一个。这些分支是组合值,既可能保存字符串,也可能递归地包含其他 QueryInfo 值,因此,它们可以同时保存数据和行为。另外,函数的返回结果可以是 Decision 值,但是,就不能方便地报告检查是否通过,因为我们只知道下一个运行的检查是什么。在清单 8.15 中,我们创建一个值,表示8.3 图中的决策树。

 

清单 8.15 检查客户的决策树 (F#)

let rec tree =     [1]

  Query({ Title = "More than$40k" 

             Check = (fun cl -> cl.Income > 40000) 

             Positive = moreThan40; Negative = lessThan40 }) 

and moreThan40 =     [2]

  Query({ Title = "Has criminalrecord" 

             Check = (fun cl -> cl.CriminalRecord) 

             Positive = Result("NO"); Negative = Result("YES") }) 

and lessThan40 =     [3]

  Query({ Title = "Years injob" 

             Check = (fun cl -> cl.YearsInJob > 1) 

             Positive = Result("YES"); Negative = usesCredit }) 

and usesCredit =     [4]

  Query({ Title = "Uses creditcard" 

             Check = (fun cl -> cl.UsesCreditCard) 

             Positive = Result("YES"); Negative = Result("NO") })

 

在清单 8.15 中有一件我们之前没见过的新东西。当声明值时,我们同时使用了 rec 关键字与新的 and 关键字,它与先前的清单中同时声明两个类型的用法完全不同,但目的类似。and关键字能够声明相互引用的几个值(或函数)。例如,在 tree [1]的声明中,我们可以使用值 moreThan40 [2],尽管它在代码的后面才声明。

在此示例中,声明顺序是使用let  rec 的主要原因,因为这样能够开始了树的根节点[1],然后,在第二个级上[2][3],为两个可能的选项创建值,最后,在第三级上[4],为一种情况声明额外的问题。我们以前使用 let rec,是为了声明递归函数,这样,能够在函数体中调用函数自身(在声明之前)。一般情况下,F# 还能够声明递归的值,简化许多常见的任务。

 

使用递归的 let 绑定进行初始化

 

我们已经看过几个递归函数的示例,但递归的值会是什么样子呢?使用 Windows Forms 创建用户界面的代码可能会是一个例子;使用简化的 API,看起来可能像这样:

 

let rec form = createForm "Mainform" [ btn ] 

and btn = createButton "Close"(fun () -> form.Close())

 

第一行创建窗体,并把放在窗体上控件的列表作为它的最后一个参数,这个列表只包含一个按钮,在第二行声明。CreateButton 函数的最后一个参数是 lambda 函数,当用户单击按钮时调用,关闭应用程序,因此,需要引用窗体值,而这是在第一行中声明的。

这有什么难的呢?在 C# 中,我们可以轻松地写代码来做同样的事情,而并不认为它是特别的递归。在C# 中,我们在创建窗体之后,为按钮添加事件处理程序,或者,在创建窗体后添加按钮。不管哪种方法,我们都改变了(mutating)对象。通过改变(mutate),实现两个值之间的相互引用很容易,但是,想要值不可变时,问题就来了。

使用递归的 let 绑定,我们可以创建引用其他值的值,并且整个序列一起声明。当然,递归也有其局限性,如下面的代码片断:

 

let rec num1 = num2 + 1 

and num2 = num1 + 1

 

这里,我们为了获取值num2,必须计算 num1;但是,要这样做,我们需要 num1 的值。第一个示例正确的区别在于,form 值只在  lambda 函数内部使用,因此,不立即需要。幸运的是,F# 编译器可以检测到这样不能运行的代码,并生成编译错误。

 

我们已经向展示了如何声明行为与数据结合的记录,以及如何使用 lambda 函数来创建这种记录类型的值。在清单 8.16 中,我们将完成这个示例,实现使用决策树检查客户的函数。

 

清单 8.16 递归处理决策树 (F# Interactive)

> let rec testClientTree(client, tree)=   [1]

     match treewith 

     | Result(message)–>     [2]

      printfn " OFFER A LOAN: %s" message

     | Query(qinfo)–>     [3]

       letresult, case =  

        if (qinfo.Check(client)) then "yes", qinfo.Positive    <-- 根据检查结果而定

        else "no", qinfo.Negative 

      printfn " - %s? %s" qinfo.Title result 

      testClientTree(client, case)    <-- 递归处理子树

;; 

val testClientTree : Client * Decision–> unit

 

> testClientTree(john, tree);;   <-- 交互测试代码

- More than $40k? no 

- Years in job? no 

- Uses credit card? yes 

OFFER A LOAN: YES 

val it : unit = ()

 

程序使用递归函数实现[1]。决策树既可能是最终结果[2],也可能是另一个查询[3]。第一种情况,就输出结果;第二种情况,首先运行检查,并在两个可能的子树中选择一个,根据结果稍后处理。然后,向控制台报告进展情况,并递归调用自身,处理子树。在清单  8.16 中,我们还立即测试代码,看我们的样本客户符合决策树哪一个路径算法。

在本节,我们用 F# 开发了纯函数的决策树。像我们之前见过的,用 C# 重写函数式的结构(尤其是差别联合)可能非常困难,因此,在下一节,我们将用C# 3.0,结合面向对象技术和函数风格,实现类似的解决方案。

 

8.4.2 F# 决策树