为一对相同长度的整数列表制定一个 Arbitrary

Question

我需要一些帮助来做这个关于 f# 中生成器的练习。

函数

List.zip : ('a list -> 'b list -> ('a * 'b) list)

和

List.unzip : (('a * 'b) list -> 'a list * 'b list)

互为倒数，条件是对列表进行操作相同的长度。为相同长度的一对整数列表制定任意值

我试着写了一些代码：

let length xs ys = 
    List.length xs = List.length ys

let samelength = 
    Arb.filter length Arb.from<int list>

它不起作用，我在 samlength 中得到长度类型不匹配：

Error: type mismatch. Expecting a 'a list -> bool but given a 'a list -> 'b list -> bool. The type bool does not match the type 'a list -> bool.

编辑：

按照建议，我尝试按照步骤大纲进行操作，但我卡住了。

let sizegen =
    Arb.filter (fun x -> x > 0) Arb.from<int>

let listgen =
    let size = sizegen 
    let xs = Gen.listOfLength size
    let ys = Gen.listOfLength size
    xs, ys

当然我有错误类型不匹配：

Error: type mistmatch. Expected to have type int but here has type Arbitrary<int>

编辑

我解决了这个练习，但是当我做测试时我的生成器似乎不工作，看起来另一个被调用了。

let samelength (xs, ys) = 
   List.length xs = List.length ys

let arbMyGen2 = Arb.filter samelength Arb.from<int list * int list> 

type MyGeneratorZ =
   static member arbMyGen2() = 
    {
        new Arbitrary<int list * int list>() with
            override x.Generator = arbMyGen2 |> Arb.toGen
            override x.Shrinker t = Seq.empty
    }

let _ = Arb.register<MyGeneratorZ>()

let pro_zip (xs: int list, ys: int list) = 
   (xs, ys) = List.unzip(List.zip xs ys)

do Check.Quick pro_zip

我收到错误：

Error: System.ArgumentException: list1 is 1 element shorter than list2

但是为什么呢？我的生成器应该只生成两个相同长度的列表。

Answer 1

如果我们查看 API reference for the Arb module，并将鼠标悬停在 filter 的定义上，您会看到 Arb.filter 的类型是：

pred:('a -> bool) -> a:Arbitrary<'a> -> a:Arbitrary<'a>

这意味着谓词应该是一个参数的函数，return是一个bool。但是你的 length 函数是两个参数的函数。你想把它变成一个只有一个参数的函数。

这样想。当你写 Arb.filter length Arb.from<int list> 时，你说的是 "I want to generate an arbitrary int list (just one at a time), and filter it according to the length rule." 但是你写的 length 规则需要两个列表并比较它们的长度。如果 FsCheck 只生成一个整数列表，它将把它的长度与什么进行比较？没有第二个列表可供比较，因此编译器实际上无法将您的代码转换为有意义的代码。

您可能想要做的（尽管这有一个问题，我将在一分钟内解决）是生成对列表，然后将其传递给你的 length 谓词。即，您可能想要 Arb.from<int list * int list>。这将生成一对整数列表，彼此完全独立。然后你仍然会在你的 length 函数中得到一个类型不匹配，但是你只需要将它的签名从 let length xs ys = 变成 let length (xs,ys) =，例如让它接收包含一对列表的单个参数，而不是将每个列表作为单独的参数。经过这些调整后，您的代码如下所示：

let length (xs,ys) = 
    List.length xs = List.length ys

let samelength = 
    Arb.filter length Arb.from<int list * int list>

但是这个还是有问题。具体来说，如果我们查看 FsCheck documentation，我们会发现此警告：

When using Gen.filter, be sure to provide a predicate with a high chance of returning true. If the predicate discards 'too many' candidates, it may cause tests to run slower, or to not terminate at all.

顺便说一句，这适用于 Arb.filter 和 Gen.filter。您的代码目前的方式，这是一个问题，因为您的过滤器将丢弃大多数列表对。由于列表是彼此独立生成的，因此它们通常具有不同的长度，因此大多数时候您的过滤器将 return false。我建议采用不同的方法。既然你说这是一个练习，我就不给你写代码了，你自己做会学到更多；我将简要说明您要采取的步骤。

生成一个 non-negative int n，这将是对中两个列表的大小。（对于奖励积分，使用Gen.sized得到你应该生成的数据"current size"，并生成n作为0到size之间的值，这样你的list-pair 生成器，就像 FsCheck 的默认列表生成器一样，将创建从小开始慢慢变大的列表。
使用Gen.listOfLength n生成两个列表。（您甚至可以 Gen.two (Gen.listOfLength n) 轻松生成一对相同大小的列表）。
不要忘记为一对列表编写适当的收缩器，因为练习要您生成适当的 Arbitrary，而没有收缩器的 Arbitrary 是在实践中不是很有用。您可能可以在这里使用 Arb.mapFilter 做一些事情，其中映射器是 id 因为您已经生成了匹配长度的列表，但是过滤器是您的 length 谓词。然后使用 Arb.fromGenShrink 将您的生成器和收缩器函数转换为适当的 Arbitrary 实例。

如果该大纲不足以让您正常工作，请再问一个关于您遇到困难的问题，我很乐意尽我所能提供帮助。

编辑：

在您尝试使用 sizegen 编写列表生成器的编辑中，您有以下不起作用的代码：

let listgen =
    let size = sizegen 
    let xs = Gen.listOfLength size
    let ys = Gen.listOfLength size
    xs, ys

此处 sizegen 是一个 Gen<int> 并且您想从中提取 int 参数。有几种方法可以做到这一点，但最简单的是FsCheck为我们提供的gen { ... }计算表达式。

顺便说一句，如果您不知道什么是计算表达式，它们是 F# 的一些最强大的功能：它们在幕后非常复杂，但它们允许您编写非常 simple-looking 的代码。您应该将 https://fsharpforfunandprofit.com/series/computation-expressions.html and https://fsharpforfunandprofit.com/series/map-and-bind-and-apply-oh-my.html 添加为书签并计划稍后阅读。如果您在第一次、第二次甚至第五次阅读时不理解它们，请不要担心：没关系。只要不断回到这两个系列的文章，并在实践中使用 gen 或 seq 等计算表达式，最终概念就会变得清晰。每次阅读这些系列时，您都会学到更多，并更接近那一刻的开悟，当它在您的大脑中 "clicks"。

但是回到你的代码。正如我所说，您想使用 gen { ... } 计算表达式。在 gen { ... } 表达式中，let! 赋值会将 "unwrap" 一个 Gen<Foo> 对象放入生成的 Foo 中，然后您可以在进一步的代码中使用它。这就是您想用 size int 做什么。所以我们将在您的代码周围包裹一个 gen { ... } 表达式，并得到以下内容：

let listgen =
    gen {
        let! size = sizegen 
        let xs = Gen.listOfLength size
        let ys = Gen.listOfLength size
        return (xs, ys)
    }

请注意，我还在最后一行添加了一个 return 关键字。在计算表达式中，return 与 let! 具有相反的效果。 let! 关键字展开一个值（类型从 Gen<Foo> 到 Foo），而 return 关键字 wraps 一个值（类型从 Foo 到 Gen<Foo>）。以便return 行采用 int list * int list 并将其转换为 Gen<int list * int list>。幕后有一些非常复杂的代码，但在计算表达式的表层，你只需要考虑 "unwrapping" 和 "wrapping" 类型来决定是否使用 let! 或 return.

为一对相同长度的整数列表制定一个 Arbitrary

Formulate an Arbitrary for pair of lists of ints of the same length

f#

generator

fscheck