F에서 색인 n으로 목록 잘라 내기

Question

n을 기준으로 목록을 잘라내는 재귀 함수를 작성하려고합니다. 그런 다음 2 목록을 반환합니다. 그래서 패스하면

cut(2, [5;10;4;2;7]);; 
    val it : int list * int list = ([5; 10], [4; 2; 7]) 

나는 그런 것을 얻고 싶습니다.

let rec cut (n, xs) = 
     match n, xs with 
     | 0, xt -> (n, xs) 
     | n, x::xt -> cut(n, xt), xs;; 

도와주세요.

let cut' (n, xs) = 
    Seq.take n xs, Seq.skip n xs 

재귀, 함수는과 같이 정의 할 수 있습니다 :

Answer 1

거 야 광고 @MisterMetaphors 재귀 함수에 대한 설명.

잘라 내기 함수는 재귀 적이 지 않지만 aux는 n에서부터 카운트 다운되고 잘라내 기 위해 전달 된리스트의 헤드에서 요소를 제거하여 작동합니다.

이렇게 잘라내는 말은 cut 2 [ 3; 4; 5; 7; 8 ]입니다. aux는 n, partition 1, partition 2의 세 가지 인수를 취하는 패턴 일치 함수입니다. 파티션 1은 빈 목록으로 시작하고 파티션 2는 cut에 전달 된 전체 목록으로 시작합니다.

첫 번째 aux가 두 번째 절과 일치하면 인수 (1, [3], [4; 5; 7; 8])가 호출됩니다. 다음 번에는 두 번째 절과 일치 할 것이고 이제는 (0, [4; 3], [5; 7; 8])로 자신을 호출합니다. 세 번째이자 마지막 절인 첫 번째 절 (n = 0)과 일치하고 xs와 ys를 포함하는 튜플을 반환합니다.

그러나 각 요소 앞에 conspend : :)를 사용했기 때문에 xs의 요소는 역순입니다. 이 이유는 왼쪽에 O (n) 인 추가 연산자 @와 비교하여 O (1) 연산이기 때문입니다.

xs가 역순이므로 함수의 마지막 표현식은 xs의 역전입니다.

대안 약간 짧은 정의

가 될 수있다 :

let cut n xs = 
    let rec aux = function 
     | 0, xs, ys -> List.rev xs, ys 
     | n, xs, y :: ys -> aux (n - 1, y :: xs, ys) 
     | _ -> failwith "invalid arguments" 
    aux (n, [], xs) 

Answer 2

이것이 달성하기 위해 목록이나 순서에 내장 된 기능을 결합하는 아마 더 나은

let cut (n, xs) = 
    let rec aux = function 
     | 0, xs, ys -> xs, ys 
     | n, xs, y :: ys -> aux (n - 1, y :: xs, ys) 
     | _ -> failwith "invalid arguments" 
    let l, r = aux (n, [], xs) 
    (List.rev l, r)