INB4 много букв, если вы не сильно заинтересованы в теме, просто считайте, что fact2
потенциально лучше оптимизируется.
На самом деле, ответ на вопрос несколько сложнее чем может показаться на первый взгляд
Для начала перепишем функции в более удобном для дальнейших рассуждений виде (в.т.ч чтобы не возиться с некорректными аргументами, но больше для того, чтобы визуально сократить шаги подстановки)
fact1, fact2 :: Integer -> Integer
fact1 1 = 1
fact1 n = n * fact1 (n - 1)
fact2 = go 1
where
go acc 1 = acc
go acc n = go (acc * n) (n - 1)
Теперь несколько слов о том, как haskell осуществляет вычисление. Он постепенно сокращает выражение, заменяя в нем одно применение функции (или оператора) на тело этой функции (или оператора), подставляя фактические параметры.
Согласно ленивой модели вычисления, для подстановки он выбирает в первую очередь то подвыражение, без вычисления которого дальше продвинуться не получится. Вместо тысячи слов:
fact1 5
~> 5 * fact1 (5 - 1)
~> 5 * fact1 4
~> 5 * (4 * fact1 (4 - 1))
~> 5 * (4 * fact1 3)
~> 5 * (4 * (3 * fact1 (3 - 1)))
~> 5 * (4 * (3 * fact1 2))
~> 5 * (4 * (3 * (2 * fact1 (2 - 1))))
~> 5 * (4 * (3 * (2 * fact1 1)))
~> 5 * (4 * (3 * (2 * 1)))
~> 5 * (4 * (3 * 2))
~> 5 * (4 * 6)
~> 5 * 24
~> 120
Обратите внимание, что результат вычисления 5 - 1
нам необходим, чтобы выбрать дальнейший путь подстановки, но некоторые выражения могут оставаться невычисленными очень долго, занимая память и тратя время на их сохранение.
Большая часть времени тратится именно на это: выражение разрастается примерно до середины вычисления, и только потом начинает сокращаться, освобождая память.
А теперь для сравнения
fact2 5
~> go 1 5
~> go (1 * 5) (5 - 1)
~> go (1 * 5) 4
~> go ((1 * 5) * 4) (4 - 1)
~> go ((1 * 5) * 4) 3
~> go (((1 * 5) * 4) * 3) (3 - 1)
~> go (((1 * 5) * 4) * 3) 2
~> go ((((1 * 5) * 4) * 3) * 2) (2 - 1)
~> go ((((1 * 5) * 4) * 3) * 2) 1
~> (((1 * 5) * 4) * 3) * 2
~> ((5 * 4) * 3) * 2
~> (20 * 3) * 2
~> 60 * 2
~> 120
Чувствуете разницу? А? И я не чувствую, все так же плохо.
Вычисление выражения 1 * 5
не требуется для выбора следующего шага подстановки, поэтому оно остается не вычисленным.
Если скомпилировать оба примера без оптимизации, второй может оказаться даже медленнее первого, так в чем же его преимущество? Как раз в возможности оптимизации.
Если включить оптимизацию, процесс вычисления второго выражения пойдет по такому пути.
fact2 5
~> go 1 5
~> go (1 * 5) (5 - 1)
~> go 5 (5 - 1)
~> go 5 4
~> go (5 * 4) (4 - 1)
~> go 20 (4 - 1)
~> go 20 3
~> go (20 * 3) (3 - 1)
~> go 60 (3 - 1)
~> go 60 2
~> go (60 * 2) (2 - 1)
~> go 120 (2 - 1)
~> go 120 1
~> 120
Обратите внимание, хоть результат вычисления 1 * 5
нам в ближайшее время и не понадобится, компилятор все равно его выполнит, потому, что проанализировав функцию go
, поймет что она строгая.
Это значит, что переданный ей аргумент обязательно будет вычислен так или иначе в дальнейшем, а значит откладывать его вычисление на потом не выгодно.
Ленивые вычисления это дар и проклятье haskell, иногда приходится повозиться, чтобы убедить компилятор выполнить вычисления заранее, там где это правда будет быстрее, но компилятор этого не видит.
Например, можно переписать fact2
с использованием очевидно строгой версии функции go
, не дожидаясь милости компилятора
fact2 = go 1
where
go acc 1 = acc
go acc n = acc `seq` go (acc * n) (n - 1)
В таком случае даже без включенной оптимизации (в т.ч. оптимизации хвостовых вызовов) второе выражение будет вычислено значительно более эффективно.
ghci
не оптимизирует. Попробуйте запускатьghci -fobject-code -O
.