首页 > 代码库 > 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# 决策树