В Хаскеле производительность и где обязательна

Question

Я только изучаю Haskell и написал две программы с учебного сайта, так что

maximumnowhere :: (Ord a) => [a] -> a
maximumnowhere [] = error "empty"
maximumnowhere [x] = x
maximumnowhere (x:xs) = if x > maximumnowhere xs then x else maximumnowhere xs

и

maximumwhere :: (Ord a) => [a] -> a
maximumwhere [] = error "empty"
maximumwhere [x] = x
maximumwhere (x:xs) = if x > maximum' then x else maximum' where maximum' = maximumwhere xs

Я думал, что эти две программы довольно эквивалентны, потому что я думалПривязка where заменяет переменную только ее содержимым.но когда я запускаю его в ghci, первый был намного медленнее последнего, особенно для массива с длиной более 25. Вероятно, привязка where делает эту огромную разницу в производительности, но я не знаю почему.Кто-нибудь может объяснить это для меня?

Answer 1

Нет, они не эквивалентны. let и where вводят совместное использование , что означает, что значение оценивается только один раз. Компилятор, как правило, не поделится результатом двух идентичных выражений, если вы сами не скажете ему об этом, потому что он, как правило, не может сам по себе сказать, выгоден ли компромисс между пространственно-временными действиями или нет.

Таким образом, ваша первая программа будет делать два рекурсивных вызова за одну итерацию, делая ее O (2 ^ n) , в то время как вторая делает только один на одну итерацию, то есть O (n) . Разница между ними огромна. При n = 25 первая программа приводит к более чем 33 миллионам рекурсивных вызовов, а вторая - только 25.

Итак, мораль этой истории в том, что если вы хотите поделиться, вы должны попросить об этом, используя let или where.