Max Valore di un albero a più vie in OCaml

Question

Sono uno studente IT e tipo di un novizio di OCaml

Recentemente, studiando per un esame che ho trovato questo esercizio.

Data: tipo 'un albero = Albero della' un * 'un elenco albero

definire una funzione mtree: 'un albero ->' una, che restituisce il valore più grande di tutti i nodi in un multiway albero, seguendo la consueta relazione di ordine in OCaml (< =)

Sono venuto a fare qualcosa di simile qui sotto, che, naturalmente, non funziona.

let rec mtree (Tree (r, sub)) = 
     let max_node (Tree(a, l1)) (Tree(b, l2)) = 
      if a >= b then (Tree(a, l1)) else (Tree(b, l2)) in 
     List.fold_left max_node r sub;; 

Dopo aver letto una risposta a questo sto postando il codice fisso.

let rec mtree (Tree(r,sub)) = 
    let max_node (Tree(a, l1)) (Tree(b, l2)) = 
     if a >= b then a else b in 
    List.fold_left (max_node) r (List.map mtree sub);; 

L'idea è la stessa, piegare la lista confrontando i nodi facendo uso della mia funzione locale di farlo e viaggiare attraverso l'albero chiamando la stessa funzione di sopra i nodi liste dei livelli consecutivi.

Tuttavia, non funziona ancora. Ora si lamenta di max_node nella parte fold_left.

Error: This expression has type 'a tree -> 'a tree -> 'a 
     but an expression was expected of type 'a tree -> 'a tree -> 'a tree 

E qui sto sicuramente perso perché non riesco a capire perché ci si aspetta di restituire un 'un albero

Answer 1

Questo codice è abbastanza credibile (IMHO). La cosa fondamentale è che non attraversa i sottoalberi dei sottoalberi. Nota che definisci la tua funzione come ricorsiva (che è molto ragionevole), ma non chiama mai se stessa.

Un altro problema da sottolineare è che l'istruzione del problema richiede un "valore" dall'albero, ma il codice restituisce un intero nodo dell'albero.

Answer 2

Rispondere alla mia domanda è una specie di zoppo, ma con i suggerimenti ricevuti qui potrei finirlo Qui sto lasciando il mio codice per chiunque abbia problemi simili.

let maxt (Tree(r,b)) = 
    let rec aux (Tree(r,b)) = 
     match b with 
     [] -> [r] 
     |l -> [r]@(List.fold_right (@) (List.map aux b) []) 
    in List.fold_left max r (aux (Tree(r,b)));;