 5 people like it.

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

These are F# solutions of Ninety-Nine Haskell Problems which are themselves translations of Ninety-Nine Lisp Problems and Ninety-Nine Prolog Problems. The solutions are hidden so you can try to solve them yourself.

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

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

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

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

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

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

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

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

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

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

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

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

Full name: Script.Tree<_>

These are F# solutions of Ninety-Nine Haskell Problems
which are themselves translations of Ninety-Nine Lisp Problems
(http://www.ic.unicamp.br/~meidanis/courses/mc336/2006s2/funcional/L-99_Ninety-Nine_Lisp_Problems.html)
and Ninety-Nine Prolog Problems

If you would like to contribute a solution or fix any bugs, send
an email to paks at kitiara dot org with the subject "99 F# problems".
I'll try to update the problem as soon as possible.

The problems have different levels of difficulty. Those marked with a single asterisk (*)
are easy. If you have successfully solved the preceeding problems you should be able to
solve them within a few (say 15) minutes. Problems marked with two asterisks (**) are of
intermediate difficulty. If you are a skilled F# programmer it shouldn't take you more than
30-90 minutes to solve them. Problems marked with three asterisks (***) are more difficult.
You may need more time (i.e. a few hours or more) to find a good solution

Though the problems number from 1 to 99, there are some gaps and some additions marked with
letters. There are actually only 88 problems.

A multiway tree is composed of a root element and a (possibly empty) set of successors which
are multiway trees themselves. A multiway tree is never empty. The set of successor trees is
sometimes called a forest.

(a)
/ | \
(f) (c) (b)
| / \
(g) (d) (e)

Problem 70B

(*) Check whether a given term represents a multiway tree.

In Prolog or Lisp, one writes a predicate to check this.

Example in Prolog:
?- istree(t(a,[t(f,[t(g,[])]),t(c,[]),t(b,[t(d,[]),t(e,[])])])).
Yes

In F#, we define multiway trees as a type.

type 'T list = List<'T>

Full name: Microsoft.FSharp.Collections.list<_>
val tree1 : char Tree

Full name: Script.tree1

Some example trees:

val tree2 : char Tree

Full name: Script.tree2
val tree3 : char Tree

Full name: Script.tree3
val tree4 : char Tree

Full name: Script.tree4
val tree5 : char Tree

Full name: Script.tree5
let rec nnodes = function
| Node (_, []) -> 1
| Node (_, xs) ->
let t = xs |> List.sumBy (nnodes)
1 + t
let string2Tree str =
let chars = str |> List.ofSeq
let rec loop chars stack =
match chars with
| '^'::xs ->
match stack with
| [x] -> x
| tx::Node(y, ty)::stack' -> loop xs (Node(y, ty @ [tx])::stack')
| [] -> failwith "malformed text"
| x::xs -> loop xs (Node(x,[])::stack)
| [] -> failwith "malformed text"
loop chars []

let tree2String tree =
let rec loop tree =
match tree with
| Node(a, []) -> a.ToString() + "^"
| Node(a, xs) -> a.ToString() + (xs |> List.fold(fun acc x -> acc + loop x) "") + "^"
loop tree
let rec ipl tree =
let rec loop depth = function
| Node(a, []) -> depth
| Node(a, xs) -> depth + (xs |> List.sumBy( fun x -> loop (depth+1) x))
loop 0 tree
let bottom_up tree =
let rec loop = function
| Node(a, []) -> a.ToString()
| Node(a, xs) -> (xs |> List.fold( fun acc x -> acc + (loop x) ) "") + a.ToString()
loop tree
let treeltl str = str |> List.ofSeq |> List.filter((<>) ' ')

let displayLisp tree =
let rec loop = function
| Node(a, []) -> a.ToString()
| Node(a, xs) -> "(" + a.ToString() + (xs |> List.fold( fun acc x -> acc + " " + (loop x) ) "") + ")"
loop tree

let lisp2Tree str =
let tokens = treeltl str
let rec loop tokens stack =
match tokens with
| ')'::xs ->
match stack with
| [x] -> x
| tx::Node(y, ty)::stack' -> loop xs (Node(y, ty @ [tx])::stack')
| [] -> failwith "malformed text"
| '('::x::xs -> loop xs (Node(x,[])::stack)
| x::xs ->
match stack with
| [] -> loop xs [Node(x,[])]
| Node(y,t)::stack -> loop xs (Node(y,t @ [Node(x,[])])::stack)
| [] -> stack |> List.head
loop tokens []