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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
|
<?xml version="1.0" encoding="ISO-8859-1" standalone="yes"?>
<page name="tutorial_exercises">
<title>Exercises</title>
<left>
<boxes-toc/>
<p>
You can cut and paste the code on this page and
test it on the <a href="http://reglisse.ens.fr/cgi-bin/cduce">online interpreter</a>.
</p>
</left>
<box title="Tree navigation" link="treenav">
<section title="XPath expressions">
<p>Write a function that implements <code>//t</code> without
using references types and <code>xtransform</code></p>
<ol>
<li>Give a non tail-recursive version</li>
<li>Give a tail-recursive version</li>
</ol>
</section>
</box>
<box title="Patterns" link="pat">
<section title="Sort (by Artur Miguel Diaz: http://ctp.di.fct.unl.pt/~amd)">
<p>
Write a non recursive function of type <code> Int -> Latin1</code> which given a non-negative number produces all its digits in the order.
</p>
<p>
The function is given below nearly completely programmed. Define the patterns that allows to produce the result.</p>
<sample> <![CDATA[
let sortAlg (n :Int):Latin1 =
match string_of n with
%%PATTERN%% -> %%RESULT%%
;;
]]> </sample>
<p>Example:</p>
<sample> <![CDATA[
fact 200 =
788657867364790503552363213932185062295135977687173263294742533
244359449963403342920304284011984623904177212138919638830257642
790242637105061926624952829931113462857270763317237396988943922
445621451664240254033291864131227428294853277524242407573903240
321257405579568660226031904170324062351700858796178922222789623
703897374720000000000000000000000000000000000000000000000000
sortAlg (fact 200) =
"00000000000000000000000000000000000000000000000000000000000000
000000000000001111111111111111111111111122222222222222222222222
222222222222222222222222222222233333333333333333333333333333333
333333333444444444444444444444444444444444445555555555555555555
555555666666666666666666666666666667777777777777777777777777777
7777777888888888888888888888889999999999999999999999999999999"
]]> </sample>
</section>
</box>
<box title="Solutions" link="solution">
<section title="Tree navigation">
<sample><![CDATA[
type t = %%specify here a type to test%%
fun ( x :[Any*]):[t*] =
let f( x :[Any*]):[t*]) = ...
]]></sample>
<p>Note here that the recursive function <code>f</code> is wrapped by a second anonymous function so that it does not expose the recursion variable.</p>
<sample><![CDATA[
fun (e : [Any*]):[ T*] =
let f( accu :[T*] , x :[Any*]):[T*] =
match x with
[ h&T&<_ ..>(k&[Any*]) ;t] -> f( accu@[h], k@t)
| [ <_ ..>(k&[Any*]) ;t] -> f( accu, k@t)
| [ h&T ;t] -> f( accu@[h], t)
| [ _ ;t] -> f( accu, t)
| [] -> accu
in f ([], e);;
]]></sample>
<p>Note that this implementation may generate empty branch warnings in particular</p>
<ul>
<li>for the first branch if <code>T&<_ ..>(k&[Any*])</code> is <code>Empty</code></li>
<li>for the second branch if <code><_ ..>(k&[Any*])</code> is smaller than <code>T&<_>(k&[Any*])</code></li>
<li>for the first branch if <code>t</code> is smaller than <code><_ ..>(k&[Any*])</code></li>
</ul>
</section>
<section title="Patterns">
<sample> <![CDATA[
let sortAlg (n :Int):Latin1 =
match string_of n with
[ (s0::'0' | s1::'1' | s2::'2' | s3::'3' | s4::'4' |
s5::'5' | s6::'6' | s7::'7' | s8::'8' | s9::'9')+ ] ->
s0 @ s1 @ s2 @ s3 @ s4 @ s5 @ s6 @ s7 @ s8 @ s9
| _ -> raise "Invalid argument for sortAlg."
;;
]]> </sample>
</section>
</box>
</page>
|