时间戳

首页 > 解决方案 > 为相同长度的整数列表对制定一个任意值

f# - 为相同长度的整数列表对制定一个任意值

问题描述

我需要一些帮助来完成这个关于 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>

它不起作用，我得到长度相同的类型不匹配：

错误：类型不匹配。期待 a'a list -> bool但给定 a 'a list -> 'b list -> bool。类型 bool 与类型不匹配'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

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

错误：类型不匹配。预计有类型int，但这里有类型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

我得到错误：

错误：System.ArgumentException：list1 比 list2 短 1 个元素

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

标签： f#generatorfscheck

解决方案

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

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

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

这样想吧。当你写的时候Arb.filter length Arb.from<int list>，你说的是“我想生成一个任意的int list（一次只生成一个），并根据length规则对其进行过滤。” 但是length您编写的规则需要两个列表并比较它们的长度。如果 FsCheck 只生成一个整数列表，它将与什么长度进行比较？没有第二个可以比较的列表，因此编译器实际上无法将您的代码变成有意义的东西。

您可能想要做的（尽管这有一个问题，我将在一分钟内解决）是生成一对列表，然后将其传递给您的length谓词。即，您可能想要Arb.from<int list * int list>. 这将生成一对整数列表，彼此完全独立。然后你仍然会在你的length函数中得到一个类型不匹配，但你只需要将它的签名从let length xs ys =to 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 文档，我们会发现以下警告：

使用时Gen.filter，一定要提供一个返回概率高的谓词true。如果谓词丢弃“太多”候选者，可能会导致测试运行速度变慢，或者根本不终止。

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

  1. 生成一个非负 int n，它将是该对中两个列表的大小。（对于奖励积分，用于Gen.sized获取您应该生成的数据的“当前大小”，并生n成为 0 和 之间的值size，以便您的列表对生成器，如 FsCheck 的默认列表生成器，将创建从小开始的列表慢慢变大）。
  2. 用于Gen.listOfLength n生成两个列表。（您甚至Gen.two (Gen.listOfLength n)可以轻松生成一对相同大小的列表）。
  3. 不要忘记为一对列表编写一个适当的收缩器，因为练习希望您生成一个适当的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参数。有几种方法可以做到这一点，但最简单的是gen { ... }FsCheck 为我们提供的计算表达式。

顺便说一句，如果您不知道什么是计算表达式，它们是 F# 最强大的功能之一：它们在底层非常复杂，但它们允许您编写看起来非常简单的代码。您应该收藏https://fsharpforfunandprofit.com/series/computation-expressions.html和https://fsharpforfunandprofit.com/series/map-and-bind-and-apply-oh-my.html并计划稍后阅读. 如果您在第一次、第二次甚至第五次阅读时不理解它们，请不要担心：没关系。继续回到这两个系列的文章，并使用像gen或这样的计算表达式seq在实践中，最终概念会变得清晰。每次阅读这些系列时，您都会学到更多知识，并更接近那一刻，当一切都在您的大脑中“点击”时。

但回到你的代码。正如我所说，您想使用gen { ... }计算表达式。在gen { ... }表达式中，let!赋值会将一个对象“解包”Gen<Foo>到生成的Foo中，然后您可以在进一步的代码中使用它。这就是你想用你的sizeint 做什么。因此，我们将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>to Foo），而return关键字包装一个值（类型从Footo Gen<Foo>）。所以那条return线需要一个int list * int list并将它变成一个Gen<int list * int list>。幕后有一些非常复杂的代码，但在计算表达式的表面级别，您只需要考虑“展开”和“包装”类型来决定是否使用let!or return。

推荐阅读