Discussion :

[alex_pi]

Vous avez des codes sources F# (ou OCaml compatibles avec F#) ?
Vous pensez que ces codes sources peuvent aider d'autres personnes ?
Vous souhaitez partager vos codes avec des internautes ?

Est ce qu'il ne serait pas bon, d'une façon ou d'une autre, de demander aux gens de mettre leur code sous licence ? Je pense que vu les codes, un creative common très permissif serait bien.. Parce que je me suis déjà retrouvé à regarder des codes OCaml qui m'auraient été utile, mais je ne les ai jamais utilisé parce qu'aucune licence n'était disponible. Que faire ?

[gorgonite]

Est ce qu'il ne serait pas bon, d'une façon ou d'une autre, de demander aux gens de mettre leur code sous licence ?

a priori, s'ils mettent leur code dispo sur un forum, c'est qu'ils le laissent à disposition de la communauté... donc je dirais LGPL par défaut, mais c'est une bonne question, et on va y refléchir

[LLB]

Juste pour te faire honte et afin que personne ne prenne exemple sur toi:

Si le but est de faire court...

Code :

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

1
2
3
type 'a type_inf = MinInf | Type of 'a | MaxInf

let includes (f1, t1) (f2, t2) = f1 <= f2 && t1 >= t2

[SpiceGuid]

J'ai amélioré mon type somme interval, et à ce propos je n'aime pas la méthode intersect car elle devrait retourner un 'a interval option, mais je suppose qu'il y a un soucis de compatibilité avec C#/.Net

[gorgonite]

J'ai amélioré mon type somme interval, et à ce propos je n'aime pas la méthode intersect car elle devrait retourner un 'a interval option, mais je suppose qu'il y a un soucis de compatibilité avec C#/.Net

il n'y a pas de soucis a priori... mais si l'on renvoit un intervalle "vide", je ne vois pas le problème

[alex_pi]

J'ai amélioré mon type somme interval, et à ce propos je n'aime pas la méthode intersect car elle devrait retourner un 'a interval option, mais je suppose qu'il y a un soucis de compatibilité avec C#/.Net

Je ne suis a priori pas trop d'accord avec toi. Un interval vide reste un interval, ce n'est pas une absence d'interval ! Après, il faut peut être rajouter la notion d'interval vide à ton type

[SpiceGuid]

Un de nos gentils membres a demandé s'il pouvait accéder au n-ième élément d'une liste comme avec un tableau (en temps constant).

La réponse est négative, toutefois à l'aide d'une VList on peut accéder au n-ième élément d'une liste en temps logarithmique sans dégrader la performance des opérations cons, hd et tl.

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
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
module VList = struct

type 'a vector =
  {vect: 'a array; mutable hd: int; tl: 'a vlist}
and 'a vlist =
  | Nil
  | Node of 'a * 'a vlist 
  | Vect of int * 'a vector

let cons h t =
  match t with
  | Nil ->
      let v = {vect=Array.make 4 h; hd=0; tl=t}
      in  Vect(h,v)
  | Node _ ->
      Node(h,t)
  | Vect(h,v) ->
      if h=v.hd then begin
        v.hd <- v.hd + 1;
        if v.hd < Array.length v.vect then begin
          v.vect.(v.hd) <- h; Vect(v.hd,v)
        end else begin
          let w = {vect=Array.make (v.hd+v.hd) h; hd=0; tl=t}
          in  v.hd <- v.hd - 1; Vect(0,w)           
        end
      end else
        Node(h,t)      

let hd l =
  match l with
  | Nil -> failwith "hd"
  | Node(h,t) -> h
  | Vect(h,v) -> v.vect.(h)

let tl l =
  match l with
  | Nil ->  failwith "tl" 
  | Node(h,t) -> t
  | Vect(h,v) -> if h>0 then Vect(h-1,v) else v.tl

let rec nth l n =
  match l with
  | Nil -> failwith "nth"
  | Node(h,t) -> if n=0 then h else nth t (n-1)
  | Vect(h,v) -> if n <= h then v.vect.(h-n) else nth v.tl (n-h-1)

end

EDIT:
Contrairement à Phil Bagwell, dans le cas d'un partage j'ai préféré retourner à une liste ordinaire (sinon la mémoire), et seule la liste "originale" bénéficie de l'accès en temps logarithmique. Pour un accès en temps logarithmique même en cas de partage et sans la mémoire il faut des techniques plus avancées (à la Okasaki).

Il y a aussi la question du filtrage, on a pas de filtrage, d'où la nécessité des catamorphismes (ici fold_left et fold_right).

