OCaml: disegna alberi binari

Question

Sto lavorando su alcuni programmi che usano alberi. Mi stavo chiedendo se c'è qualche pezzo di codice per disegnare alberi generali in OCaml.

type Tree = Node of Tree * int * Tree | Child of int;; 

Tutto ciò che trovo su Internet utilizza Caml Light, non Objective Caml.
Grazie in anticipo.

Answer 1

Potrebbe chiarire cosa si intende per "disegnare"? Immagino tu stia pensando a una visualizzazione grafica dell'albero?

Ho avuto una discreta esperienza con la generazione di descrizioni grafico/albero nel formato punto, utilizzato dallo strumento graphviz. L'idea è che il tuo programma OCaml generi una rappresentazione testuale del grafico in questo formato, quindi usi strumenti esterni per renderlo (trasformarlo in un'immagine), e possibilmente visualizzarlo sullo schermo.

Dot funziona per i grafici generali. Mentre puoi trovare strumenti specializzati per alberi binari che hanno più funzioni, nella mia esperienza funziona piuttosto bene con tutti i tipi di alberi e mostra qualcosa che di solito è ciò che desideri. Ora lo strumento non è privo di difetti e ho riscontrato dei bug (chiamando dot segfaults) in alcuni casi. Comunque penso che sia una scelta ragionevole.

Come stampare nel formato dot in modo concreto: selezionare qualsiasi example di un grafico già esistente, la struttura sarà abbastanza ovvia: è solo un formato testuale. Quindi scrivi il tuo codice in esecuzione sulla struttura del grafico, chiamando Printf con le cose giuste per le etichette, ecc., E voilà. Ad esempio, this example sembra buono e here è il formato di origine. Cito la parte pertinente:

/* courtesy Ian Darwin and Geoff Collyer, Softquad Inc. */ 
digraph unix { 
    size="6,6"; 
    node [color=lightblue2, style=filled]; 
    "5th Edition" -> "6th Edition"; 
    "5th Edition" -> "PWB 1.0"; 
    "6th Edition" -> "LSX"; 
    "6th Edition" -> "Interdata"; 
    "Interdata" -> "Unix/TS 3.0"; 
    "Interdata" -> "PWB 2.0"; 
    "Interdata" -> "7th Edition"; 
    "7th Edition" -> "8th Edition"; 
    "7th Edition" -> "32V"; 
    "7th Edition" -> "V7M"; 
    "V7M" -> "Ultrix-11"; 
    "8th Edition" -> "9th Edition"; 
    [...] 
} 

Answer 2

Di solito è molto facile e divertente da usare la libreria Graphics per disegnare il vostro albero, se è semplice e non troppo profonda.

Se si vuole una rappresentazione testuale:

type tree = Node of tree * int * tree | Child of int;; 
let draw tree = 
    let rec print indent tree = 
    match tree with 
     Child n -> 
     Printf.printf "%s%d\n" indent n 
    | Node (left, n, right) -> 
     Printf.printf "%s----\n" indent; 
     print (indent^"| ") left; 
     Printf.printf "%s%d\n" indent n; 
     print (indent^"| ") right; 
     Printf.printf "%s----\n" indent 
    in 
    print "" tree