Ubuntu-fr

reaver

les listes -> CAML

Bonjour,
je bloque sur un langage de programmation en caml.
j'ai lu que pour sélectionner un élément dans une liste répondant à une condition on pouvait écrire :
let rec sel cond lst =
match lst with
|[] -> none
| t::q -> if cond t then some t
             else sel cond q
je ne comprend pas comment est ce que je pourrais exécuter ce programme ni ce que signifie "some t"
Merci d'avance pour votre aide

Dernière modification par slasher-fun (Le 03/03/2011, à 20:55)

fde

Re : les listes -> CAML

Salut reaver! Heureux de voir qu'on ne parle pas que de langages impératifs sur ubuntu-fr!:)

Bon, pour ta question, c'est assez simple : il existe un type algébrique (i.e. un type symbolique, utilisant des constructeurs) nommé "option". Celui-ci est paramétrique, et a comme définition :

type ’a option = None | Some of ’a

Ce type permet, dans notre cas, de faire quelque chose du genre : SI il existe un élément t appartenant à la liste et répondant à la condition, alors -> Some t. Sinon, pas de solution -> None. Le type de ta fonction sel sera donc :

('a -> bool) -> 'a list -> 'a option

Attention, étant plutôt spécialiste de Haskell, il se peut que j'aie commis des erreurs de syntaxes. A première vue, non, mais on ne sait jamais...

Dernière modification par fde (Le 04/03/2007, à 19:20)

reaver

Re : les listes -> CAML

mais justement je ne comprend toujours pas comment je peux faire pour exécuter mon programme ? Et quelle est la définition de "some"?
Merci beaucoup !

fde

Re : les listes -> CAML

Je viens de définir Some. Relis ce que j'ai écrit.
Pour exécuter ton programme, tu as besoin d'un interpréteur CaML (j'en ai utilisé un il y a quelques années, mais je ne sais plus le nom). Tu écris ta fonction, ensuite tu la valides (elle est retenue par l'interpréteur). Pour l'utiliser, tu l'appelles avec des arguments valides, c'est-à-dire répondant à la signature que je t'ai donnée.

Dernière modification par fde (Le 04/03/2007, à 19:41)

Yannick_LM

Re : les listes -> CAML

Sinon, sans utiliser option :

let sel2 cond lst = 
let rec sel_aux (l1,l2) =
match(l1,l2) with
| [],a -> a 
| a::q,res -> if cond a then (sel_aux(q,a::res))
 			else (sel_aux(q,res))
in
sel_aux(lst, []) ;;

Attention, ici, on renvoie la liste des éléments qui conviennent (et pas une option contenant juste le premier élément qui convient ou none)

Voilà....

(Ah, Caml, la prépa, tout ça. Que de bons souvenirs)

---

Trucs et astuces pour Vim
Ma web page  avec des trucs dessus ...

Yannick_LM

Re : les listes -> CAML

Bon, j'arrive un peu tard.

Sinon, il y a ocaml (dans les dépôts)

L'interpréteur s'appelle ocaml, tu peux soit y entrer tes instructions une par une,  soit écrire un script en .ml, et exécuter le code avec

ocaml MonScript.ml

(Pas bavard)

Edit :
un script pour illustrer mon propos :

(* La condition : *)
let positif x = x > 0;;

(* Une fonction pour imprimer les listes *)
let rec print_list l =
match l with
| [] -> print_newline()
| a::q -> begin
		print_int(a) ;
		print_string(" ");
		print_list q ;
	end ;;


(* La fonction de sélection *)
let sel cond lst = 
let rec sel_aux (l1,l2) = (* fonction récursive auxilliaire *)
match(l1,l2) with
| [],a -> a 
| a::q,res -> if cond a then (sel_aux(q,a::res)) (* On rajoute a dans la liste des résultats *)
 			else (sel_aux(q,res)) 
in
sel_aux(lst, []) ;;

let list = [ -1 ; 2; -3 ; 4 ; -6] ;;

let res = sel positif list ;;

(* Affichage du résultat *)
print_list res;;

Voilà.

J'aurais découvert un truc : la prog, c'est comme le vélo, ça s'oublie pas...
(Ca faisait bien trois ans que je n'avais pas écrit une ligne en Caml)

Dernière modification par Yannick_LM (Le 04/03/2007, à 20:07)

---

Trucs et astuces pour Vim
Ma web page  avec des trucs dessus ...

fde

Re : les listes -> CAML

Bonjour,
je bloque sur un langage de programmation en caml.
j'ai lu que pour sélectionner un élément dans une liste répondant à une condition on pouvait écrire :

Salut Yannick_LM! Ton implémentation ne sélectionne pas un élément répondant à une condition, mais la sous-liste des éléments répondant à la condition ; tu as donc implémenté filter, et non sel, qui requiert l'utilisation du type option.

PS : Ta fonction est récursive terminale ; c'est bien! Elle aurait pu être aussi curryfiée ; c'est mieux!

Yannick_LM

Re : les listes -> CAML

Au temps pour moi ...

(ça m'apprendra à lire les sujets)
EDIT :
P.S.
Mais elle est curryfiée !

let sel_pos = sel positif;;
let res2 = sel_pos list ;;
print_list res2;;

affiche bien 4 2
Non ?
Ou alors, on n'est pas d'accord sur ce que signifie curryfiée ...
Bien qu'on soit d'accord sur le fait qu'elle soit récursive terminale.

Dernière modification par Yannick_LM (Le 04/03/2007, à 21:14)

---

Trucs et astuces pour Vim
Ma web page  avec des trucs dessus ...

fde

Re : les listes -> CAML

Oh c'est rien, je parlais simplement de sel_aux qui prend un couple au lieu de prendre deux arguments séparés... Généralement, on écrit plutôt la fonction récursive terminale  en ajoutant un accumulateur - comme tu l'as fait en ajoutant l2 - mais en plaçant cet accumulateur comme premier argument. C'est une question esthétique et un peu tirée par les cheveux, mais pour une fois qu'on parle progra déclarative sur mon forum préféré, j'en profite pour mettre mon grain de sel! :D

Yannick_LM

Re : les listes -> CAML

J'ai fini par trouver ce que tu voulais dire :

let sel cond lst = 
let rec sel_aux l1 l2 =
match l2 with
| [] -> l1
| a::q -> if cond a then (sel_aux (a::l1) q)
	  else (sel_aux l1 q) 
in
sel_aux [] lst ;;

....

Et c'est effectivement beaucoup plus joli.

---

Trucs et astuces pour Vim
Ma web page  avec des trucs dessus ...

reaver

Re : les listes -> CAML

Si par exemple ma condition est de choisir les entiers supérieurs à 5. je fais quoi ?

Yannick_LM

Re : les listes -> CAML

C'est vrai qu'on s'est un peu éloigné du sujet...

Bon, la fonction principale, c'est sel.
Elle prend en argument une condition cond et une liste lst.
Son type est donc :
('a -> bool) -> ('a list) -> 'a option

Si tu veux sélectionner un entier > 5, il faut définir une condition, (int -> bool), que tu appeleras par exemple sup_5, et ensuite, tu pourras utiliser

sel supp_5

Qui aura donc pour signature : int list -> int option

C'est l'avantage de Caml : des fonctions curryfiées, donc des fonctions passées en argument qui font d'autres fonctions ....

---

Trucs et astuces pour Vim
Ma web page  avec des trucs dessus ...