Создайте генератор элементов с бесконечным списком

Я играю с QuickCheck и наткнулся на какое-то странное поведение

sample $ elements [1..5]

однако работает как положено

sample $ elements [1..]

зависает в ghci, даже при использовании конечного типа, такого как Int

sample $ elements [(1::Int)..]

Почему он не печатает произвольные (каламбур :) большие Ints?

Обновить

Я проверил объяснение @amalloy, используя

sample $ elements ([1 .. ] :: [Int8])

что прекращается.


haskell quickcheck
person dimid    schedule 08.09.2016    source источник

Ответы (2)


arrow_upward
4
arrow_downward

elements равномерно выбирает элементы случайным образом, что означает, что в среднем в список попадет length / 2 элементов. Для бесконечных значений это невозможно, а для больших конечных списков, таких как [1..] :: [Int], это все еще достигает 1 миллиарда элементов, по одному через связанный список. Довольно медленная операция!

person amalloy    schedule 08.09.2016
comment
Спасибо, почему в среднем длина достигает 2 элементов? - person dimid; 08.09.2016
comment
Я имею в виду, подумай об этом. В списке с N элементами, каков средний индекс? Середина — это среднее значение, и оно имеет индекс N/2. Поскольку вы выбираете случайным образом, ваш средний индекс будет средним индексом списка. - person amalloy; 08.09.2016
comment
Верно, но зачем вам проходить первые [len/2] - 1 элементов? Если вы знаете максимальное Int, вы можете получить его за O(1), разделив на 2. Извините, если я упустил что-то очевидное, я новичок в хаскеле. - person dimid; 08.09.2016
comment
Списки в Haskell всегда являются связанными списками. - person amalloy; 08.09.2016
comment
Понятно, значит, даже целочисленные списки не имеют произвольного доступа? Это звучит ужасно неэффективно. - person dimid; 08.09.2016
comment
Вы используете что-то другое, кроме списка, когда вам нужен произвольный доступ. Массив, например. - person amalloy; 08.09.2016
comment
@dimid Это действительно неэффективно, когда вам нужен произвольный доступ. Однако во многих случаях это не так. Кроме того, рассмотрите простой код, такой как let list = ... in (1:list, 2:list). Связанные списки могут построить последнюю пару за O (1), а массивы — нет. И массивы никогда не могут выражать бесконечные (ленивые) списки, такие как [1..] :: [Integer], которые иногда удобно использовать. - person chi; 08.09.2016

arrow_upward
1
arrow_downward

Кажется, что elements плохо документирован. Помимо того, что аргумент непустой, он должен быть конечным. См. исходный код:

-- | Generates one of the given values. The input list must be non-empty.
elements :: [a] -> Gen a
elements [] = error "QuickCheck.elements used with empty list"
elements xs = (xs !!) `fmap` choose (0, length xs - 1)

Он пытается вычислить длину входного списка, что вызовет бесконечный цикл в бесконечном списке.

person crockeea    schedule 08.09.2016
comment
На самом деле, как указал amalloy, рассматриваемый список конечен из-за типа [Int]. В зависимости от вашей машины Int может быть 32- или 64-битным. В первом случае компьютер с большим объемом оперативной памяти может выйти из строя (в конце концов). В последнем случае вам точно не хватит памяти. - person crockeea; 08.09.2016