- Tree navigation
- Patterns
- Solutions

You can cut and paste the code on this page and test it on the online interpreter.

# Exercises

CDuce: documentation: Tutorial: Exercises

Higher-order functions User's manual

## Tree navigation

### XPath expressions

Write a function that implements `//t` without using references types and `xtransform`

1. Give a non tail-recursive version
2. 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."
    ;;

Site map

CDuce: documentation: Tutorial: Exercises

Higher-order functions User's manual