Tree navigation
XPath expressions
Write a function that implements //t without using references types and xtransform
- Give a non tail-recursive version
- Give a tail-recursive version
Patterns
Sort (by Artur Miguel Diaz: http://ctp.di.fct.unl.pt/~amd)
Write a non recursive function of type Int -> Latin1 which given a non-negative number produces all its digits in the order.
The function is given below nearly completely programmed. Define the patterns that allows to produce the result.
let sortAlg (n :Int):Latin1 = match string_of n with PATTERN -> RESULT ;;
Example:
fact 200 = 788657867364790503552363213932185062295135977687173263294742533 244359449963403342920304284011984623904177212138919638830257642 790242637105061926624952829931113462857270763317237396988943922 445621451664240254033291864131227428294853277524242407573903240 321257405579568660226031904170324062351700858796178922222789623 703897374720000000000000000000000000000000000000000000000000 sortAlg (fact 200) = "00000000000000000000000000000000000000000000000000000000000000 000000000000001111111111111111111111111122222222222222222222222 222222222222222222222222222222233333333333333333333333333333333 333333333444444444444444444444444444444444445555555555555555555 555555666666666666666666666666666667777777777777777777777777777 7777777888888888888888888888889999999999999999999999999999999"
Solutions
Tree navigation
type t = specify here a type to test fun ( x :[Any*]):[t*] = let f( x :[Any*]):[t*]) = ...
Note here that the recursive function f is wrapped by a second anonymous function so that it does not expose the recursion variable.
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);;
Note that this implementation may generate empty branch warnings in particular
- for the first branch if T&<_ ..>(k&[Any*]) is Empty
- for the second branch if <_ ..>(k&[Any*]) is smaller than T&<_>(k&[Any*])
- for the first branch if t is smaller than <_ ..>(k&[Any*])
Patterns
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." ;;