OCaml-T9 예측 텍스트 구현에서 가장자리로 하위 트리 찾기

Question

저는 OCaml에 매우 익숙하며 T9 예측 텍스트 프로그램을 작성하는 일련의 함수를 구현하는 데 어려움을 겪고 있습니다. 예를 들어 내 단어가 "개"인 경우 - 정수 목록은 [3; 6; 4]가됩니다. 나는 이미 단어를 int리스트에 연관시키는 패턴 일치 함수를 가지고있다. 나는 가능한 단어에 번호를 매핑하는 데이터 유형 트라이을 사용하고있어 가능한 결과 :

type ('a, 'b) trie = Node of 'b list * ('a * ('a, 'b) trie) list

'는 입력의 단어 목록으로 표시 노드의

B 타입의 키 라벨 가장자리를 가진 트라이

매개 변수 trie와 가장자리 끝에 trie를 반환하는 가장자리 레이블이있는 함수를 작성해야합니다.

val trie_of_key : (’a, ’b) trie -> ’a -> (’a, ’b) trie = <fun>

어떻게 주어진 노드에 도달하기 위해 가장자리를 통과합니까? 함수형 프로그래밍은 여전히 ​​나에게 방향 감각을 잃어 버리기 때문에 예상되는 하위 트라이에 도달하는 데 필요한 재귀 단계가 확실하지 않습니다.

Answer 1

trie를 수정하고 싶지 않으면 함수 프로그래밍은 일반적인 기존 명령 프로그래밍과 동일합니다. 길을 따라 구조 조정을 수행하지 않는 조회 기능은 매우 간단해야합니다. 어쩌면 당신은 그 문제를 지나치게 생각하고 있을까요?

시도한 것을 보지 않고 더 말하기는 어렵습니다.

업데이트

여기에 단지 B-트리 구조 쓴 조회 기능입니다. 해결하려는 문제와 유사점이 있으므로 어쩌면 아이디어를 얻을 수 있습니다.

type ('a, 'b) btree = Node of ('a * 'b) list * ('a, 'b) btree list 

let rec lookup bt k = 
    match bt with 
    | Node ([], _) -> raise Not_found 
    | Node (keyvals, subtrees) -> 
     let rec look kvs sts = 
      match kvs with 
      | [] -> 
       lookup (List.hd sts) k (* Rightmost subtree *) 
      | (hdk, hdv) :: tlkv -> 
       if hdk = k then hdv 
       else if hdk < k then look tlkv (List.tl sts) 
       else lookup (List.hd sts) k 
     in 
     look keyvals subtrees 

나는 아무 키/값 쌍을 가진 노드에 하위 트리와 리프 노드임을 세부 사항은 중요하지만,주의 깊게 코드를 이해하려고 노력한다면, 그것은 불변 기반으로 생각하지 않는다 . 그렇지 않은 경우 노드에 n 개의 키/값 쌍이 있으면 정확히 n + 1 개의 하위 트리가 있습니다. 이 하위 트리는 비어있을 수 있습니다.