; ********************** EXAMPLE PROGRAM IN 'MONICA' ************************

; first we define the new type 'BINary TREE'. such a tree is either empty
; or consists of a node carrying an item and having two branches carrying
; binary trees themselves:
;
;         node:X:Left:Right        X
;                                 / \
;                             Left   Right
; the type is 'polymorphic' because there are trees 
; carrying numbers: bintree(num) , lists of numbers: bintree(list(num)) 
; so the most general type of a binary tree is bintree(Alpha) where 
; Alpha is a 'type variable'
; 
; read this program into the monica interpreter by typing
; >> #consult("flp1_test_monica").   from the monica prompt '>>'
; this is of course a very sloooooooow program! 


? typedef [
     empty : bintree(Alpha),
     node  : (Alpha -> bintree(Alpha) -> bintree(Alpha) -> bintree(Alpha))
     ].

; insert: num -> bintree(num) -> bintree(num) takes a number and a tree
; as arguments and returns the tree with the number inserted at the 'right'
; place: smaller numbers down the left side, larger down the right.

? define [
     insert:N:empty => node:N:empty:empty,
     insert:N:(node:M:Left:Right) => 
           if N < M then node:M:(insert:N:Left):Right 
                 else
          (if M < N then node:M:Left:(insert:N:Right) 
                 else 
          node:N:Left:Right)
     ].      

; make tree makes an ordered tree out of a list:
; make_tree:[2,4,1,5,3] gives   2
;                              / \
;                             1   4
;                                / \
;                               3   5

? define [ make_tree:[] => empty,
         make_tree:[N|Ns] => insert:N:(make_tree:Ns)].


; wtree traverses a tree 'in order' and writes it down

? define [
     wtree:empty => true, 
     wtree:(node:X:Left:Right) =>  (wtree:Left) and #write(X) and (wtree:Right)
     ]. 

; >> write_in_order:[2,4,1,5,3] will write 12345 on your screen. 

? define [ write_in_order: List => wtree:(make_tree:List)].