[InOCamlWeTrust]

Dans la librairie de OCaml, il y a Set et Map aussi qui sont très bien... mais on peut faire un poil mieux (en travaillant beaucoup, par contre) avec les arbres AVL.

[gorgonite]

Dans la librairie de OCaml, il y a Set et Map aussi qui sont très bien... mais on peut faire un poil mieux (en travaillant beaucoup, par contre) avec les arbres AVL.

c'est quand même facile à coder un AVL... même dans des langages bas niveau où faut tout gérer (je me souviens d'une utilisation générique en C, ça m'a pris moins d'une aprem à coder )

[SpiceGuid]

Un AVL ne permet pas d'ajouter une donnée en temps constant.
Une table de hachage le fait mais n'est pas un TAD persistent (fonctionnel).

[InOCamlWeTrust]

Une table de hachage ne PERMET PAS d'ajouter non plus un élément en temps constant... si tu trouves la preuve quelque part, tu me l'amènes ! De plus les AVL permettent de n'utiliser que la mémoire réellement nécessaire, évitant ainsi les gaspillages, et ne font intervenir aucun redimensionnement (qui pour le coup est linéaire... donc extrêmement coûteux).

Mais bon, on ne va pas s'acharner sur ce genre de trucs.

[Jedai]

Une table de hachage ne PERMET PAS d'ajouter non plus un élément en temps constant... si tu trouves la preuve quelque part, tu me l'amènes ! De plus les AVL permettent de n'utiliser que la mémoire réellement nécessaire, évitant ainsi les gaspillages, et ne font intervenir aucun redimensionnement (qui pour le coup est linéaire... donc extrêmement coûteux).

Le gros avantage d'une table de hachage c'est une meilleure localité mémorielle. Par contre je suis bien d'accord que l'avantage en performance par rapport à de bons arbres équilibrés est souvent exagéré.

--
Jedaï

[InOCamlWeTrust]

Le gros avantage d'une table de hachage c'est une meilleure localité mémorielle.

Mmmmouui... enfin, bon, moi je trouve que les gens font une trop grande fixation sur cette structure de données, certes efficace.

[LLB]

Je voulais une table de hachage globale (dont les clés sont des strings), dans laquelle je pusse mettre n'importe quel type de valeur. Cependant, je voulais séparer les différents types pour éviter les conflits, comme si j'avais une table de hachage par type.

Le but était donc d'alléger mon code et de ne pas avoir à manipuler 10 tables de hachage similaires.

Code F# :

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

1
2
3
4
5
open System.Collections.Generic
 
let data = Dictionary<_,_>()
let generic_get<'a> (x: string) = data.[(x, typeof<'a>)] |> unbox<'a>
let generic_set x (v: 'a) = data.[(x, typeof<'a>)] <- box v

Exemple d'utilisation :

Code F# :

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

1
2
3
4
5
6
7
8
9
10
11
12
> generic_set "str1" 42;;
val it : unit = ()
> generic_set "str2" 12;;
val it : unit = ()
> generic_set "str1" "valeur";;
val it : unit = ()
> 10 + generic_get "str1";;
val it : int = 52
> "abc" + generic_get "str1";;
val it : string = "abcvaleur"
> generic_get<int> "str2";;
val it : int = 12

[gasche]

Edit: j'ai amélioré le code pour mettre l'accent sur la sémantique (à l'aide d'un type inductif) plutôt que sur la concision

J'ai amélioré le code pour mettre l'accent sur la modularité plutôt que sur les types inductifs.

On commence avec un code modulaire simple, semblable au code de gorgonite (mais en moins laid) :

Code :

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

1
2
3
4
5
6
7
8
9
10
type 'a interval = 'a bound * 'a bound
and 'a bound = { value : 'a; eq : 'a -> 'a -> bool; inf : 'a -> 'a -> 'a; sup : 'a -> 'a -> 'a }

let eq (x, y) (x', y') = x.eq x.value x'.value && y.eq y.value y'.value

