이 재귀 함수를 꼬리 재귀로 변환하는 힌트 (코드 아님)가 필요합니까?

Question

문자열 및 문자열 목록의 목록을 가져온 다음 전달 된 문자열은 있지만 전달 된 문자열은 포함하지 않은 각 목록의 모든 요소 목록을 반환하는이 함수가 있습니다. 당신은 재귀 함수가 볼 수 있고 내가 꼬리 재귀 함수로 변환 원하는

fun myfilter(list : string list list, s : string) = 
case list of 
    [] => [] 
    |xs::xs' => case all_except_option(s, xs) of (* helper function that does it for a string and a list of strings *) 
        NONE => [] 
        |SOME n => if n = xs 
          then myfilter(xs',s) 
          else n@myfilter(xs',s) 

myfilter([["a","b"],["c","d"],["e","a","x"]], "a") -> ["b","e","x"]

지금이다. 나는 꼬리 재귀의 예를 잘 알고 있지만 위 함수에서 어떻게 할 수 있는지보고 싶지 않다.

Answer 1

꼬리 재귀라고 생각할 때, 다음 것은 "accumulator"라고 생각한다.

함수가 꼬리 재귀가 아닌 이유는 어떤 결과를 얻기 위해 함수 자체를 호출해야하기 때문이며 다음에은 그 결과로 어떤 작업을 수행합니다. 계산을 재귀 호출로 옮길 수 있다면 꼬리 재귀입니다.

이 경우 계산은 두 개의 목록을 함께 사용하는 것입니다. 따라서 솔루션은 let ... in ... end 내부에 선언 된 함수이며 누산기 인 세 번째 매개 변수를 사용합니다. 그런 다음 누적기에 항목을 추가 할 수 있습니다.

좋은 예는 꼬리 재귀 계승 함수입니다. 여기에 일반 계승 함수는 다음과 같습니다

fun fact 0 = 1 
    | fact x = x * fact (x-1) 

은 꼬리 재귀, 우리가 축적 소요 로컬 함수를 정의 할 수 있도록하고, 거기에 곱셈을 수행하려면.

fun fact x = 
let 
    fun fact' 0 acc = acc 
    | fact' x acc = fact (x-1) (x*acc) 
in 
    fact' x 1 
end 

1을 곱하면 아무런 효과가 없으므로 누산기의 시작 값으로 1을 사용합니다.

그래, 그 외에도 코드를 개선하기 위해 할 수있는 일이 조금 있습니다. 나는 이렇게 여기에 많은 사람들이 나타났습니다 :

fun foo xs = 
case xs of 
    []  => ... 
    | (x::xs) => ... 

훨씬 더 좋은 것 어디 그냥 수행

당신은 다음과 같이, 하나, "힌트"를 얻을 생각하지 않을

fun foo []  = ... 
    | foo (x::xs) = ...