Ninety-Nine F# Problems - Problems 70 - 73 - Multiway Trees

 1: /// These are F# solutions of Ninety-Nine Haskell Problems 
 2: /// (http://www.haskell.org/haskellwiki/H-99:_Ninety-Nine_Haskell_Problems), 
 3: /// which are themselves translations of Ninety-Nine Lisp Problems
 4: /// (http://www.ic.unicamp.br/~meidanis/courses/mc336/2006s2/funcional/L-99_Ninety-Nine_Lisp_Problems.html)
 5: /// and Ninety-Nine Prolog Problems
 6: /// (https://sites.google.com/site/prologsite/prolog-problems).
 7: ///
 8: /// If you would like to contribute a solution or fix any bugs, send 
 9: /// an email to paks at kitiara dot org with the subject "99 F# problems". 
10: /// I'll try to update the problem as soon as possible.
11: ///
12: /// The problems have different levels of difficulty. Those marked with a single asterisk (*) 
13: /// are easy. If you have successfully solved the preceeding problems you should be able to 
14: /// solve them within a few (say 15) minutes. Problems marked with two asterisks (**) are of 
15: /// intermediate difficulty. If you are a skilled F# programmer it shouldn't take you more than 
16: /// 30-90 minutes to solve them. Problems marked with three asterisks (***) are more difficult. 
17: /// You may need more time (i.e. a few hours or more) to find a good solution
18: ///
19: /// Though the problems number from 1 to 99, there are some gaps and some additions marked with 
20: /// letters. There are actually only 88 problems.
21: ///
22: /// 
23: /// A multiway tree is composed of a root element and a (possibly empty) set of successors which
24: /// are multiway trees themselves. A multiway tree is never empty. The set of successor trees is
25: /// sometimes called a forest.
26: ///  
27: ///                              (a)
28: ///                            /  |  \
29: ///                          (f) (c) (b)
30: ///                           |      /  \
31: ///                          (g)   (d)  (e)
32: /// 
33: /// Problem 70B 
34: /// 
35: /// (*) Check whether a given term represents a multiway tree. 
36: /// 
37: /// In Prolog or Lisp, one writes a predicate to check this. 
38: /// 
39: /// Example in Prolog: 
40: /// ?- istree(t(a,[t(f,[t(g,[])]),t(c,[]),t(b,[t(d,[]),t(e,[])])])).
41: /// Yes
42: ///  
43: /// In F#, we define multiway trees as a type.
44: /// 
45: type 'a Tree = Node of 'a  * 'a Tree list
46: ///         
47: /// Some example trees: 
48: /// 
49: let tree1 = Node ('a', [])
50: 
51: let tree2 = Node ('a', [Node ('b', [])])
52: 
53: let tree3 = Node ('a', [Node ('b', [Node ('c', [])])])
54: 
55: let tree4 = Node ('b', [Node ('d', []); Node ('e', [])])
56: 
57: let tree5 = Node ('a', [
58:                         Node ('f', [Node ('g', [])]);
59:                         Node ('c', []);
60:                         Node ('b', [Node ('d', []); Node ('e', [])])
61:                        ] )
62: 
63: /// The last is the tree illustrated above. 
64: /// 
65: /// 
66: /// (*) Problem 70B : Check whether a given term represents a multiway tree
67: /// As in problem 54A, all members of this type are multiway trees; there is no use for a 
68: /// predicate to test them.
69: /// 

(*) Problem 70C : Count the nodes of a multiway tree.

1: /// Example in F#: 
2: /// 
3: /// > nnodes tree2;;
4: /// val it : int = 2 
5: 
6: (Solution)

(**) Problem 70 : Tree construction from a node string.

 1: /// We suppose that the nodes of a multiway tree contain single characters. In the depth-first 
 2: /// order sequence of its nodes, a special character ^ has been inserted whenever, during the 
 3: /// tree traversal, the move is a backtrack to the previous level.
 4: ///  
 5: /// By this rule, the tree below (tree5) is represented as: afg^^c^bd^e^^^ 
 6: /// 
 7: /// 
 8: /// 
 9: /// Define the syntax of the string and write a predicate tree(String,Tree) to construct the 
