Max Wert eines Multiway Baum in OCaml

Question

Ich bin ein IT-Student Art von Neuling zu OCaml

Vor kurzem für eine Prüfung studieren ich diese Übung gefunden.

Gegeben: Typ 'ein Baum = Baum der' a * ‚eine Baumliste

eine Funktion mtree definieren: 'a tree ->' a, dass der größten Wert aller Knoten in einem Multiway zurück Baum, nach der üblichen Reihenfolge Beziehung in OCaml (< =)

Ich bin gekommen, um etwas wie das unten zu tun, was natürlich nicht funktioniert.

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;; 

Nachdem ich eine Antwort zu diesem gelesen habe, poste ich den örtlich festgelegten Code.

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);; 

Die Idee ist die gleiche, die Liste falten Sie die Knoten unter Verwendung meiner lokalen Funktion zu vergleichen, um zu tun, und der Baum durchlaufen, indem Sie die Funktion selbst über den Knoten Listen der aufeinander folgenden Ebenen aufrufen.

Funktioniert immer noch nicht. Jetzt beschwert sich Max_node im fold_left-Teil.

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

Und hier bin ich auf jeden Fall verloren, weil ich nicht sehen kann, warum es erwartet ‚ein Baum

Answer 1

Dieser Code zurückzukehren ist ziemlich glaubwürdig (IMHO). Das Wichtigste, was fehlt, ist, dass es Teilbäume der Teilbäume nicht durchläuft. Beachten Sie, dass Sie Ihre Funktion als rekursiv definieren (was sehr vernünftig ist), aber sie ruft sich nie selbst auf.

Ein weiteres Problem ist, dass die Problemanweisung einen "Wert" aus der Baumstruktur aufruft, aber Ihr Code einen ganzen Baumknoten zurückgibt.

Answer 2

Meine eigene Frage zu beantworten ist irgendwie lahm, aber mit den hier erhaltenen Hinweisen könnte ich es beenden Ich lasse meinen Code hier für jeden, der vor ähnlichen Problemen steht.

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)));;