Haskell beginner: «Нет экземпляра для ... возникающего из ...» error

Question

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

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

Я пытаюсь написать функцию («maxCollatzUnder»), которая при передаче целого числа «m» возвращает целое число (меньшее или равное m), которое имеет самую длинную последовательность Collatz (т. Е. Наибольшее число Collatz) , Например, maxCollatz 20 (т. Е. Какое целое число ниже (включительно) 20 имеет самую длинную последовательность коллажа?) Должно возвращать 19 (число 19 имеет последовательность Collatz длиной 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) создать список из 2-х кортежей (x, y) для каждого целого x в диапазоне от 1 до m (где m - аргумент функции) и где где y представляет число Collatz для целого 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» на следующий код (см. Ниже) Единственное изменение заключается в том, что в приведенной ниже версии функция fold возвращает «j» (т. Е. Самое большое число Collatz) вместо «i» (т. Е. Целое число, которое генерирует наибольшее число Collatz).

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] 

Haskell затем пытается вывести тип 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 с.»

• "Таким образом, 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! "

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

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