Personal tools

99 questions/61 to 69

From HaskellWiki

< 99 questions(Difference between revisions)
Jump to: navigation, search
m (solution 61)
(Problem 63)
 
(31 intermediate revisions by 9 users not shown)
Line 1: Line 1:
 
__NOTOC__
 
__NOTOC__
   
These are Haskell translations of [http://www.ic.unicamp.br/~meidanis/courses/mc336/2006s2/funcional/L-99_Ninety-Nine_Lisp_Problems.html Ninety Nine Lisp Problems].
+
This is part of [[H-99:_Ninety-Nine_Haskell_Problems|Ninety-Nine Haskell Problems]], based on [https://prof.ti.bfh.ch/hew1/informatik3/prolog/p-99/ Ninety-Nine Prolog Problems].
   
If you want to work on one of these, put your name in the block so we know someone's working on it. Then, change n in your block to the appropriate problem number, and fill in the <Problem description>,<example in lisp>,<example in Haskell>,<solution in haskell> and <description of implementation> fields.
+
== Binary trees ==
  +
  +
As defined in problem 54A.
  +
  +
An example tree:
  +
<haskell>
  +
tree4 = Branch 1 (Branch 2 Empty (Branch 4 Empty Empty))
  +
(Branch 2 Empty Empty)
  +
</haskell>
   
 
 
== Problem 61 ==
 
== Problem 61 ==
   
Line 12: Line 11:
 
A leaf is a node with no successors. Write a predicate count_leaves/2 to count them.
 
A leaf is a node with no successors. Write a predicate count_leaves/2 to count them.
   
<pre>
 
 
Example:
 
Example:
  +
  +
<pre>
 
% count_leaves(T,N) :- the binary tree T has N leaves
 
% count_leaves(T,N) :- the binary tree T has N leaves
  +
</pre>
   
 
Example in Haskell:
 
Example in Haskell:
> count_leaves (Branch 1 (Branch 2 Nil (Branch 4 Nil Nil)) (Branch 2 Nil Nil))
 
2
 
</pre>
 
   
Solution:
 
 
<haskell>
 
<haskell>
data Tree a = Nil | Branch a (Tree a) (Tree a)
+
> countLeaves tree4
+
2
count_leaves Nil = 0
 
count_leaves (Branch a Nil Nil) = 1
 
count_leaves (Branch a left right) = count_leaves left + count_leaves right
 
 
</haskell>
 
</haskell>
+
  +
[[99 questions/Solutions/61 | Solutions]]
  +
 
== Problem 61A ==
 
== Problem 61A ==
   
<Problem description>
+
Collect the leaves of a binary tree in a list
  +
  +
A leaf is a node with no successors. Write a predicate leaves/2 to collect them in a list.
   
<pre>
 
 
Example:
 
Example:
<example in lisp>
 
   
Example in Haskell:
+
<pre>
<example in Haskell>
+
% leaves(T,S) :- S is the list of all leaves of the binary tree T
 
</pre>
 
</pre>
   
Solution:
+
Example in Haskell:
  +
 
<haskell>
 
<haskell>
<solution in haskell>
+
> leaves tree4
  +
[4,2]
 
</haskell>
 
</haskell>
   
<description of implementation>
+
[[99 questions/Solutions/61A | Solutions]]
+
 
== Problem 62 ==
 
== Problem 62 ==
   
<Problem description>
+
Collect the internal nodes of a binary tree in a list
  +
  +
An internal node of a binary tree has either one or two non-empty successors. Write a predicate internals/2 to collect them in a list.
   
<pre>
 
 
Example:
 
Example:
<example in lisp>
 
   
Example in Haskell:
+
<pre>
<example in Haskell>
+
% internals(T,S) :- S is the list of internal nodes of the binary tree T.
 
</pre>
 
</pre>
   
Solution:
+
Example in Haskell:
  +
 
<haskell>
 
<haskell>
<solution in haskell>
+
Prelude>internals tree4
  +
Prelude>[1,2]
 
</haskell>
 
</haskell>
   
<description of implementation>
+
[[99 questions/Solutions/62 | Solutions]]
+
  +
 
== Problem 62B ==
 
== Problem 62B ==
   
<Problem description>
+
Collect the nodes at a given level in a list
  +
  +
A node of a binary tree is at level N if the path from the root to the node has length N-1. The root node is at level 1. Write a predicate atlevel/3 to collect all nodes at a given level in a list.
   
<pre>
 
 
Example:
 
Example:
<example in lisp>
 
   
Example in Haskell:
+
<pre>
<example in Haskell>
+
% atlevel(T,L,S) :- S is the list of nodes of the binary tree T at level L
 
</pre>
 
</pre>
   
Solution:
+
Example in Haskell:
  +
 
<haskell>
 
<haskell>
<solution in haskell>
+
Prelude>atLevel tree4 2
  +
Prelude>[2,2]
 
</haskell>
 
</haskell>
   
<description of implementation>
+
[[99 questions/Solutions/62B | Solutions]]
+
 
== Problem 63 ==
 
== Problem 63 ==
   
<Problem description>
+
Construct a complete binary tree
  +
  +
A complete binary tree with height H is defined as follows:
  +
* The levels 1,2,3,...,H-1 contain the maximum number of nodes (i.e 2**(i-1) at the level i)
  +
* In level H, which may contain less than the maximum possible number of nodes, all the nodes are "left-adjusted". This means that in a levelorder tree traversal all internal nodes come first, the leaves come second, and empty successors (the nil's which are not really nodes!) come last.
  +
  +
Particularly, complete binary trees are used as data structures (or addressing schemes) for heaps.
  +
  +
We can assign an address number to each node in a complete binary tree by enumerating the nodes in level-order, starting at the root with number 1. For every node X with address A the following property holds: The address of X's left and right successors are 2*A and 2*A+1, respectively, if they exist. This fact can be used to elegantly construct a complete binary tree structure.
  +
  +
Write a predicate complete_binary_tree/2.
   
<pre>
 
 
Example:
 
Example:
<example in lisp>
 
   
Example in Haskell:
+
<pre>
<example in Haskell>
+
% complete_binary_tree(N,T) :- T is a complete binary tree with N nodes.
 
</pre>
 
</pre>
   
Solution:
+
Example in Haskell:
  +
 
<haskell>
 
<haskell>
<solution in haskell>
+
Main> completeBinaryTree 4
  +
Branch 'x' (Branch 'x' (Branch 'x' Empty Empty) Empty) (Branch 'x' Empty Empty)
  +
  +
Main> isCompleteBinaryTree $ Branch 'x' (Branch 'x' Empty Empty) (Branch 'x' Empty Empty)
  +
True
 
</haskell>
 
</haskell>
   
<description of implementation>
+
[[99 questions/Solutions/63 | Solutions]]
+
 
== Problem 64 ==
 
== Problem 64 ==
   
<Problem description>
+
Given a binary tree as the usual Prolog term t(X,L,R) (or nil). As a preparation for drawing the tree, a layout algorithm is required to determine the position of each node in a rectangular grid. Several layout methods are conceivable, one of them is shown in the illustration below:
   
<pre>
+
https://prof.ti.bfh.ch/hew1/informatik3/prolog/p-99/p64.gif
Example:
+
<example in lisp>
+
In this layout strategy, the position of a node v is obtained by the following two rules:
  +
* x(v) is equal to the position of the node v in the inorder sequence
  +
* y(v) is equal to the depth of the node v in the tree
  +
Write a function to annotate each node of the tree with a position, where (1,1) in the top left corner or the rectangle bounding the drawn tree.
  +
  +
Here is the example tree from the above illustration:
  +
  +
<haskell>
  +
tree64 = Branch 'n'
  +
(Branch 'k'
  +
(Branch 'c'
  +
(Branch 'a' Empty Empty)
  +
(Branch 'h'
  +
(Branch 'g'
  +
(Branch 'e' Empty Empty)
  +
Empty
  +
)
  +
Empty
  +
)
  +
)
  +
(Branch 'm' Empty Empty)
  +
)
  +
(Branch 'u'
  +
(Branch 'p'
  +
Empty
  +
(Branch 's'
  +
(Branch 'q' Empty Empty)
  +
Empty
  +
)
  +
)
  +
Empty
  +
)
  +
</haskell>
   
 
Example in Haskell:
 
Example in Haskell:
<example in Haskell>
 
</pre>
 
   
Solution:
 
 
<haskell>
 
<haskell>
<solution in haskell>
+
> layout tree64
  +
Branch ('n',(8,1)) (Branch ('k',(6,2)) (Branch ('c',(2,3)) ...
 
</haskell>
 
</haskell>
   
<description of implementation>
+
[[99 questions/Solutions/64 | Solutions]]
  +
 
 
 
== Problem 65 ==
 
== Problem 65 ==
   
<Problem description>
+
An alternative layout method is depicted in the illustration below:
   
<pre>
+
https://prof.ti.bfh.ch/hew1/informatik3/prolog/p-99/p65.gif
Example:
+
<example in lisp>
+
Find out the rules and write the corresponding function.
  +
Hint: On a given level, the horizontal distance between neighboring nodes is constant.
  +
  +
Use the same conventions as in problem P64 and test your function in an appropriate way.
  +
  +
Here is the example tree from the above illustration:
  +
  +
<haskell>
  +
tree65 = Branch 'n'
  +
(Branch 'k'
  +
(Branch 'c'
  +
(Branch 'a' Empty Empty)
  +
(Branch 'e'
  +
(Branch 'd' Empty Empty)
  +
(Branch 'g' Empty Empty)
  +
)
  +
)
  +
(Branch 'm' Empty Empty)
  +
)
  +
(Branch 'u'
  +
(Branch 'p'
  +
Empty
  +
(Branch 'q' Empty Empty)
  +
)
  +
Empty
  +
)
  +
</haskell>
   
 
Example in Haskell:
 
Example in Haskell:
<example in Haskell>
 
</pre>
 
   
Solution:
 
 
<haskell>
 
<haskell>
<solution in haskell>
+
> layout tree65
  +
Branch ('n',(15,1)) (Branch ('k',(7,2)) (Branch ('c',(3,3)) ...
 
</haskell>
 
</haskell>
   
<description of implementation>
+
[[99 questions/Solutions/65 | Solutions]]
+
  +
 
== Problem 66 ==
 
== Problem 66 ==
   
<Problem description>
+
Yet another layout strategy is shown in the illustration below:
   
<pre>
+
https://prof.ti.bfh.ch/hew1/informatik3/prolog/p-99/p66.gif
Example:
+
<example in lisp>
+
The method yields a very compact layout while maintaining a certain symmetry in every node. Find out the rules and write the corresponding Prolog predicate. Hint: Consider the horizontal distance between a node and its successor nodes. How tight can you pack together two subtrees to construct the combined binary tree?
  +
  +
Use the same conventions as in problem P64 and P65 and test your predicate in an appropriate way. Note: This is a difficult problem. Don't give up too early!
  +
  +
Which layout do you like most?
   
 
Example in Haskell:
 
Example in Haskell:
<example in Haskell>
 
</pre>
 
   
Solution:
 
 
<haskell>
 
<haskell>
<solution in haskell>
+
> layout tree65
  +
Branch ('n',(5,1)) (Branch ('k',(3,2)) (Branch ('c',(2,3)) ...
 
</haskell>
 
</haskell>
   
<description of implementation>
+
[[99 questions/Solutions/66 | Solutions]]
 
== Problem 67 ==
 
   
<Problem description>
+
  +
== Problem 67A ==
  +
  +
A string representation of binary trees
  +
  +
Somebody represents binary trees as strings of the following type:
  +
  +
:a(b(d,e),c(,f(g,)))
  +
  +
a) Write a Prolog predicate which generates this string representation, if the tree is given as usual (as nil or t(X,L,R) term). Then write a predicate which does this inverse; i.e. given the string representation, construct the tree in the usual form. Finally, combine the two predicates in a single predicate tree_string/2 which can be used in both directions.
  +
  +
Example in Prolog
   
 
<pre>
 
<pre>
Example:
+
?- tree_to_string(t(x,t(y,nil,nil),t(a,nil,t(b,nil,nil))),S).
<example in lisp>
+
S = 'x(y,a(,b))'
  +
?- string_to_tree('x(y,a(,b))',T).
  +
T = t(x, t(y, nil, nil), t(a, nil, t(b, nil, nil)))
  +
</pre>
   
 
Example in Haskell:
 
Example in Haskell:
<example in Haskell>
 
</pre>
 
   
Solution:
 
 
<haskell>
 
<haskell>
<solution in haskell>
+
Main> stringToTree "x(y,a(,b))" >>= print
  +
Branch 'x' (Branch 'y' Empty Empty) (Branch 'a' Empty (Branch 'b' Empty Empty))
  +
Main> let t = cbtFromList ['a'..'z'] in stringToTree (treeToString t) >>= print . (== t)
  +
True
 
</haskell>
 
</haskell>
   
<description of implementation>
+
[[99 questions/Solutions/67A | Solutions]]
  +
 
 
 
== Problem 68 ==
 
== Problem 68 ==
   
<Problem description>
+
Preorder and inorder sequences of binary trees. We consider binary trees with nodes that are identified by single lower-case letters, as in the example of problem P67.
   
<pre>
+
a) Write predicates preorder/2 and inorder/2 that construct the preorder and inorder sequence of a given binary tree, respectively. The results should be atoms, e.g. 'abdecfg' for the preorder sequence of the example in problem P67.
Example:
+
<example in lisp>
+
b) Can you use preorder/2 from problem part a) in the reverse direction; i.e. given a preorder sequence, construct a corresponding tree? If not, make the necessary arrangements.
  +
  +
c) If both the preorder sequence and the inorder sequence of the nodes of a binary tree are given, then the tree is determined unambiguously. Write a predicate pre_in_tree/3 that does the job.
   
 
Example in Haskell:
 
Example in Haskell:
<example in Haskell>
 
</pre>
 
   
Solution:
 
 
<haskell>
 
<haskell>
<solution in haskell>
+
Main> let { Just t = stringToTree "a(b(d,e),c(,f(g,)))" ;
  +
po = treeToPreorder t ;
  +
io = treeToInorder t } in preInTree po io >>= print
  +
Branch 'a' (Branch 'b' (Branch 'd' Empty Empty) (Branch 'e' Empty Empty)) (Branch 'c' Empty (Branch 'f' (Branch 'g' Empty Empty) Empty))
 
</haskell>
 
</haskell>
   
<description of implementation>
+
[[99 questions/Solutions/68 | Solutions]]
  +
 
 
 
== Problem 69 ==
 
== Problem 69 ==
   
<Problem description>
+
Dotstring representation of binary trees.
   
<pre>
+
We consider again binary trees with nodes that are identified by single lower-case letters, as in the example of problem P67. Such a tree can be represented by the preorder sequence of its nodes in which dots (.) are inserted where an empty subtree (nil) is encountered during the tree traversal. For example, the tree shown in problem P67 is represented as 'abd..e..c.fg...'. First, try to establish a syntax (BNF or syntax diagrams) and then write a predicate tree_dotstring/2 which does the conversion in both directions. Use
Example:
+
difference lists.
<example in lisp>
 
   
 
Example in Haskell:
 
Example in Haskell:
<example in Haskell>
 
</pre>
 
   
Solution:
 
 
<haskell>
 
<haskell>
<solution in haskell>
+
> fst (ds2tree example)
  +
Branch 'a' (Branch 'b' (Branch 'd' Empty Empty) (Branch 'e' Empty Empty)) (Branch 'c' Empty (Branch 'f' (Branch 'g' Empty Empty) Empty))
  +
  +
> tree2ds (Branch 'x' (Branch 'y' Empty Empty) (Branch 'z' (Branch '0' Empty Empty) Empty))
  +
"xy..z0..."
 
</haskell>
 
</haskell>
   
<description of implementation>
+
[[99 questions/Solutions/69 | Solutions]]
   
   

Latest revision as of 08:51, 2 December 2010


This is part of Ninety-Nine Haskell Problems, based on Ninety-Nine Prolog Problems.

[edit] 1 Binary trees

As defined in problem 54A.

An example tree:

tree4 = Branch 1 (Branch 2 Empty (Branch 4 Empty Empty))
                 (Branch 2 Empty Empty)

[edit] 2 Problem 61

Count the leaves of a binary tree

A leaf is a node with no successors. Write a predicate count_leaves/2 to count them.

Example:

% count_leaves(T,N) :- the binary tree T has N leaves

Example in Haskell:

> countLeaves tree4
2

Solutions

[edit] 3 Problem 61A

Collect the leaves of a binary tree in a list

A leaf is a node with no successors. Write a predicate leaves/2 to collect them in a list.

Example:

% leaves(T,S) :- S is the list of all leaves of the binary tree T

Example in Haskell:

> leaves tree4
[4,2]

Solutions

[edit] 4 Problem 62

Collect the internal nodes of a binary tree in a list

An internal node of a binary tree has either one or two non-empty successors. Write a predicate internals/2 to collect them in a list.

Example:

% internals(T,S) :- S is the list of internal nodes of the binary tree T.

Example in Haskell:

Prelude>internals tree4
Prelude>[1,2]

Solutions


[edit] 5 Problem 62B

Collect the nodes at a given level in a list

A node of a binary tree is at level N if the path from the root to the node has length N-1. The root node is at level 1. Write a predicate atlevel/3 to collect all nodes at a given level in a list.

Example:

% atlevel(T,L,S) :- S is the list of nodes of the binary tree T at level L

Example in Haskell:

Prelude>atLevel tree4 2
Prelude>[2,2]

Solutions

[edit] 6 Problem 63

Construct a complete binary tree

A complete binary tree with height H is defined as follows:

  • The levels 1,2,3,...,H-1 contain the maximum number of nodes (i.e 2**(i-1) at the level i)
  • In level H, which may contain less than the maximum possible number of nodes, all the nodes are "left-adjusted". This means that in a levelorder tree traversal all internal nodes come first, the leaves come second, and empty successors (the nil's which are not really nodes!) come last.

Particularly, complete binary trees are used as data structures (or addressing schemes) for heaps.

We can assign an address number to each node in a complete binary tree by enumerating the nodes in level-order, starting at the root with number 1. For every node X with address A the following property holds: The address of X's left and right successors are 2*A and 2*A+1, respectively, if they exist. This fact can be used to elegantly construct a complete binary tree structure.

Write a predicate complete_binary_tree/2.

Example:

% complete_binary_tree(N,T) :- T is a complete binary tree with N nodes.

Example in Haskell:

Main> completeBinaryTree 4
Branch 'x' (Branch 'x' (Branch 'x' Empty Empty) Empty) (Branch 'x' Empty Empty)
 
Main> isCompleteBinaryTree $ Branch 'x' (Branch 'x' Empty Empty) (Branch 'x' Empty Empty)
True

Solutions

[edit] 7 Problem 64

Given a binary tree as the usual Prolog term t(X,L,R) (or nil). As a preparation for drawing the tree, a layout algorithm is required to determine the position of each node in a rectangular grid. Several layout methods are conceivable, one of them is shown in the illustration below:

p64.gif

In this layout strategy, the position of a node v is obtained by the following two rules:

  • x(v) is equal to the position of the node v in the inorder sequence
  • y(v) is equal to the depth of the node v in the tree

Write a function to annotate each node of the tree with a position, where (1,1) in the top left corner or the rectangle bounding the drawn tree.

Here is the example tree from the above illustration:

tree64 = Branch 'n'
                (Branch 'k'
                        (Branch 'c'
                                (Branch 'a' Empty Empty)
                                (Branch 'h'
                                        (Branch 'g'
                                                (Branch 'e' Empty Empty)
                                                Empty
                                        )
                                        Empty
                                )
                        )
                        (Branch 'm' Empty Empty)
                )
                (Branch 'u'
                        (Branch 'p'
                                Empty
                                (Branch 's'
                                        (Branch 'q' Empty Empty)
                                        Empty
                                )
                        )
                        Empty
                )

Example in Haskell:

> layout tree64
Branch ('n',(8,1)) (Branch ('k',(6,2)) (Branch ('c',(2,3)) ...

Solutions


[edit] 8 Problem 65

An alternative layout method is depicted in the illustration below:

p65.gif

Find out the rules and write the corresponding function. Hint: On a given level, the horizontal distance between neighboring nodes is constant.

Use the same conventions as in problem P64 and test your function in an appropriate way.

Here is the example tree from the above illustration:

tree65 = Branch 'n'
                (Branch 'k'
                        (Branch 'c'
                                (Branch 'a' Empty Empty)
                                (Branch 'e'
                                        (Branch 'd' Empty Empty)
                                        (Branch 'g' Empty Empty)
                                )
                        )
                        (Branch 'm' Empty Empty)
                )
                (Branch 'u'
                        (Branch 'p'
                                Empty
                                (Branch 'q' Empty Empty)
                        )
                        Empty
                )

Example in Haskell:

> layout tree65
Branch ('n',(15,1)) (Branch ('k',(7,2)) (Branch ('c',(3,3)) ...

Solutions


[edit] 9 Problem 66

Yet another layout strategy is shown in the illustration below:

p66.gif

The method yields a very compact layout while maintaining a certain symmetry in every node. Find out the rules and write the corresponding Prolog predicate. Hint: Consider the horizontal distance between a node and its successor nodes. How tight can you pack together two subtrees to construct the combined binary tree?

Use the same conventions as in problem P64 and P65 and test your predicate in an appropriate way. Note: This is a difficult problem. Don't give up too early!

Which layout do you like most?

Example in Haskell:

> layout tree65
Branch ('n',(5,1)) (Branch ('k',(3,2)) (Branch ('c',(2,3)) ...

Solutions


[edit] 10 Problem 67A

A string representation of binary trees

Somebody represents binary trees as strings of the following type:

a(b(d,e),c(,f(g,)))

a) Write a Prolog predicate which generates this string representation, if the tree is given as usual (as nil or t(X,L,R) term). Then write a predicate which does this inverse; i.e. given the string representation, construct the tree in the usual form. Finally, combine the two predicates in a single predicate tree_string/2 which can be used in both directions.

Example in Prolog

?- tree_to_string(t(x,t(y,nil,nil),t(a,nil,t(b,nil,nil))),S).
S = 'x(y,a(,b))'
?- string_to_tree('x(y,a(,b))',T).
T = t(x, t(y, nil, nil), t(a, nil, t(b, nil, nil)))

Example in Haskell:

Main> stringToTree "x(y,a(,b))" >>= print
Branch 'x' (Branch 'y' Empty Empty) (Branch 'a' Empty (Branch 'b' Empty Empty))
Main> let t = cbtFromList ['a'..'z'] in stringToTree (treeToString t) >>= print . (== t)
True

Solutions


[edit] 11 Problem 68

Preorder and inorder sequences of binary trees. We consider binary trees with nodes that are identified by single lower-case letters, as in the example of problem P67.

a) Write predicates preorder/2 and inorder/2 that construct the preorder and inorder sequence of a given binary tree, respectively. The results should be atoms, e.g. 'abdecfg' for the preorder sequence of the example in problem P67.

b) Can you use preorder/2 from problem part a) in the reverse direction; i.e. given a preorder sequence, construct a corresponding tree? If not, make the necessary arrangements.

c) If both the preorder sequence and the inorder sequence of the nodes of a binary tree are given, then the tree is determined unambiguously. Write a predicate pre_in_tree/3 that does the job.

Example in Haskell:

Main> let { Just t = stringToTree "a(b(d,e),c(,f(g,)))" ;
            po = treeToPreorder t ;
            io = treeToInorder t } in preInTree po io >>= print
Branch 'a' (Branch 'b' (Branch 'd' Empty Empty) (Branch 'e' Empty Empty)) (Branch 'c' Empty (Branch 'f' (Branch 'g' Empty Empty) Empty))

Solutions


[edit] 12 Problem 69

Dotstring representation of binary trees.

We consider again binary trees with nodes that are identified by single lower-case letters, as in the example of problem P67. Such a tree can be represented by the preorder sequence of its nodes in which dots (.) are inserted where an empty subtree (nil) is encountered during the tree traversal. For example, the tree shown in problem P67 is represented as 'abd..e..c.fg...'. First, try to establish a syntax (BNF or syntax diagrams) and then write a predicate tree_dotstring/2 which does the conversion in both directions. Use difference lists.

Example in Haskell:

> fst (ds2tree example)
Branch 'a' (Branch 'b' (Branch 'd' Empty Empty) (Branch 'e' Empty Empty)) (Branch 'c' Empty (Branch 'f' (Branch 'g' Empty Empty) Empty))
 
> tree2ds (Branch 'x' (Branch 'y' Empty Empty) (Branch 'z' (Branch '0' Empty Empty) Empty))
"xy..z0..."

Solutions