let intersection (x, y) (x', y') =
  {x with value = x.sup x.value x'.value},
  {y with value = y.inf y.value y'.value}

let includes a b = eq b (intersection a b)

On met une petite routine de création des bornes :

Code :

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

1
2
3
4
5
6
(* Simple intervals (bound functions inferred from a compare function) *)
let simple_bound cmp x =
  { value = x;
    eq = (fun a b -> cmp a b = 0);
    inf = (fun a b -> if cmp a b <= 0 then a else b);
    sup = (fun a b -> if cmp a b >= 0 then a else b) }

Ensuite on améliore incrémentalement : on crée des fonctions qui vont créer un nouveau type "bound" en ajoutant des fonctionnalités.

Gestion des types produits (on se place dans l'ensemble produit, au lieu de mettre les produits dans la définition d'un intervalle comme le fait assez laidement SpiceGuid) :

Code :

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

1
2
3
4
5
6
7
8
(* product *)
let product bound_a bound_b =
  { value = bound_a.value, bound_b.value;
    eq = (fun (a, b) (a', b') -> bound_a.eq a a' && bound_b.eq b b');
    inf = (fun (a, b) (a', b') -> bound_a.inf a a', bound_b.inf b b');
    sup = (fun (a, b) (a', b') -> bound_a.sup a a', bound_b.sup b b') }

let interval_product (a, b) (a', b') = (product a a', product b b')

Gestion des bornes ouvertes ou fermées dans un intervalle :

Code :

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

1
2
3
4
5
6
7
8
(* open/closed intervals : 'true' means closed *)
type 'a open_closed = bool * 'a

let with_openclose bound =
  { value = (true, bound.value);
    eq = (fun (ta, a) (tb, b) -> ta = tb && bound.eq a b);
    inf = (fun (ta, a) (tb, b) -> ta || tb, bound.inf a b);
    sup = (fun (ta, a) (tb, b) -> ta || tb, bound.sup a b) }

Gestion des valeurs infinies :

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
18
19
20
(* infinity *)
type 'a with_infinity =
  Value of 'a | Neg_inf | Pos_inf

let with_infinity bound =
  { value = Value bound.value;
    eq = (fun a b -> match a, b with
          | Neg_inf, Neg_inf | Pos_inf, Pos_inf -> true
          | Value x, Value y -> bound.eq x y
          | _ -> false);
    inf = (fun a b -> match a, b with
           | Neg_inf, _ | _, Neg_inf -> Neg_inf
           | Pos_inf, t | t, Pos_inf -> t
           | Value x, Value y -> Value (bound.inf x y));
    sup = (fun a b -> match a, b with
           | Neg_inf, t | t, Neg_inf -> t
           | Pos_inf, _ | _, Pos_inf -> Pos_inf
           | Value x, Value y -> Value (bound.sup x y)) }

let interval_with_infinity (a, a') = with_infinity a, with_infinity a'

Je trouve cette manière de faire assez rigolote. Après c'est à l'utilisateur de se faire sa propre cuisine. Pour représenter des intervalles usuels dans R, il faut des (float open_closed with_infinity). Si on utilise (float with_infinity open_closed), on obtient des intervalles dans le compactifié de R (donc avec les valeurs {+oo} et {-oo} représentables).

Pour représenter l'ensemble vide, on peut soit utiliser [3,2] (si la borne inférieure est plus grande que la borne supérieure, c'est vide), soit utiliser des 'a openclosed et faire un singleton ouvert.

Enfin, le grand avantage par rapport au code de SpiceGuid et la gestion des produits de types non-homogènes.

Version complète, avec quelques tests :
http://bluestorm.info/ocaml/interval.ml.html (enlever le .html pour avoir la source)

[SpiceGuid]

Bravo

Code :

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

1
2
type 'a interval = 'a bound * 'a bound
and 'a bound = { value : 'a; eq : 'a -> 'a -> bool; inf : 'a -> 'a -> 'a; sup : 'a -> 'a -> 'a }

C'est plus polymorphe que mon code (qui n'utilise que Pervasives.compare).

on se place dans l'ensemble produit, au lieu de mettre les produits dans la définition d'un intervalle

Tu généralise au produit cartésien alors que je n'avais généralisé qu'à la puissance.
Et surtout ton code est plus fortement typé, le mien peut générer des exceptions Invalid_argument.

[gasche]

Et surtout ton code est plus fortement typé, le mien peut générer des exceptions Invalid_argument.

Où est-ce que tu risques l'invalid_argument ?

Sinon, il reste un problème avec le code tel quel, c'est qu'il est possible de mélanger dans un intervalle des bornes avec des fonctions de comparaison différentes. Ça pourrait se régler en rajoutant des assertions (mais utiliser l'égalité physique sur les types fonctionnels c'est un peu risqué, il faut faire gaffe quand on déclare les bornes; heureusement si on passe que par des constructeurs comme simple_bound on peut le faire côté lib), mais ça revient à faire des tests au runtime.

[alex_pi]

Code :

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

