统计数据类型的非递归

我有一个数据类型：统计数据类型的非递归

datatype int A = leaf of int * string 
       | trunk of int * (int A) list

说，如果我有测试：INT A，那么我想算叶子和树干的测试，并返回他们为一对夫妇：（＃叶子，＃中继）。但是我不想使用递归。

这是我的尝试：

fun count(test: int A): int*int = 
     case test 
     of trunk(a,l) => 
      let 
       val l1 = List.filter(fn trunk(a',l') => true 
            | _ => false) l 
       val l2 = List.filter(fn leaf(a',s) => true 
            | _ => false) l 
      in 
       (List.length(l2), List.length(l1) + 1) 
      end 
      | leaf(a,s) => (1, 0)

这只要可以作为L”是零。正如你所看到的，我将发束和中继线分成不同的列表并返回长度。但是，l'可以包含未被计数的其他树叶和树干。注意这不是递归的。我一直在考虑尝试使用延续，但我不知道如何去做。有什么建议吗？

来源

2014-10-27 Sarah cartenz

你能帮助我知道你为什么不想在这里使用递归吗？这是在这里推理的一种非常自然的方式。 – Jon 2014-10-28 14:29:43

我宁愿使用像reduce和map这样的列表操作！这是以不同方式做事的一种方式。 – 2014-10-29 10:09:33

让我们考虑一个更简单的数据类型（'数据类型'树'树列表'）和一个例子。你如何找到这个中继线的中继线数量？val x = trunk（[trunk（[trunk（[]）]）]' – Jon 2014-10-30 14:22:19

由于我们的数据类型与列表不同，因此我们需要为它制定明确的缩减函数。这个reduce函数接受一个应用于每个叶子的函数（ff）。它还包含一个应用于每条干线并递归组合结果的函数（fd）。它看起来像这样：

fun reduce(ff:('a*string -> 'b))(fd:('a * 'b list -> 'b))(s: int A): 'b = 
     case s 
     of leaf(a, d) => ff(a,d) 
      | trunk(a, l) => fd(a, List.map(fn x => reduce(ff)(fd)(x)) l)

最后，我们的计数功能看起来像这样：

乐趣计数（S：INT A）：INT * INT =

let 
    val i = reduce(fn x => 1)(fn (y,l) => foldr op+ 0 l)(s) 
    val i' = reduce(fn x => 0)(fn (y,l) => 1 + foldr op+ 0 l)(s) 
    in 
    (i, i') 
    end

那在（i）中，如果找到一个叶子，用1替换它，如果找到一个树干，则用0替换它，然后求和整个列表。在（i'）中，如果发现叶子，则用0替换它。否则，如果发现树干并加上1，则加1。

来源

2014-11-08 13:12:42

统计数据类型的非递归

回答

相关问题