Помогите с отладкой неожиданного поведения takeWhile с большими числами в Haskell

Question

Во-первых, извиняюсь за смутное название, но я не уверен точно , что я здесь спрашиваю (!).

После встречи с Хаскеллом в университете я недавноЯ начал использовать его в гневе и поэтому работаю над проблемами Project Euler как расширенный Hello World, правда.Я столкнулся с ошибкой в ​​одном из моих ответов, которая, кажется, предполагает неправильное понимание фундаментальной части языка, и это не то, что я мог бы понять из учебных пособий, или что-то, что я достаточно знаю, чтобы начать поиск в Google.

Краткое описание самой проблемы - решение относится к простым числам, поэтому я хотел получить бесконечный список простых чисел, который я реализовал (пока без оптимизации!) Таким образом:

isPrime :: Int -> Bool
isPrime n = isPrime' 2 n
            where isPrime' p n | p >= n           = True
                               | n `mod` p == 0  = False
                               | otherwise       = isPrime' (p+1) n

primes :: [Int]
primes = filter isPrime [2..]

Поскольку бесконечные спискиможет быть немного утомительно оценивать, я, конечно, буду использовать ленивую оценку, чтобы гарантировать, что только те части, которые я хочу, будут оценены.Так, например, я могу попросить GHCI о простых числах меньше 100:

*Main> takeWhile (< 100) primes
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]

Теперь вот часть, которую я совсем не понимаю - , когда верхний предел становится достаточно большим,Я не получаю ответов вообще .В частности:

*Main> takeWhile (< 4000000000) primes
[]

Это не проблема с самим takeWhile или частично примененной функцией, так как takeWhile (< 4000000000) [2..] работает, как я и ожидал.Это не проблема с моим использованием фильтра (в пределах определения primes), так как takeWhile (< 4000000000) (filter even [2..]) также возвращает ожидаемый результат.

Посредством бинарного поиска я обнаружил, что наибольшим верхним пределом, который работает, является 2^31 - 1, так что это, безусловно, подразумевает какое-то пространственное ограничение (то есть наибольшее целое число со знаком со знаком).Однако:

1. У меня сложилось впечатление, что у Haskell нет языковых ограничений на размер целых чисел, и они ограничены только количеством свободной памяти.
2. Это число появляется тольков менее чем предикате, который, как я знаю, работает, как и ожидалось, по крайней мере, в некоторых случаях.Конечно, когда он применяется к элементам списка, это не должно волновать, откуда они берутся?Глядя только на первый элемент, я знаю , что предикат возвращает true для ввода 2, когда он приходит от filter even [2..];Я знаю , что primes возвращает 2 в качестве первого элемента.Итак, как мой список может быть пустым, как этот предикат не работает «для некоторых значений 2»?

Любые мысли были бы благодарны, так как у меня недостаточно опыта, чтобы знать, с чего начатьодин.Спасибо, что нашли время взглянуть.

Answer 1

В haskell есть 2 встроенных интегральных типа: Int и Integer.Integer является значением по умолчанию и не ограничено.Int однако ограничен.Поскольку вы явно используете Int в типе, для isPrime 4000000000 используется как Int и переполнения.Если вы измените тип isPrime на Integer -> Bool или даже лучше Integral a => a -> Bool (читай: функция, которая может принимать любое значение Integral и возвращает Bool), она будет работать как положено.

Важная вещь, которую следует здесь исключить (кроме разницы между Int и Integer), заключается в том, что тип 4000000000 зависит от того, как он используется.Если он используется в качестве аргумента функции, которая принимает Int, это будет Int (а в 32-разрядных системах она будет переполнена).Если он используется в качестве аргумента функции, которая принимает Integer, это будет Integer (и никогда не переполняется).Если он используется в качестве аргумента функции, которая принимает любой тип Integral, он также будет Integer, поскольку Integer является экземпляром по умолчанию Integral.

Answer 2

Это простой ответ (... который, как я вижу, уже частично отвечен) - "преждевременная специализация".

Первая часть вашего определения, сигнатура типа, определяет:

isPrime :: Int -> Bool

Int - это не просто быстрый способ сказать, что Integer - - это разные типы !Чтобы быть придиркой (которая, в свою очередь, побуждает всех разорвать множество мест здесь, где я не точен), существуют никогда"различные значения 2" - это должнобыть типа Int, потому что именно так вы указали функцию (вы сравниваете 2 с аргументом функции n, и вам разрешено сравнивать только значения того же типа, поэтому ваш 2 "привязан" к *Тип 1015 *.

О, и, как предупреждение, тип Int - это тип, который просто распространен с возможностью создания углового регистра. Если ваша система построена в 64-битной среде, то ваш Int также будетбыть основанным на 64-битном представлении, и ваш пример будет работать до 2 ^ 63-1, а не 2 ^ 31-1, как ваш. Обратите внимание на мою фразу: у меня 64-битный компьютер с ОС MS Windows,Это означает, что пока еще нет официального 64-битного набора инструментов MinGW - моя ОС 64-битная, но у меня есть версия GHC, скомпилированная с 32-битными библиотеками, поэтому она имеет 32-битные Int s.Я использую Linux, даже в виртуальной машине, она имеет 64-битный инструментарийпоэтому Int с 64 бит.Если бы вы использовали один из них, вы, возможно, даже не заметили такого поведения!

Итак, я думаю, это еще одна причина быть осторожным при рассуждении о ваших типах.(Особенно в Хаскеле, во всяком случае ....)