<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd"><html xmlns="http://www.w3.org/1999/xhtml"><head><title>CDuce: Exercises</title><meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1"/><link href="cduce.css" type="text/css" rel="stylesheet"/></head><body style="margin: 0; padding : 0;"><table width="100%" border="0" cellspacing="10" cellpadding="0"><tr><td valign="top" style="width:20%;" align="left"><div class="leftbar" id="leftbar"><div class="smallbox"><ul><li><a href="#treenav">Tree navigation</a></li><li><a href="#pat">Patterns</a></li><li><a href="#solution">Solutions</a></li></ul><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></div></div></td><td><h1>Exercises</h1><div class="mainpanel"><div class="smallbox"><p><a href="index.html">CDuce: documentation</a>: <a href="tutorial.html">Tutorial</a>: Exercises</p><p><a href="tutorial_higherorder.html"><img class="icon" width="16" alt="Previous page:" src="img/left.gif" height="16"/> Higher-order functions</a> <a href="manual.html"><img class="icon" width="16" alt="Next page:" src="img/right.gif" height="16"/> User's manual</a></p></div><div><h2><a name="treenav">Tree navigation</a></h2><h3>XPath expressions</h3><p>Write a function that implements <b><tt>//t</tt></b> without
using references types and <b><tt>xtransform</tt></b></p><ol><li>Give a non tail-recursive version</li><li>Give a tail-recursive version</li></ol></div><div><h2><a name="pat">Patterns</a></h2><h3>Sort (by Artur Miguel Diaz: http://ctp.di.fct.unl.pt/~amd)</h3><p>
Write a non recursive function of type <b><tt> Int -> Latin1</tt></b> 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><div class="code"><pre>
let sortAlg (n :Int):Latin1 =
match string_of n with
<i>PATTERN</i> -> <i>RESULT</i>
;;
</pre></div><p>Example:</p><div class="code"><pre>
fact 200 =
788657867364790503552363213932185062295135977687173263294742533
244359449963403342920304284011984623904177212138919638830257642
790242637105061926624952829931113462857270763317237396988943922
445621451664240254033291864131227428294853277524242407573903240
321257405579568660226031904170324062351700858796178922222789623
703897374720000000000000000000000000000000000000000000000000
sortAlg (fact 200) =
"00000000000000000000000000000000000000000000000000000000000000
000000000000001111111111111111111111111122222222222222222222222
222222222222222222222222222222233333333333333333333333333333333
333333333444444444444444444444444444444444445555555555555555555
555555666666666666666666666666666667777777777777777777777777777
7777777888888888888888888888889999999999999999999999999999999"
</pre></div></div><div><h2><a name="solution">Solutions</a></h2><h3>Tree navigation</h3><div class="code"><pre>
type t = <i>specify here a type to test</i>
fun ( x :[Any*]):[t*] =
let f( x :[Any*]):[t*]) = ...
</pre></div><p>Note here that the recursive function <b><tt>f</tt></b> is wrapped by a second anonymous function so that it does not expose the recursion variable.</p><div class="code"><pre>
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);;
</pre></div><p>Note that this implementation may generate empty branch warnings in particular</p><ul><li>for the first branch if <b><tt>T&<_ ..>(k&[Any*])</tt></b> is <b><tt>Empty</tt></b></li><li>for the second branch if <b><tt><_ ..>(k&[Any*])</tt></b> is smaller than <b><tt>T&<_>(k&[Any*])</tt></b></li><li>for the first branch if <b><tt>t</tt></b> is smaller than <b><tt><_ ..>(k&[Any*])</tt></b></li></ul><h3>Patterns</h3><div class="code"><pre>
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."
;;
</pre></div></div><div class="meta"><p><a href="sitemap.html">Site map</a></p></div><div class="smallbox"><p><a href="index.html">CDuce: documentation</a>: <a href="tutorial.html">Tutorial</a>: Exercises</p><p><a href="tutorial_higherorder.html"><img class="icon" width="16" alt="Previous page:" src="img/left.gif" height="16"/> Higher-order functions</a> <a href="manual.html"><img class="icon" width="16" alt="Next page:" src="img/right.gif" height="16"/> User's manual</a></p></div></div></td></tr></table></body></html>
