Нахождение последовательностей Коллатца ряда чисел

Question

Я новичок в Haskell и пытаюсь решить задачу Project Euler 14. Я еще не закончил программу, но часть, которую я выполнил, не работает.Предполагается, что этот фрагмент кода будет распечатывать длины последовательностей Коллатца чисел от 2 до 100.

main = print $ collatzSeq [] [2..100]

collatzSeq xs (x:s) = collatzSeq (collatzLength x []):xs s

collatzLength x y
    | x < 2 = length (x:y)
    | even x = collatzLength (x / 2) (x / 2):y
    | otherwise = collatzLength (3 * x + 1) (3 * x + 1):y

Я пытался изменить код различными способами, и я считаю, что проблема заключается вв функции collatzLength.Но из того, что я узнал о Haskell, эта функция должна работать, но это не так, и я не понимаю, чего мне не хватает.Я просто получаю сообщение об ошибке компиляции.

Answer 1

Ну, есть некоторые ошибки в вашем коде.Они - распространенная ошибка тех, кто плохо знаком с Хаскеллом.Я перечислю их, как показано ниже:

1. Функция приложения всегда будет иметь левую ассоциативность и наивысший приоритет по сравнению со всеми операторами.

Итак, код:

even x = collatzLength (x / 2) (x / 2):y

эквивалентен

even x = (collatzLength (x / 2) (x / 2)):y

Это явно неверно, поскольку второй аргумент collatzLength is [Int], а не Int

Функция (/) или оператор не могут применяться к типу Int или классу Num.

см. (/) применяется к типу данныхкоторый является экземпляром только Fractional, но Int нет.В вашем коде деление применяется только к четному числу, поэтому вместо него можно использовать quot как:

even x = collatzLength (x `quot` 2) ((x `quot` 2):y)

Отсутствует базовый регистр рекурсивной функции.

Как упомянул talex в комментарии, рекурсивная функция collatzSeq никогда не заканчивается.Так как он пропускает базовый случай, чтобы указать, как функция должна завершить свои вычисления.В вашем случае обычно проверяют, является ли список ввода пустым или нет:

collatzSeq xs []    = xs
collatzSeq xs (x:s) = collatzSeq ((collatzLength x []):xs) s

Наконец, лучше предоставить сигнатуру типа для функции, чтобы сделать код понятным и читаемым.

Соберите их все вместе, коррекция будет выглядеть так:

collatzSeq::[Int]->[Int]->[Int]
collatzSeq xs []    = xs
collatzSeq xs (x:s) = collatzSeq ((collatzLength x []):xs) s

collatzLength::Int->[Int]->Int
collatzLength x y
    | x < 2 = length (x:y)
    | even x = collatzLength (x `quot` 2) ((x `quot` 2):y)
    | otherwise = collatzLength (3 * x + 1) ((3 * x + 1):y)