Факториальная реализация Haskell

Здравствуйте, у меня есть небольшой вопрос в haskell.
Я реализовал факториал, как показано ниже.

factorial n = n * factorial(n-1)
factorial 0 = 1

К сожалению, в приведенном выше коде возникает ошибка " C stack overflow ".
Потом я изменил код жизни вот так.

factorial 0 = 1
factorial n = n * factorial(n-1)

И, наконец, это удалось.
Может ли кто-нибудь сообщить мне разницу между первым кодом и вторым кодом?

Всего 2 ответа


Вы предоставили два кейса:

factorial n = n * factorial (n - 1)
factorial 0 = 0

Когда вы пробуете factorial 0, Haskell попытается сопоставить 0 с каждым из ваших двух случаев, начиная с верхнего регистра. Поскольку регистр n соответствует 0 (и фактически соответствует абсолютно чему угодно), вы всегда будете использовать верхнюю строку, и это будет выглядеть так, как если бы вы только написали

factorial n = n * factorial (n - 1)

С другой стороны, если вы измените порядок, Haskell сначала попытается сопоставить 0 с 0 и, таким образом, вызовет случай factorial 0 = 1.


Сопоставление с шаблоном с использованием n в первом определении заменяет литерал 0 во втором шаблоне. Haskell будет соответствовать по порядку. Поскольку n соответствует любому номеру (включая 0), вы никогда не доберетесь до этого базового случая 0.

Второе определение устраняет эту ошибку.


Есть идеи?

10000