1
2
type 'a interval = 'a bound * 'a bound
and 'a bound = { value : 'a; eq : 'a -> 'a -> bool; inf : 'a -> 'a -> 'a; sup : 'a -> 'a -> 'a }

Ca ne devrait pas plutôt être :

Code :

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

1
2
type 'a interval = 'a bound * 'a bound
and 'a bound = { value : 'a; eq : 'a bound -> bool; inf : 'a bound -> 'a bound; sup : 'a bound -> 'a bound }

? Bon ok, ça forcerait à stocker plus de fermetures différentes, mais ce serait pas plus logique, puisqu'on stocke les fonctions de comparaison dans les bornes (ah, nos bon vieux foncteurs...) de faire

Code :

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

b1.eq b2

plutot que

Code :

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

b1.eq b1.value b2.value

Et en plus ça inciterait à utiliser la fonction propre à chaque borne, plutôt que de risquer un

Code :

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

b3.eq b1.value b2.value

qui pourrait éventuellement poser des problèmes en cas d'erreurs.
Mais bon, vu que je suis loin d'avoir lu l'intégralité de la discussion, je raconte peut être n'importe quoi :-D

[alex_pi]

Ca ne devrait pas plutôt être :

Code :

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

1
2
type 'a interval = 'a bound * 'a bound
and 'a bound = { value : 'a; eq : 'a bound -> bool; inf : 'a bound -> 'a bound; sup : 'a bound -> 'a bound }

Effectivement, après avoir un peu plus regardé le code, je me rends compte que c'est génant de ne pas avoir accès aux comparaison direct des valeurs pour pouvoir étendre le type d'intervale qu'on a. Mais je tiens à dire (pour ce que ça vaut :-p) que je trouve ce style très laid :-D

[gasche]

Euh, tu as probablement lu l'intégralité de la discussion qui me concerne en tout cas, puisque je n'ai posté que deux messages sur ce thread.

Code :

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

type 'a bound = { value : 'a; eq : 'a bound -> bool; inf : 'a bound -> 'a bound; sup : 'a bound -> 'a bound }

J'ai choisi l'autre style parce que ces fonctions doivent être apportées par l'utilisateur. De ce fait, il vaut mieux demander les fonctions les plus "simples" et les plus naturelles possibles de son point de vue.

Ainsi, j'ai choisi une fonction de comparaison sur les 'a plutôt que sur les 'a bound : comme toute fonction de comparaison sensée sur les 'a bound dérive d'une fonction de comparaison sur les 'a, il me parît plus naturel de demander à l'utilisateur d'apporter la fonction sur les 'a, et d'en dériver automatiquement la fonction sur les 'a bound, en interne (en substance c'est ce que fait le code de 'intersection').

Ensuite, pour ce qui est de l'utilisation d'un style objet, où "obj.eq" utilise la valeur de obj, je ne suis pas vraiment fan. J'aime bien penser que les bornes stockent à la fois la valeur de l'élément et la structure de l'ensemble ordonné. Avec ce point de vue, je préfère voir la structure le plus clairement possible, plutôt que la déformer par rapport à un élément particulier.
De plus, le fait d'avoir des fonctions élément-agnostiques permet de faire des tests d'égalités sur ces fonctions (iirk !), pour savoir si les bornes utilisent bien la même relation d'ordre.

Et en plus ça inciterait à utiliser la fonction propre à chaque borne, plutôt que de risquer un [...] qui pourrait éventuellement poser des problèmes en cas d'erreurs.

De quelles erreurs parles-tu ? Si c'est du fait de comparer des bornes qui ont été créées à partir d'ordres différents, le problème est toujours présent. Le fait qu'on soit moins poussé à comparer des choses différentes ne garantit rien de plus : la seule chose que les deux modèles imposent c'est que les fonctions de comparaisons utilisent des bornes dont le type de base est le même. Dans tous les cas, il faut je pense des tests au runtime.

(ah, nos bon vieux foncteurs...)

Haha oui, crachons un peu sur ce sale F#. Ceci dit, j'ai en réalité commencé avec des foncteurs (et le design évident en partant de OrderedType), et je me suis retrouvé confronté à un problème quand j'ai voulu faire des produits d'ensembles ordonnés de types hétérogènes (avec l'implémentation que j'avais commencée, ça demandait en gros d'avoir un foncteur prenant un nombre variable de modules en argument). Ceci dit, on peut peut-être faire des foncteurs en utilisant l'approche actuelle de construction des ordres produits au niveau des bornes, et non des intervalles.