Проблемы с получением списка делителей числа в Хаскеле

Question

Это не повторяющийся вопрос .Читайте ниже ...

Я объявляю следующую функцию:

divisors x = [(a, x/a) | a <- [2..(sqrt x)], x `mod` a == 0]

То, что я хочу получить, это делители x: список кортежей, который будет содержать (n, k) например n * k = x

Пример:

> divisors x
[(1,10), (2, 5)]

Почему вышеприведенный код не работает?

Выдает ошибку:

*Main> divisors 10

<interactive>:1:0:
    Ambiguous type variable `t' in the constraints:
      `Floating t'
        arising from a use of `divisors' at <interactive>:1:0-10
      `Integral t'
        arising from a use of `divisors' at <interactive>:1:0-10
    Probable fix: add a type signature that fixes these type variable(s)

Я пытался вручную установить сигнатуру функции без успеха ...

Answer 1

Проблема в том, что sqrt возвращает Floating a, и вам действительно нужны целые числа при поиске делителей. Вы можете превратить Floating a в Integral a с ceiling, floor или round. Я буду использовать ceiling, поскольку я не уверен, что использование floor или average не пропустит делитель.

Функция sqrt также принимает только плавающее число, поэтому вам нужно преобразовать целое число в плавающее, прежде чем передать его ему (это можно сделать с помощью fromIntegral).

Также вы используете /, который также работает с плавающими числами. Использование div лучше, поскольку оно работает с целыми числами (округление при необходимости).

divisors x = [(a, x `div` a) | a <- [2..(ceiling $ sqrt $ fromIntegral x)], x `mod` a == 0]

При этом divisors 10 даст [(2,5)] (ваш код предотвращает случай (1,10) - я предполагаю, что это было преднамеренно). К сожалению, вы получите дубликаты, например, divisors 12 вернет [(2,6),(3,4),(4,3)], но это не должно быть слишком сложно исправить, если это проблема.

Answer 2

Вы можете увидеть проблему, если спросите тип:

 divisors :: (Integral t, Floating t) => t -> [(t, t)]

, а затем проверьте, какие вещи являются Integral и Floating:

 Prelude> :info Floating
 class Fractional a => Floating a where
 instance Floating Float -- Defined in GHC.Float
 instance Floating Double -- Defined in GHC.Float

и

 Prelude> :info Integral
 class (Real a, Enum a) => Integral a where
 instance Integral Integer -- Defined in GHC.Real
 instance Integral Int -- Defined in GHC.Real

, поэтому он не может быть Int, Integer, Float или Double.У вас проблемы ...

К счастью, мы можем конвертировать между типами, так что если sqrt нужен плавающий, а mod нужен интеграл (кстати, rem быстрее), мыможет либо, например, покончить с делением с плавающей запятой:

 divisors :: Integer -> [(Integer, Integer)]
 divisors x = [(a, x `div` a) | a <- [2..ceiling (sqrt (fromIntegral x))], x `rem` a == 0]

 > divisors 100
 [(2,0),(4,0),(5,0),(10,0)]

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

Answer 3

В Хаскеле целочисленное деление и дробное деление - это разные операции и имеют разные имена. Оператор косой черты / предназначен для дробного деления. Целочисленное деление выполняется с помощью div или quot (разница между этими двумя факторами связана с поведением при наличии отрицательных чисел).

Попробуйте заменить x/a на

x `quot` a

вместо.

Ошибка компилятора говорит вам именно это: вы рассматриваете тип иногда как целое число (с помощью mod), а иногда как дробное число (с помощью /), и он не уверен, как выбрать тип, который действует как оба из них.

У вас будет похожая проблема с sqrt, как только она будет отсортирована. Опять же, вы должны быть последовательными в том, являются ли ваши типы целыми числами или (в этом случае) с плавающей точкой Для нахождения возможных делителей достаточно, чтобы диапазон достигал наибольшего целого числа, меньшего числа с плавающей запятой, поэтому рассмотрите возможность использования floor (sqrt (fromIntegral x))). fromIntegral преобразует x (который должен иметь целочисленный тип) в другой тип - в этом случае по умолчанию он будет Double. Затем floor преобразует результат Double обратно в целочисленный тип.

Answer 4

Вместо того, чтобы использовать квадратный корень для ограничения поиска, вы можете позволить пониманию охватывать бесконечный список и использовать takeWhile, чтобы остановить поиск, когда остаток больше делителя:

divisors x = takeWhile (uncurry (<=)) [(a, x `div` a) | a <- [1..], x `mod` a == 0]

> divisors 100
[(1,100),(2,50),(4,25),(5,20),(10,10)]

Примечание: ваш оригинальный пример показывает (1,10) как один из divisors из 10, поэтому я начал понимать с 1 вместо 2.

Хм, этот поиск выходит за пределы квадратного корня, пока не достигнет следующего фактора выше.

Как насчет этого:

divisors x = [(a, x `div` a) | a <- takeWhile ((<= x) . (^2)) [1..], x `mod` a == 0]