Сформулируйте произвольное для пары списков целых одинаковой длины - PullRequest
Новая
       19

Сформулируйте произвольное для пары списков целых одинаковой длины

3 голосов
/ 28 мая 2019

Мне нужна помощь, чтобы выполнить это упражнение о генераторах в 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 list -> bool, но учитывая 'a list -> 'b list -> bool. Тип bool не соответствует типу 'a list -> bool.

Edit:

Как и предполагалось, я пытался следовать плану шагов, но я застрял. 

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 на 1 элемент короче list2

Но почему? Мой генератор должен генерировать только два списка одинаковой длины.

1 Ответ

4 голосов
/ 28 мая 2019

Если мы посмотрим на ссылку API для модуля Arb и наведем курсор мыши на определение filter, вы увидите, что тип Arb.filter: 

pred:('a -> bool) -> a:Arbitrary<'a> -> a:Arbitrary<'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 = на 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 здесь, где mapper равен 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, который затем можно будет использовать в дальнейшем коде.Что вы хотите сделать со своим 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 переносит значение (тип идет от Foo до Gen<Foo>).Таким образом, строка return принимает int list * int list и превращает ее в Gen<int list * int list>.Есть некоторый очень сложный код, происходящий изнутри, но на поверхностном уровне выражения вычисления вам просто нужно подумать с точки зрения типов «разворачивания» и «обертывания», чтобы решить, использовать ли let! или return.

...