4 people like it.

Like the snippet!

## 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: /// 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)

union case Tree.Node: 'a * 'a Tree list -> 'a Tree

type 'a Tree = | Node of 'a * 'a Tree list

Full name: Snippet.Tree<_>

type: 'a Tree

implements: System.IEquatable<'a Tree>

implements: System.Collections.IStructuralEquatable

implements: System.IComparable<'a Tree>

implements: System.IComparable

implements: System.Collections.IStructuralComparable

Full name: Snippet.Tree<_>

type: 'a Tree

implements: System.IEquatable<'a Tree>

implements: System.Collections.IStructuralEquatable

implements: System.IComparable<'a Tree>

implements: System.IComparable

implements: System.Collections.IStructuralComparable

*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.(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 'T list = List<'T>

Full name: Microsoft.FSharp.Collections.list<_>

type: 'T list

implements: System.Collections.IStructuralEquatable

implements: System.IComparable<List<'T>>

implements: System.IComparable

implements: System.Collections.IStructuralComparable

implements: System.Collections.Generic.IEnumerable<'T>

implements: System.Collections.IEnumerable

Full name: Microsoft.FSharp.Collections.list<_>

type: 'T list

implements: System.Collections.IStructuralEquatable

implements: System.IComparable<List<'T>>

implements: System.IComparable

implements: System.Collections.IStructuralComparable

implements: System.Collections.Generic.IEnumerable<'T>

implements: System.Collections.IEnumerable

val tree1 : char Tree

Full name: Snippet.tree1

type: char Tree

implements: System.IEquatable<char Tree>

implements: System.Collections.IStructuralEquatable

implements: System.IComparable<char Tree>

implements: System.IComparable

implements: System.Collections.IStructuralComparable

Full name: Snippet.tree1

type: char Tree

implements: System.IEquatable<char Tree>

implements: System.Collections.IStructuralEquatable

implements: System.IComparable<char Tree>

implements: System.IComparable

implements: System.Collections.IStructuralComparable

*Some example trees:*val tree2 : char Tree

Full name: Snippet.tree2

type: char Tree

implements: System.IEquatable<char Tree>

implements: System.Collections.IStructuralEquatable

implements: System.IComparable<char Tree>

implements: System.IComparable

implements: System.Collections.IStructuralComparable

Full name: Snippet.tree2

type: char Tree

implements: System.IEquatable<char Tree>

implements: System.Collections.IStructuralEquatable

implements: System.IComparable<char Tree>

implements: System.IComparable

implements: System.Collections.IStructuralComparable

val tree3 : char Tree

Full name: Snippet.tree3

type: char Tree

implements: System.IEquatable<char Tree>

implements: System.Collections.IStructuralEquatable

implements: System.IComparable<char Tree>

implements: System.IComparable

implements: System.Collections.IStructuralComparable

Full name: Snippet.tree3

type: char Tree

implements: System.IEquatable<char Tree>

implements: System.Collections.IStructuralEquatable

implements: System.IComparable<char Tree>

implements: System.IComparable

implements: System.Collections.IStructuralComparable

val tree4 : char Tree

Full name: Snippet.tree4

type: char Tree

implements: System.IEquatable<char Tree>

implements: System.Collections.IStructuralEquatable

implements: System.IComparable<char Tree>

implements: System.IComparable

implements: System.Collections.IStructuralComparable

Full name: Snippet.tree4

type: char Tree

implements: System.IEquatable<char Tree>

implements: System.Collections.IStructuralEquatable

implements: System.IComparable<char Tree>

implements: System.IComparable

implements: System.Collections.IStructuralComparable

val tree5 : char Tree

Full name: Snippet.tree5

type: char Tree

implements: System.IEquatable<char Tree>

implements: System.Collections.IStructuralEquatable

implements: System.IComparable<char Tree>

implements: System.IComparable

implements: System.Collections.IStructuralComparable

Full name: Snippet.tree5

type: char Tree

implements: System.IEquatable<char Tree>

implements: System.Collections.IStructuralEquatable

implements: System.IComparable<char Tree>

implements: System.IComparable

implements: System.Collections.IStructuralComparable

let rec nnodes = function

| Node (_, []) -> 1

| Node (_, xs) ->

let t = xs |> List.sumBy (nnodes)

1 + t

| 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 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 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 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 []

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 []

### More information

Link: |
http://fssnip.net/au |

Posted: |
3 years ago |

Author: |
Cesar Mendoza (website) |

Tags: |
Ninety-Nine F# Problems, tutorial, F#, trees |