Новичок в Haskell: ошибка "Нет экземпляра для... возникающего из..."

Question

Моя цель - написать функцию, которая вычисляет максимальное число Коллатца ниже определенного числа 'n'. (Это вопрос проекта Эйлера для тех, кто знаком.)

Некоторый контекст: число Коллатца для данного целого числа равно длине последовательности Коллатца для этого целого числа. Последовательность Коллатца для целого числа вычисляется следующим образом: первое число ("n0") в последовательности - это само это целое число; если n0 четное, следующее число в последовательности ("n1") равно n / 2; если n0 нечетно, то n1 равно 3 * n0 + 1. Мы продолжаем рекурсивное расширение последовательности до тех пор, пока не достигнем 1, после чего последовательность заканчивается. Например, последовательность Коллатца для 5: {5, 16, 8, 4, 2, 1} (потому что 16 = 3 * 5 + 1, 8 = 16 / 2, 4 = 8 / 2,...)

Я пытаюсь написать функцию ("maxCollatzUnder"), которая, когда передано целое число "m", возвращает целое число (меньше или равно m), которое имеет самую длинную последовательность Коллатца (то есть, наибольшее число Коллатца). Например, maxCollatz 20 (то есть, какое целое число ниже (включительно) 20 имеет самую длинную последовательность коллажей?) Должно возвращать 19 (число 19 имеет последовательность Коллатца длины 21: [19,58,29,88,44,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1]).

В приведенном ниже коде функции "collatz" и "collatzHelper" компилируются и работают правильно. У меня проблемы с функцией "maxCollatzUnder". Эта функция предназначена для (I) создания списка из двух кортежей (x,y) для каждого целого числа x в диапазоне от 1 до m (где m - аргумент функции) и где, где y представляет число Коллатца для целого числа x, а затем (II) просмотреть список для наибольшего числа Коллатца (то есть, у) и вернуть соответствующее ему целое число (то есть, х)

maxCollatzUnder n = foldl(\acc (i,j) -> if j > acc then i else acc) 0 
    (zip [1..n] ( map collatzLength [1..n]))
    where collatzLength n = length . collatz $ n

collatz n = map truncate $ collatzHelper n

collatzHelper 0 = [0]
collatzHelper 1 = [1]
collatzHelper n
    | (truncate n) `mod` 2 == 0 = [n] ++ collatzHelper (n/2)
    | otherwise = [n] ++ collatzHelper (3*n+1)

Я получаю следующую ошибку, когда я (пытаюсь) скомпилировать.

*Main> :l PE14Collatz.hs
[1 of 1] Compiling Main             ( PE14Collatz.hs, interpreted )

PE14Collatz.hs:7:89:
    No instance for (RealFrac Int)
      arising from a use of `collatzLength'
    In the first argument of `map', namely `collatzLength'
    In the second argument of `zip', namely
      `(map collatzLength [1 .. n])'
    In the third argument of `foldl', namely
      `(zip [1 .. n] (map collatzLength [1 .. n]))'
Failed, modules loaded: none.

Любопытно, что код компилируется и запускается правильно, если я изменю "maxCollatzUnder" на следующий код (см. Ниже). Единственное изменение заключается в том, что в приведенной ниже версии функция сгиба возвращает "j" (т. Е. Наибольшее число Коллатца) вместо "i" (т. Е. Целое число, которое генерирует наибольшее число Коллатца).

maxCollatzUnder n = foldl(\acc (i,j) -> if j > acc then j else acc) 0 
    (zip [1..n] ( map collatzLength [1..n]))
    where collatzLength n = length . collatz $ n

Приветствуются предложения по более эффективному / элегантному подходу, хотя мне все равно будет интересно понять причину этой ошибки.

Answer 1

Из-за вашего использования truncate (метод RealFrac) а также / (метод Fractional суперкласс RealFrac), Haskell выводит следующие два типа подписей для ваших последних двух функций:

collatz :: (RealFrac a, Integral b) => a -> [b]
collatzHelper :: RealFrac a => a -> [a]

Затем Хаскелл пытается определить тип maxCollatzUnder и его мыслительный процесс выглядит так:

• "В collatzLength n = length . collatz $ n проходим n в collatz поэтому аргумент collatzLength должен быть RealFrac ".

• "Поэтому в map collatzLength [1..n], [1..n] должен быть список RealFrac ценности."

• "Следовательно n в map collatzLength [1..n] должен быть RealFrac тип."

• "Следовательно n в zip [1..n] (что такое же n) должен быть RealFrac типа и так [1..n] это список RealFrac s ".

• "Следовательно i в (\acc (i,j) -> if j > acc then i else acc) должен быть RealFrac ".

• "Потому что вышеупомянутая лямбда может вернуться либо i или же acc, они должны быть одного типа. "

• "Так как j сравнивается с acc, j должен быть того же типа, что и acc - и, следовательно, того же типа, что и i и RealFrac ".

• "Но ждать- j это возвращаемое значение из collatzLength, который является возвращаемым значением вызова length и так должно быть Int но Int не в RealFrac ! "

• "ОШИБКА! ОШИБКА!"

Я должен идти (компилятор Кабал не любит, когда я выдаю их секреты), но самое короткое решение - не использовать truncate а также / и просто использовать div для (этажного) целочисленного деления.