Ваша функция не является хвостовой рекурсией;он охраняется рекурсивноОднако защищенная рекурсия - это то, что вам следует использовать в Haskell, если вы хотите эффективно использовать память.
Чтобы вызов был хвостовым, его результат должен быть результатом всей функции.Это определение применяется как к рекурсивным, так и к нерекурсивным вызовам.
Например, в коде
f x y z = (x ++ y) ++ z
вызов (x ++ y) ++ z является хвостовым вызовом, поскольку его результат является результатом всей функции.Вызов x ++ y является , а не хвостовым вызовом.
В качестве примера хвостовой рекурсии рассмотрим foldl:
foldl :: (b -> a -> b) -> b -> [a] -> b
foldl _ acc [] = acc
foldl f acc (x:xs) = foldl f (f acc x) xs
Рекурсивный вызов foldl f (f acc x) xs является хвостово-рекурсивным вызовом, потому что его результат является результатом всей функции.
Рекурсивные вызовы в вашем коде
merge2 (x:xs)(y:ys) = if y < x then y: merge2 (x:xs) ys else x :merge2 xs (y:ys)
не являются хвостово-рекурсивными, потому что они не даютрезультат всей функции.После вызова merge2 вы берете результат и используете его для создания нового списка.Конструктор (:), а не рекурсивный вызов, дает результат всей функции.
Однако хвостовая рекурсия не гарантирует эффективность пространства в ленивом языке.При ленивой оценке Haskell создает thunks или структуры в памяти, которые представляют код, который еще предстоит оценить.Рассмотрим оценку следующего кода:
foldl f 0 (1:2:3:[])
=> foldl f (f 0 1) (2:3:[])
=> foldl f (f (f 0 1) 2) (3:[])
=> foldl f (f (f (f 0 1) 2) 3) []
=> f (f (f 0 1) 2) 3
Вы можете считать ленивую оценку происходящей «вовне».Когда рекурсивные вызовы foldl оценены, в аккумуляторе накапливаются громоотводы.Таким образом, хвостовая рекурсия с аккумуляторами неэффективна с точки зрения пространства в ленивом языке из-за отложенной оценки.
Вместо хвостовой рекурсии следует пытаться использовать защищенную рекурсию, где рекурсивный вызов скрыт внутри конструктора данных.При ленивой оценке выражения оцениваются до тех пор, пока они не будут в нормальной форме слабой головы (WHNF).Выражение находится в WHNF, если оно либо:
- Конструктор данных, примененный к аргументам (например,
Just (1 + 1)) - Частично примененная функция (например,
const 2) - Лямбда-выражение (например,
\x -> x)
Рассмотрим map:
map :: (a -> b) -> [a] -> [b]
map _ [] = []
map f (x:xs) = f x : map f xs
map (+1) (1:2:3:[])
=> (+1) 1 : map (+1) (2:3:[])
Выражение (+1) 1 : map (+1) (2:3:[]) в WHNF из-за данных (:)конструктор, и, следовательно, оценка останавливается на этом этапе.Ваша функция merge2 также использует защищенную рекурсию, поэтому она также экономит место на ленивом языке.
TL; DR: на ленивом языке хвостовая рекурсия все еще может занимать память, если она формирует thunksв аккумуляторе, пока защищенная рекурсия не накапливает гром.
Полезные ссылки: