Haskell에 꼬리 재귀 최적화 기능이 있습니까?

Haskell에 꼬리 재귀 최적화 기능이 있습니까?

---

저는 오늘 유닉스에서 "time"명령을 발견했고 Haskell에서 tail-recursive와 normal recursive 함수 사이의 런타임 차이를 확인하는 데 사용할 것이라고 생각했습니다.

다음 기능을 작성했습니다.

--tail recursive
fac :: (Integral a) => a -> a
fac x = fac' x 1 where
    fac' 1 y = y
    fac' x y = fac' (x-1) (x*y) 

--normal recursive
facSlow :: (Integral a) => a -> a
facSlow 1 = 1
facSlow x = x * facSlow (x-1)

이것들은이 프로젝트에서만 사용하기위한 것이었기 때문에 0이나 음수를 확인하지 않았습니다.

그러나 각각에 대한 주요 메소드를 작성하고 컴파일하고 "time"명령으로 실행하면 둘 다 꼬리 재귀 함수를 제거하는 일반 재귀 함수 와 유사한 런타임을 가졌습니다 . 이것은 lisp의 tail-recursive 최적화와 관련하여들은 것과는 반대입니다. 그 이유는 무엇입니까?

---

Haskell은 지연 평가를 사용하여 재귀를 구현하므로 필요한 경우 값을 제공하겠다는 약속으로 모든 것을 처리합니다 (이를 썽크라고 함). 썽 크는 진행하는 데 필요한만큼만 줄어 듭니다. 이것은 수학적으로 표현을 단순화하는 방법과 유사하므로 그렇게 생각하는 것이 도움이됩니다. 평가 순서가 코드에 의해 지정 되지 않는다는 사실로 인해 컴파일러는 예전의 꼬리 호출 제거보다 훨씬 더 똑똑한 최적화를 수행 할 수 있습니다. 최적화를 원하면 컴파일하십시오 -O2!

facSlow 5사례 연구로 평가하는 방법을 살펴 보겠습니다 .

facSlow 5
5 * facSlow 4            -- Note that the `5-1` only got evaluated to 4
5 * (4 * facSlow 3)       -- because it has to be checked against 1 to see
5 * (4 * (3 * facSlow 2))  -- which definition of `facSlow` to apply.
5 * (4 * (3 * (2 * facSlow 1)))
5 * (4 * (3 * (2 * 1)))
5 * (4 * (3 * 2))
5 * (4 * 6)
5 * 24
120

따라서 걱정했던 것처럼 계산이 발생하기 전에 숫자가 쌓여 있지만 걱정하는 것과 달리facSlow 종료 대기중인 함수 호출 스택이 없습니다. 각 감소가 적용되고 사라지고 스택 프레임 이 그대로 유지됩니다. wake (즉, (*)엄격 하기 때문에 두 번째 인수의 평가를 트리거합니다).

Haskell의 재귀 함수는 매우 재귀적인 방식으로 평가되지 않습니다! 주위에 걸려있는 유일한 호출 스택은 곱셈 자체입니다. (*)가 엄격한 데이터 생성자로 간주되는 경우 보호 된 재귀라고합니다 (일반적으로 비 엄격 데이터 생성자 와 함께 언급되지만 추가 액세스에 의해 강제 될 경우 데이터 생성자가 데이터 생성자입니다).

이제 tail-recursive를 살펴 보겠습니다 fac 5.

fac 5
fac' 5 1
fac' 4 {5*1}       -- Note that the `5-1` only got evaluated to 4
fac' 3 {4*{5*1}}    -- because it has to be checked against 1 to see
fac' 2 {3*{4*{5*1}}} -- which definition of `fac'` to apply.
fac' 1 {2*{3*{4*{5*1}}}}
{2*{3*{4*{5*1}}}}        -- the thunk "{...}" 
(2*{3*{4*{5*1}}})        -- is retraced 
(2*(3*{4*{5*1}}))        -- to create
(2*(3*(4*{5*1})))        -- the computation
(2*(3*(4*(5*1))))        -- on the stack
(2*(3*(4*5)))
(2*(3*20))
(2*60)
120

So you can see how the tail recursion by itself hasn't saved you any time or space. Not only does it take more steps overall than facSlow 5, it also builds a nested thunk (shown here as {...}) - needing an extra space for it - which describes the future computation, the nested multiplications to be performed.

This thunk is then unraveled by traversing it to the bottom, recreating the computation on the stack. There is also a danger here of causing stack overflow with very long computations, for both versions.

If we want to hand-optimise this, all we need to do is make it strict. You could use the strict application operator $! to define

facSlim :: (Integral a) => a -> a
facSlim x = facS' x 1 where
    facS' 1 y = y
    facS' x y = facS' (x-1) $! (x*y) 

This forces facS' to be strict in its second argument. (It's already strict in its first argument because that has to be evaluated to decide which definition of facS' to apply.)

Sometimes strictness can help enormously, sometimes it's a big mistake because laziness is more efficient. Here it's a good idea:

facSlim 5
facS' 5 1
facS' 4 5 
facS' 3 20
facS' 2 60
facS' 1 120
120

Which is what you wanted to achieve I think.

Summary

• If you want to optimise your code, step one is to compile with -O2
• Tail recursion is only good when there's no thunk build-up, and adding strictness usually helps to prevent it, if and where appropriate. This happens when you're building a result that is needed later on all at once.
• Sometimes tail recursion is a bad plan and guarded recursion is a better fit, i.e. when the result you're building will be needed bit by bit, in portions. See this question about foldr and foldl for example, and test them against each other.

Try these two:

length $ foldl1 (++) $ replicate 1000 
    "The size of intermediate expressions is more important than tail recursion."
length $ foldr1 (++) $ replicate 1000 
    "The number of reductions performed is more important than tail recursion!!!"

foldl1 is tail recursive, whereas foldr1 performs guarded recursion so that the first item is immediately presented for further processing/access. _{(The first "parenthesizes" to the left at once, (...((s+s)+s)+...)+s, forcing its input list fully to its end and building a big thunk of future computation much sooner than its full results are needed; the second parenthesizes to the right gradually, s+(s+(...+(s+s)...)), consuming the input list bit by bit, so the whole thing is able to operate in constant space, with optimizations).}

You might need to adjust the number of zeros depending on what hardware you're using.

---

It should be mentioned that the fac function is not a good candidate for guarded recursion. Tail recursion is the way to go here. Due to laziness you are not getting the effect of TCO in your fac' function because the accumulator arguments keep building large thunks, which when evaluated will require a huge stack. To prevent this and get the desired effect of TCO you need to make these accumulator arguments strict.

{-# LANGUAGE BangPatterns #-}

fac :: (Integral a) => a -> a
fac x = fac' x 1 where
  fac' 1  y = y
  fac' x !y = fac' (x-1) (x*y)

If you compile using -O2 (or just -O) GHC will probably do this on its own in the strictness analysis phase.

---

You should check out the wiki article on tail recursion in Haskell. In particular, because of expression evaluation, the kind of recursion you want is guarded recursion. If you work out the details of what's going on under the hood (in the abstract machine for Haskell) you get the same kind of thing as with tail recursion in strict languages. Along with this, you have a uniform syntax for lazy functions (tail recursion will tie you to strict evaluation, whereas guarded recursion works more naturally).

(And in learning Haskell, the rest of those wiki pages are awesome, too!)

---

If I recall correctly, GHC automatically optimizes plain recursive functions into tail-recursive optimized ones.

참고URL : https://stackoverflow.com/questions/13042353/does-haskell-have-tail-recursive-optimization