Discussion :

[hortensiass]

Bonjour,
J'ai un probleme en caml light.
Pour un programme je dois insérer un élément dans un tableau pour cela je le coupe en deux avec la fonction sub_vect avec deux fonctions auxilliaires

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
let aux1 (t:int vect) (i:int)=
sub_vect t 0 i;;
cette fonction ne pose pas de problème, par contre, pour la deuxieme
let aux2 (t:int vect) (i:int)=
let p=vect_length t in
sub_vect t i+1 p-2-i;;

il semble y avoir un probleme de type car il me renvoit à propos de sub_vect... cette expression est de type int->int vect mais est utilisée avec le type int.
merci d'avance

[gorgonite]

et comme cela ?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

sub_vect t (i+1) (p-2-i)

[hortensiass]

merci beaucoup et désolée pour cette question!

[InOCamlWeTrust]

Petite remarque : on ne coupe JAMAIS un tableau pour y insérer un élément. C'est une habitude de bonne programmation/algorithmie : si tu dois faire ainsi, ça veut dire que tu n'utilises pas le tableau comme il faut. C'est justement l'une des principales caractéristiques des tableaux : pouvoir accéder à un élément quelconque, à la différence des listes.

[phryte]

merci beaucoup et désolée pour cette question!

Où insérer l'élément ? à un rang ?
voici une réponse possible avec une liste v, (insérer x au rang r) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
let v=1::2::3::4::5::[];;
let r=1;;
let rec insert x = fun 
   [] -> [] 
  | (a::q) -> (
      if list_length q = (list_length v)-r 
      then x::a::q 
      else a :: (insert x q)
    )
;;
insert 9 v;;
 
let rec insert1 x = function
[] -> [x]
| t::q when list_length q = list_length v -r -> x::t::q
| t::q -> t :: (insert1 x q);;
insert1 9 v;;

[Jedai]

Où insérer l'élément ? à un rang ?
voici une réponse possible avec une liste v, (insérer x au rang r) :

Sauf que : ta liste v est fixe, ton rang aussi, tu utilises 2 list_length à chaque itération... En bref ton algo est en O(r*n) et ton implémentation n'est pas pratique à réutiliser.

Une solution en O(r) et réutilisable :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
let rec insert r x ys = 
  if r = 0 
  then x :: ys 
  else match ys with
    | [] -> []
    | t :: q -> t :: insert (r-1) x q

--
Jedaï

[Garulfo]

Allez hop.. deux autres versions.

Une tail-recursive

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
let insert_2 r x ys = 
    let rec insert_aux r element liste tete =
        if r = 0
        then List.rev_append tete (element :: liste) 
        else match liste with
            | [] -> ys
            | t :: q -> insert_aux (r-1) element q (t :: tete)
    in
        insert_aux r x ys []
    ;;

et une par continuation

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
let insert_3 r x ys =
    let rec insert_aux r element liste k =
        if r = 0
        then k (element :: liste)
        else match liste with
            | [] -> ys
            | t :: q -> let k0 = fun l -> (k (t::l))
                        in
                            insert_aux (r-1) element q k0
    in
        insert_aux r x ys (fun x -> x)
    ;;