이 F # 함수는 꼬리 재귀 적입니까? 여기서 재귀 함수가 함수 내에서 여러 번 호출됩니까?

Question

꼬리 재귀 함수에 대한 몇 가지 질문이 있습니다. this 및 this. 그러나 다음과 유사한 것을 찾을 수 없습니다.

필자가 알고있는 테일 콜 최적화 함수는 더 이상 평가하지 않고 마지막 호출에서 누적 값을 반환해야합니다. 계승 함수를 사용하여 이해하는 것은 꽤 쉽습니다. 예를 들어 루프 2에 최적화되어 있습니다. 그러나 다른 경우에 알려주는 것이 항상 명확하지는 않습니다. 다음에서 마지막 호출은 무엇입니까? 함수가 여러 번 재귀 적으로 몸체에 호출되기 때문에 많은 함수가 있습니다.

브라이언은 알아낼 수있는 방법을 제시하고 있지만 꼬리 호출 최적화 방법을 잘 모르겠습니다. 컴파일러에 --tailcalls 플래그를 전달하여 자동으로 처리 할 수 ​​있지만 항상 성공합니까?

f 및 g은 같은 유형을 반환합니다.

위의 코드를 최적화하여 꼬리말을 작성하면 도움이됩니다.

Answer 1

Jon이 이미 말했듯이 함수는 꼬리 재귀가 아닙니다. 기본 문제는 번을 번으로 재귀 적으로 호출해야한다는 것입니다 (에 전달 된 λ 함수에서 수행 된 xs 목록의 모든 요소에 대해 한 번).

실제로 여러 번의 재귀 호출을 수행해야하는 경우 연속 전달 스타일 또는 즉 필수 스택을 사용하는 것이 유일한 옵션 일 수 있습니다.연속체 뒤에있는 아이디어는 모든 함수가 결과가 사용 가능할 때 실행되어야하는 또 다른 함수 (마지막 인수로)를 취한다는 것입니다.

다음의 예 (오른쪽) 기반 정상 (왼쪽) 버전과 계속

let res = foo a b       fooCont a b (fun res -> 
printfn "Result: %d" res      printfn "Result: %d" res) 

연속 통과 스타일의 함수를 작성하는 방법을 보여줍니다, 당신은 계속 기반 사용해야합니다 fold 기능도 있습니다.

List.fold g acc (List.map (fun xxs -> myfunc f xxs) xs) 

가되다 : 먼저 fold의 람다 함수에 map에서 수행 작업을 이동하여 map를 사용하여 피할 수는 다음과 같이

List.fold (fun state xxs -> g state (myfunc f xxs)) acc xs 

그런 다음 코드를 다시 작성할 수 있습니다 (참고 모두 f 및 g은 질문에 표시되지 않았지만 이제는 연속 기반 함수이므로 계속을 나타내는 추가 인수가 사용됩니다.

,210

List.foldCont 기능은 fold의 연속 기반 버전이며, 다음과 같이 쓸 수있다 : 당신이 완전한 작업 예제를 게시하지 않았기 때문에

module List = 
    let rec foldCont f (state:'TState) (list:'T list) cont = 
    match list with 
    | [] -> cont state 
    | x::xs -> foldCont f state xs (fun state -> 
     f x state cont) 

, 내가 정말 코드를 테스트 할 수 있지만 내 생각 작동해야합니다.

Answer 2

나의 이해는 ... 기능에 최적화 된 꼬리 호출이 마지막 호출에 누적 값을 반환해야 함을 거의

입니다. 꼬리 재귀는 재귀 호출이 모두 꼬리 위치에 나타나는 경우입니다. 꼬리 위치는 호출자가 호출 수신자로부터 직접 결과를 반환 함을 의미합니다.

다음 마지막 호출은 무엇입니까?

꼬리 위치에 두 가지 호출이 있습니다. 먼저 f으로 전화하십시오. 둘째, List.fold으로 전화하십시오. 재귀 호출은 호출자가 반환 값을 직접 반환하지 않기 때문에 꼬리 위치에 있지 않습니다. 또한

if (List.isEmpty xs) then f x 

사용 패턴 대신 isEmpty 친구들의 일치.

위의 코드를 꼬리 - 호출 최적화에 도움을 주시면 감사하겠습니다.

사용자가 꼬리 재귀 버전을 작성하는 데 도움이 될 수 있으려면 작업 코드 나 적어도 사양을 게시해야합니다. 일반적으로 가장 간단한 솔루션은 연속성 전달 스타일 또는 명령형 스타일로 작성하는 것입니다.