Я хотел бы отметить важное различие:
cyclic' = [0,1] ++ cyclic'
cyclic'' = [0,1] ++ x
where x = cyclic''
Эти две функции рекурсивны в том смысле, что определение ссылок самой функции. Но
cyclic = let x = 0 : y
y = 1 : x
in x
нет! Он использует x внутренне, что является рекурсивным, но целого cyclic нет - в его определении нет ссылки на себя. Именно поэтому они отличаются друг от друга при компиляции на основной язык.
Это имеет некоторые важные практические последствия, а именно, что рекурсивные функции не могут быть inlined, но не рекурсивные могут. Вот почему вы часто видите определения как
fix :: (a -> a) -> a
fix f = let x = f x in x
(от source из Data.Function) вместо более прямой
fix f = f (fix f)
(я не совсем уверен, почему GHC не делает это автоматически.)
Просто для полноты картины, есть и другие короткие пути, как определить cyclic:
-- recursive:
cyclic = 0 : 1 : cyclic
-- non-recursive:
cyclic = let x = 0 : 1 : x in x
cyclic = cycle [0,1]
cyclic = fix ([0,1] ++)
Update: Приведем пример: Давайте определим
-- The `const` combinator, defined explicitly so that
-- it gets inlined.
k :: a -> b -> a
k x y = x
fix, fix' :: (a -> a) -> a
fix f = let x = f x in x
fix' f = f (fix' f)
main = do
print $ fix (k 1)
print $ fix' (k 2)
Так fix' рекурсивно, а fix не является (определение fix копируется из Data.Function). Что происходит, когда мы используем fix'? Компилятор не может встроить его, потому что после вложения он снова получит выражение, которое содержит fix'. Должен ли он включить его во второй раз? А потом в третий раз? Поэтому рекурсивные функции никогда не создаются по дизайну. С другой стороны, fix не является рекурсивным, поэтому fix (k 1) вставляется в let x = k 1 x in x. Затем компилятор строит k, что приводит к let x = 1 in x, который заменяется просто на 1.
Мы можем проверить выше требование сбросов скомпилированного кода на языке ядра:
$ ghc -ddump-simpl -dsuppress-all Main.hs
[1 of 1] Compiling Main (Main.hs, Main.o)
==================== Tidy Core ====================
Result size of Tidy Core = {terms: 24, types: 27, coercions: 0}
Rec {
fix'_reJ
fix'_reJ = \ @ a_c f_aeR -> f_aeR (fix'_reJ f_aeR)
end Rec }
main
main =
>>
$fMonadIO
($ (print $fShowInteger) (__integer 1))
($ (print $fShowInteger)
(fix'_reJ
(let {
x_aeN
x_aeN = __integer 2 } in
\ _ -> x_aeN)))
main
main = runMainIO main
В то время как я нахожусь в этом, позвольте мне добавить еще одну версию: 'cyclic3 = let x = [0,1] ++ yy = x in x' – sitiposit
Вы можете создавать бесконечные списки с функциями 'Data.List' 'repeat' и' cycle' – viorior