Drucken eines Trie in Ocaml

Question

Jede der unten aufgeführten Funktionen funktioniert wie erwartet. (Mit Ausnahme des letzten)

Ich versuche, die to_list Arbeit zu machen, ich will es ein list von char lists zurückzukehren, aber ich bisher habe ich es geschafft nur zu ihrer Umsetzung mit einfachen prints Rückkehr unit

type trie = Trie of bool * (char * trie) list 
let empty = Trie (false, []) 

let explode wd = (*breaks up a word in a list of chars*) 
    let rec exp i acc = 
     if i = -1 then acc else exp (i-1) (wd.[i]::acc) in 
     exp (String.length wd - 1) [] 

let insert tr wd = (*insert a word into the trie*) 
let rec insert' wd tr = match wd, tr with 
    | [], Trie (_, l) -> Trie (true, l) 
    | wh::wt, Trie (b, l) -> 
     try Trie(b, (wh, insert' wt (List.assoc wh l))::List.remove_assoc wh l) 
     with Not_found -> Trie (b, (wh, insert' wt empty) :: l) 
     in insert' (explode wd) tr 

let from_list = List.fold_left insert empty (*makes trie from string list*) 

let to_list tr = (*prints all trie words*) 
    let rec to_list' (Trie (b, l)) acc = 
     if b then 
      (
       List.iter print_char (List.rev acc); 
       print_char '\n' 
      ) 
     else(); 
     List.iter (fun (c, t) -> to_list' t (c::acc)) l in 
    to_list' tr [] 

EDIT: Dank @Goswin von Brederlow habe ich meine to_list Druckfunktion übersichtlicher gemacht.

Was ich versucht:

let to_list tr = (*fails at compile time*) 
    let rec to_list' acc = function 
     | Trie(_, []) -> [List.rev acc] 
     | Trie(true, (c, h)::_) -> (List.rev acc) :: to_list' (c::acc) h 
     | Trie(_, l) -> List.map (fun (c, t) -> to_list' (c::acc) t) in 
     to_list' [] a tr 

Beispiel:

let t = from_list ["hello"; "hell"; "helsinki"; "here"];; 
# to_list t;; 
here 
helsinki 
hell 
hello 
- : unit =() 

Hat scheitern, weil List.map nur 'a list und nicht n-depth nested lists zurückkehren geben?

Answer 1

Es gibt zwei vernünftige Möglichkeiten, dies zu tun: map eine Liste von Listen zurückgeben und dann abflachen, oder einen Akku zu fädeln. Ich gebe die zweite, da es effizienter und nicht viel komplizierter ist:

let to_list trie = 
    let rec recur acc chars (Trie (word_here, entries)) = 
    let acc = 
     match entries with 
     | [] -> acc 
     | _ -> 
     List.fold_left (fun acc (char, trie) -> 
      recur acc (char::chars) trie) 
      acc entries in 
    if word_here then List.rev chars::acc 
    else acc in 
    recur [] [] trie 

Answer 2

List.map kann eine Liste von Listen zurückgeben. Das ist nicht dein Problem.

Sie sagen, dass Ihre to_list Funktion nicht kompiliert, aber Sie zeigen den Fehler nicht an. Dies macht es schwieriger, Beratung anzubieten. diese

Das erste Problem, das ich in dem Code zu sehen ist:

List.map (fun (c, t) -> to_list' (c::acc) t) 

Es gibt nur ein Argument hier. Aber im Allgemeinen würden Sie zwei Argumente liefern wollen: eine Funktion (was Sie haben) und eine Liste (die Sie nicht haben).