10: /// Tree when the String is given. Make your predicate work in both directions.
11: ///
12: /// Example in F#: 
13: /// 
14: /// > string2Tree "afg^^c^bd^e^^^";;
15: /// val it : char Tree =
16: ///   Node
17: ///     ('a',
18: ///      [Node ('f',[Node ('g',[])]); Node ('c',[]);
19: ///       Node ('b',[Node ('d',[]); Node ('e',[])])])
20: /// > string2Tree "afg^^c^bd^e^^^" = tree5;;
21: /// val it : bool = true
22: 
23: (Solution)

(*) Problem 71 : Determine the internal path length of a tree.

 1: /// We define the internal path length of a multiway tree as the total sum of the path lengths
 2: /// from the root to all nodes of the tree. By this definition, tree5 has an internal path 
 3: /// length of 9.
 4: ///  
 5: /// Example in F#: 
 6: /// 
 7: /// > ipl tree5;;
 8: /// val it : int = 9
 9: /// > ipl tree4;;
10: /// val it : int = 2
11: 
12: (Solution)

(*) Problem 72 : Construct the bottom-up order sequence of the tree nodes.

 1: /// Write a predicate bottom_up(Tree,Seq) which constructs the bottom-up sequence of the nodes
 2: /// of the multiway tree Tree.
 3: ///  
 4: /// Example in F#: 
 5: /// 
 6: /// > bottom_up tree5;;
 7: /// val it : string = "gfcdeba"
 8: /// > bottom_up tree4;;
 9: /// val it : string = "deb"
10: 
11: (Solution)

(**) Problem 73 : Lisp-like tree representation.

 1: /// There is a particular notation for multiway trees in Lisp. Lisp is a prominent 
 2: /// functional programming language, which is used primarily for artificial intelligence 
 3: /// problems. As such it is one of the main competitors of Prolog. In Lisp almost everything
 4: /// is a list, just as in Prolog everything is a term.
 5: ///  
 6: /// The following pictures show how multiway tree structures are represented in Lisp.
 7: ///  
 8: ///    (a)        (a)        (a)        (b)            (a)
 9: ///                |          |        /   \         /  |  \
10: ///               (b)        (b)     (d)   (e)     (f)  (c)  (b)
11: ///                           |                     |       /   \
12: ///                          (c)                   (g)    (d)   (e)
13: ///
14: ///     a        (a b)    (a (b c))   (b d e)    (a (f g) c (b d e))
15: ///
16: /// Note that in the "lispy" notation a node with successors (children) in the tree is always
17: /// the first element in a list, followed by its children. The "lispy" representation of a 
18: /// multiway tree is a sequence of atoms and parentheses '(' and ')', which we shall 
19: /// collectively call "tokens". We can represent this sequence of tokens as a Prolog list; 
20: /// e.g. the lispy expression (a (b c)) could be represented as the Prolog list 
21: /// ['(', a, '(', b, c, ')', ')']. Write a predicate tree_ltl(T,LTL) which constructs the
22: /// "lispy token list" LTL if the tree is given as term T in the usual Prolog notation.
23: ///  
24: /// (The Prolog example given is incorrect.) 
25: /// 
26: /// Example in F#: 
27: /// 
28: /// > treeltl "(x (a (f g) c (b d e)))";;
29: /// val it : char list =
30: ///   ['('; 'x'; '('; 'a'; '('; 'f'; 'g'; ')'; 'c'; '('; 'b'; 'd'; 'e'; ')'; ')';
31: ///    ')']
32: ///
33: /// > displayList tree1;;
34: /// val it : string = "a"
35: /// > displayLisp tree2;;
36: /// val it : string = "(a b)"
37: /// > displayLisp tree3;;
38: /// val it : string = "(a (b c))"
39: /// > displayLisp tree4;;
40: /// val it : string = "(b d e)"
41: /// > displayLisp tree5;;
42: /// val it : string = "(a (f g) c (b d e))"
43: ///
44: /// > lisp2Tree "(a (f g) c (b d e))" = tree5;;
45: /// val it : bool = true
46: ///
47: /// As a second, even more interesting exercise try to rewrite tree_ltl/2 in a way that the
48: /// inverse conversion is also possible.
49: 
50: (Solution)