Ocaml에서 목록을 병합하는 코드 오류

Question

안녕하세요 Ocaml에서 목록을 병합하려고합니다. 나는 내 초보자이다. 나의 실수가 바보 인 경우에 용서해주십시오.

예를 들어, 입력이 [[1]; [2; 3]; [4]]라면 나는 [1; 2; 3 ; 4].

는

내가 사용하려고 생각은 = [] 의사 코드는

func flatten(list, accumalator) 
    For each item from right to left in list 
    If Item is a scalar then n :: accumalator 
    Else fi Item is a list of form head :: tail then 
       head :: flatten (tail, accumalator). 

내가 이론적으로 생각 다음되는 accumaltor과 오른쪽 (사용 fold_right)에서 목록을 반복 처리를 다음과 같이 알고리즘은 정확하지만, 동의하지 않으면 알려주십시오. 이 알고리즘을 구현하는 내 OCaml의 코드에 이제

let rec flatten acc x = 
    match x with 
      n -> n :: acc 
     | [x] -> x :: acc 
     | head :: remainder -> 
      head :: (my_flat acc remainder) 
and my_flat = List.fold_right flatten 
;; 

my_flat [] [[1];[2;3];[4]] 

나는 다음과 같은 오류입니다 얻는 오류 :이 표현은 목록

에게 '표현하지만,이 유형 의 예상'를 입력있다

일치 문에서 마지막 패턴의 head :: (my_flat acc 나머지) 행을 읽는 중에 오류가 발생합니다.

도움이 되었습니까?

Answer 1

OCaml에서 목록의 모든 요소는 동일한 유형이어야합니다. 따라서 값 [1; [2; 3]; 4]은 모두 자체적으로 유효하지 않습니다. 여기에는 int 유형의 두 요소와 int list 유형의 요소가 포함됩니다. 본질적으로 해결해야 할 문제에 대한 진술은 불가능합니다.

$ ocaml312 
     Objective Caml version 3.12.0 

# [1; [2; 3]; 4];; 
Characters 4-10: 
    [1; [2; 3]; 4];; 
     ^^^^^^ 
Error: This expression has type 'a list 
     but an expression was expected of type int 

이 숙제 문제 같은 소리, 그래서 난 그냥 OCaml의에서 유효 목록에 자신을 제한하는 것은 해결하기 쉽게 만들 수 있습니다 말할 수 있습니다.

편집

확인, 문제는 지금 해결할 수 있습니다!

보고 된 유형 오류의 본질은 다음과 같습니다. 누적 된 결과가 acc (이 예에서는 int list)입니다. x (또한 int list 유형) 목록을 추가하려고합니다. x을 head (int) 및 remainder (int list)으로 분할했습니다. 보시다시피 은 my_flat 함수에 적합한 인수가 아닙니다. 그것은 int list list, 즉 int 목록의 목록을 원합니다. 실제로 재귀 호출은 flatten으로 가고 my_flat으로 가야합니다.

내가 보는 또 다른 문제 : List.fold_right의 인수는 함수, 목록 및 시작 값입니다. my_flat으로 전화를 걸면 나머지 두 개가 다른 순서로 제공됩니다. 빈 목록 []이 시작 값입니다.

나는 이것이 당신을 갈 수 있기를 희망한다. OCaml을 처음 사용하기 시작한 이래로 아마도 두 가지 문제가있을 것입니다.여기에 편집 2

는

가

함수 my_flat의 정돈 버전에 .... 당신은 여전히 ​​자신의 솔루션을 작업하는 경우 스포일러가 될 수있는 몇 가지 더 의견입니다 List.flatten이라는 OCaml 표준 라이브러리.

let rec flatten = function 
    [] -> [] 
    | l::r -> l @ flatten r 

나는이 매우 우아한 해결책 전화 싶지만, 불행히도 그것은 꼬리 재귀 아니다 : 그것은 구현보고 흥미 롭군요. 따라서 스택 공간의 일부 (선형)을 소비하고 매우 긴 목록에 대해 충돌 할 수도 있습니다.

여기 (토마스에 의해 언급 된 바와 같이) 꼬리 재귀 동작을 얻을 수있는 표준 FP 누적 트릭을 사용하여 동일한 아이디어를 기반으로 하나의 :

let flatten2 ll = 
    let rec go acc = function 
    | [] -> List.rev acc 
    | l :: r -> go (List.rev_append l acc) r 
in 
    go [] ll 

종종 그렇듯이, 꼬리 재귀 버전은 결과를 축적 역순으로 바꾸고 끝에서 뒤집습니다.

Answer 2

입력 값의 기본 경우를 분해하여 알고리즘을 직접 작성하여 시작할 수 있습니다. 즉, 입력 목록입니다 중 빈, 또는 입력 목록의 머리는 비어 있거나 입력리스트의 머리는 머리와 꼬리가 :이 코드가 아니기 때문에,

let rec flatten = function 
    | []   -> [] 
    | []  :: t -> flatten t 
    | (x::y) :: t -> x :: (flatten (y::t)) 

당신은 다음 기능을 최적화 할 수 있습니다 tail-recursive 따라서 목록이 너무 커지면 충돌이 발생합니다. 그래서 당신은 일반적인 기술을 사용하여이 작업을 다시 작성할 수 있습니다 :

let flatten list = 
    let rec aux accu = function 
    | []   -> accu 
    | []  :: t -> aux accu t 
    | (x::y) :: t -> aux (x::accu) (y::t) in 
    List.rev (aux [] list) 

그래서 내 조언이다

: 입력 유형에 따라 문제를 분해하여 시작하고 나중에 코드를 최적화하는 축전지를 사용합니다. 토마스에 의해 지적이 솔루션은 꼬리 재귀되지 않습니다 : 여기에 모든 당신의 도움 에 대한

Answer 3

덕분에 나는이 문제를

let flatten list = 
    let rec flatten_each acc x = 
     match x with 
       [] -> acc 
     | head :: remainder -> head :: (flatten_each acc remainder) 
in 
List.fold_right flatten_each (List.rev list) [] 
;; 

편집을 해결하는 데 사용되는 코드입니다. 꼬리 재귀 버전

나는 보조 기능이 누적됩니다이 하나,리스트의 목록의 첫 번째 요소 및 목록의 목록의 나머지를 좋아

let flatten list = 
    let rec flatten_each acc x = 
     match x with 
       [] -> acc 
      | head :: remainder -> (flatten_each (acc @ [head]) remainder) 
    in 
    List.fold_right flatten_each list [] 
;; 

Answer 4

이하, 그것은 나를 위해 명확 :

let flatten list = 
    let rec aux acc list1 list2 = 
    match list1 with 
     | x :: tail -> aux (x :: acc) tail list2 
     | [] -> 
     match list2 with 
      | [] -> List.rev acc 
      | x :: tail -> aux acc x tail 
    in 
    aux [] [] list