홈>2020-03-18 11:51

f# - 꼬리 재귀 목록 추가를 어떻게 구현할 수 있습니까?

F #에서와 같은 간단한 추가 기능 :

let rec app s t =
   match s with
      | [] -> t
      | (x::ss) -> x :: (app ss t)

함수가 꼬리 재귀가 아니기 때문에 s가 커지면 충돌합니다. F #의 표준 추가 기능이 큰 목록과 충돌하지 않으므로 다르게 구현해야합니다. 그래서 나는 궁금해했다 : 꼬리 재귀 정의 추가는 어떻게 생겼습니까? 나는 다음과 같은 것을 생각해 냈다 :

let rec comb s t =
   match s with
      | [] -> t
      | (x::ss) -> comb ss (x::t)
let app2 s t = comb (List.rev s) t

작동하지만 다소 이상해 보입니다. 더 우아한 정의가 있습니까?

f#appendtail-recursion

답변 # 1

전통적 (꼬리 재귀 아님)

let rec append a b =
    match a, b with
    | [], ys -> ys
    | x::xs, ys -> x::append xs ys

어큐뮬레이터 사용 (테일 재귀)

let append2 a b =
    let rec loop acc = function
        | [] -> acc
        | x::xs -> loop (x::acc) xs
    loop b (List.rev a)

계속 (꼬리 재귀)

let append3 a b =
    let rec append = function
        | cont, [], ys -> cont ys
        | cont, x::xs, ys -> append ((fun acc -> cont (x::acc)), xs, ys)
    append(id, a, b)

비 테일 재귀 함수를 연속적으로 재귀로 변환하는 것은 매우 간단하지만 개인적으로는 간단한 가독성을 위해 누산기를 선호합니다.

답변 # 2
줄리엣이 게시 한 것 외에 :

시퀀스 표현식 사용
내부적으로 시퀀스 표현식은 꼬리 재귀 코드를 생성하므로 제대로 작동합니다.
```
let append xs ys = 
  [ yield! xs
    yield! ys ]
```
변경 가능한 .NET 유형 사용
David는 F # 목록이 변경 될 수 있다고 언급했지만 F # 코어 라이브러리로만 제한됩니다 (기능 개념을 위반하므로 사용자가 기능을 사용할 수 없음). 변경 가능한 .NET 데이터 유형을 사용하여 변경 기반 버전을 구현할 수 있습니다.
```
let append (xs:'a[]) (ys:'a[]) = 
  let ra = new ResizeArray<_>(xs)
  for y in ys do ra.Add(y)
  ra |> List.ofSeq
```
일부 시나리오에서는 유용 할 수 있지만 일반적으로 F # 코드에서 돌연변이는 피합니다.
답변 # 3
F # 소스를 한 눈에 보면 꼬리가 내부적으로 변경 가능한 것 같습니다. 간단한 해결책은 요소를 두 번째 목록에 맞추기 전에 첫 번째 목록을 뒤집는 것입니다. 그것은 목록을 뒤집는 것과 함께 꼬리를 재귀 적으로 구현하는 것이 쉽지 않습니다.

이전 javascript - URL에 원치 않는 느낌표가 표시되는 각도

다음 기본 유형을 둘러싼 C ++ 클래스 래퍼

Python2.net

f# - 꼬리 재귀 목록 추가를 어떻게 구현할 수 있습니까?