정수 목록을 F #의 트리로 변환

Question

저는 F #을 처음 사용했습니다. 간단한 정수 목록을 트리로 변환하는 방법을 알고 싶습니다.

let lst =[1;2;3;4] 
type Tree= 
|Leaf of int 
|Node Tree * Tree 

목록은이 ---> 같은 트리로 변환한다 잎 1, 노드 (잎 2), 노드 (노드 (잎 3 잎 4))

Answer 1

당신이 얻고 싶은 출력 귀하의 대답은 약간 형식이 잘못되었습니다,하지만 내 해석은 균형 이진 트리를 작성하려고한다는 것입니다. 이를 재귀 적으로 수행하려면 입력 목록을 두 개의 반으로 나눈 다음 왼쪽과 오른쪽 반에서 트리를 재귀 적으로 작성해야합니다.

기능 목록을 반으로 나누는 것이 그렇게 간단하지 않기 때문에 약간 까다 롭습니다. 실제로, 당신은 아마 배열로 데이터를 설정하고 그것을 사용하지만,이 기능 솔루션을 원하는 경우 사용할 수있는 수 :

type Tree = Leaf of int | Node of Tree * Tree 

let rec half marker acc xs = 
    match xs, marker with 
    | x::xs, _::_::marker -> half marker (x::acc) xs 
    | x::xs, _::[] -> List.rev (x::acc), xs 
    | xs, _ -> List.rev acc, xs 

half 함수의 트릭은 목록을 반복 실행하고 두를 유지한다는 것이다 목록 사본. 하나의 요소()에서 각 단계마다 두 개의 요소가 필요하므로이 목록이 비어있을 때까지 각 단계에서 요소 하나만 가져 오는 원래 목록의 중간에 도달했습니다.

이제 당신은 정확하게 당신이 얻고 자하는 결과 어떤 나무

let rec makeTree = function 
    | [] -> failwith "Does not work on empty lists" 
    | [x] -> Leaf x 
    | xs -> let l, r = half xs [] xs 
      Node(makeTree l, makeTree r)