Discussion :

[alex_pi]

Euh non, je n'avais vraiment pas lu, encore désolé...

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) }

Arghl, mais c'est quoi ce hack de bas niveau ? Ca ne coute rien de faire

Code :

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

1
2
3
type 'a open_closed = 
  | Open of 'a
  | Close of 'a

Et comme ça le programmeur n'a pas à retourner au commentaire de la définition du type. Après, effectivement, les deux autres fonctions sont un poil plus lourde à écrire, mais bon..

[gasche]

Ça n'a rien d'un hack. Tu représentes ton type comme 'a + 'a, et moi comme 2 * 'a.

En plus, ma version est mieux. Dans ton cas tu dupliques de l'information (tu précises deux fois que le contenu est de type 'a), et ça a un coût. Par exemple pour appliquer une fonction sur l'élément de type 'a, tu dois faire un filtrage alors que moi je peux y accéder directement (les joies de la factorisation) par "snd", quel que soit le type ouvert/fermé de la borne. Alors certes, on peut recoder une fonction "get" qui aurait le même effet que snd, mais ça c'est un hack. De manière générale, un type somme est adapté pour les types disjoints, alors que moi justement je veux qu'ils ne soient pas trop disjoints pour pouvoir les manipuler pareil (sémantiquement, les deux 'a désignent le même objet, si tu veux).

Ceci dit, le type openclosed actuel ne marche pas : Open et Closed (ou true et false) doivent avoir des comportements différents selon que l'on est sur une borne inférieure ou supérieure, et ce n'est actuellement pas le cas (donc l'intersection est mal implémentée). Je vais voir ce que je peux faire pour corriger ça.

En attendant j'ai refactorisé le truc avec des foncteurs, et je trouve ça plutôt joli :

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
48
49
50
51
52
53
54
55
56
57
58
59
60
module type BoundType = sig
  type t
  val eq : t -> t -> bool
  val inf : t -> t -> t
  val sup : t -> t -> t
end

module SimpleBound (Ord : Set.OrderedType) : BoundType with type t = Ord.t
= struct
  type t = Ord.t
  let make (t : Ord.t) = (t : t)
  let eq a b = Ord.compare a b = 0
  let inf a b = if Ord.compare a b <= 0 then a else b
  let sup a b = if Ord.compare a b >= 0 then a else b
end

type 'a with_infinity = Value of 'a | Min_inf | Max_inf

module WithInfinity (Bound : BoundType) : BoundType
  with type t = Bound.t with_infinity
= struct
  type t = Bound.t with_infinity
  let eq a b = match a, b with
  | Min_inf, Min_inf | Max_inf, Max_inf -> true
  | Value a, Value b -> Bound.eq a b
  | _ -> false
  let inf a b = match a, b with
  | Min_inf, _ | _, Min_inf -> Min_inf
  | Max_inf, t | t, Max_inf -> t
  | Value x, Value y -> Value (Bound.inf x y)
  let sup a b = match a, b with
  | Min_inf, t | t, Min_inf -> t
  | Max_inf, _ | _, Max_inf -> Max_inf
  | Value x, Value y -> Value (Bound.sup x y)
end

module OpenClosed (Bound : BoundType) : BoundType
  with type t = bool * Bound.t
= struct
  type t = bool * Bound.t
  let eq (ta, a) (tb, b) = ta = tb && Bound.eq a b
  let inf (ta, a) (tb, b) = ta && tb, Bound.inf a b
  let sup (ta, a) (tb, b) = ta && tb, Bound.sup a b
end

module Product (A : BoundType) (B : BoundType) : BoundType
  with type t = A.t * B.t
= struct
  type t = A.t * B.t
  let eq (a, b) (a', b') = A.eq a a' && B.eq b b'
  let inf (a, b) (a', b') = A.inf a a', B.inf b b'
  let sup (a, b) (a', b') = A.sup a a', B.sup b b'
end

module Interval (Bound : BoundType) = struct
  type t = Bound.t * Bound.t
  let eq (x, y) (x', y') = Bound.eq x x' && Bound.eq y y'
  let intersection (x, y) (x', y') = Bound.sup x x', Bound.inf y y'
  let includes a b = eq b (intersection a b)
end

Exemple d'utilisation :

Code :

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

1
2
3
4
5
module R_interval = Interval (WithInfinity ( OpenClosed (SimpleBound (struct type t = float let compare = compare end))))

R_interval.intersection (Value (true, 0.), Max_inf) (Value (false, 0.), Value (true, 3.));;
- : (bool * float) with_infinity * (bool * float) with_infinity =
(Value (false, 0.), Value (true, 3.))

C'est pas mal, et ça supprime les problèmes de bornes hétérogènes : on a maintenant une garantie statique que les deux bornes comparées utilisent le même ordre.

[LLB]

C'est pas mal, et ça supprime les problèmes de bornes hétérogènes : on a maintenant une garantie statique que les deux bornes comparées utilisent le même ordre.

Cool !

Mais tu sais, c'est ce qu'on avait déjà avec la solution naïve en F#. Plutôt que de trimbaler partout tes opérations de comparaison et de risquer d'insérer des bugs vicieux si jamais tu appelles par erreur = ou <, F# possède déjà ces comparateurs. C'est transparent et ça fait ce qu'on veut. Ca s'appelle =, <, compare, min, max, etc., c'est fournit par défaut et c'est plus joli que eq, inf et autres bidouilles. Si jamais tu veux utiliser une autre fonction de temps en temps, rien ne t'empêche de définir une classe avec une nouvelle fonction de comparaison. Et comme c'est une nouvelle classe, le compilateur t'empêchera de mélanger des types identiques avec une comparateur différent.

En bref, 75% du code que tu as écrit n'est pas nécessaire, vu qu'on est dans un thread consacré à F# (si, si ).

[Jedai]

En Haskell, sur le même modèle que la dernière proposition de Bluestorm :

Code Haskell :

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
module Interval where
 
data WithInf a = MinInf | Value a | MaxInf
                 deriving (Eq, Ord, Show, Read)
 
data OpenClosed a = OC Bool a -- (Open (True) or Closed (False), value)
    deriving (Eq, Show, Read)
 
open v = OC True v
closed v = OC False v
 
instance Ord a => Ord (OpenClosed a) where
    compare (OC _ v) (OC _ v') = compare v v'
    min (OC oc v) (OC oc' v') = case compare v v' of
                                  EQ -> OC (oc && oc') v
                                  LT -> OC oc v
                                  GT -> OC oc' v'
    max (OC oc v) (OC oc' v') = case compare v v' of
                                  EQ -> OC (oc && oc') v
                                  LT -> OC oc' v'
                                  GT -> OC oc v
 
data Product a b = Prod a b
                 deriving (Eq, Show, Read)
 
instance (Ord a, Ord b) => Ord (Product a b) where
    compare (Prod a b) (Prod a' b') = compare (a,b) (a',b')
    min (Prod a b) (Prod a' b') = Prod (min a a') (min b b')
    max (Prod a b) (Prod a' b') = Prod (max a a') (max b b')
 
type Interval a = (a,a)
 
intersect (i,s) (i',s') = (max i i', min s s')
i1 `includedIn` i2 = i1 == (i1 `intersect` i2)

(Tes inf et sup de ton OpenClosed sont un peu bizarres...)

(NB : Si on veut utiliser un ordre spécial pour les valeurs (pas celui de sa classe Ord), il suffit d'utiliser un newtype (qui sera supprimé à la compilation) avec une classe Ord personnalisée)

--
Jedaï

[gasche]

Sauf que les fonctions de comparaison ne remplacent pas sup et inf.

Par exemple, dans le cas d'un type produit, tu as sup (2, 5) (3, 4) = (3, 5).
Comment tu fais ça avec tes fonctions de comparaison (sans définir le produit inductivement, je veux dire) ?

Alors oui, tu peux aussi faire des classes qui apportent ces opérateurs, mais à ce moment là tu as à priori de nouveau le problème des comparateurs hétérogènes. Comment garantir que les objets que tu manipules ont la même méthode pour inf et sup ?


Jedai > oui, le OpenClosed actuel est flawed, on y travaille :-'
Je me demande si un Closed | OpenRight | OpenLeft ne pourrait pas faire l'affaire (où Closed veut dire "borne inclue" dans tous les cas, OpenRight borne exclue seulement si il est à droite, et closed sinon, et OpenLeft symétrique), mais je ne sais pas encore (et là je fais autre chose).

[LLB]

Par exemple, dans le cas d'un type produit, tu as sup (2, 5) (3, 4) = (3, 5).

En effet, c'est un peu plus compliqué pour ce cas-là (il n'y était pas dans la version de gorgonite).

S'il y a vraiment besoin du type produit et sans réécrire tout le code (comme tu l'as fait), on peut jouer avec l'introspection. Il suffit de tester dynamiquement si les objets possèdent les méthodes Inf et Sup et les appeler. S'il n'y a pas ces méthodes, on appelle la version normale.

OK, au final le code ne sera pas beaucoup plus simple que le tien, mais ça devrait être plus joli pour l'utilisateur.

[gasche]

Mais l'introspection ne résout pas le problème de savoir si les méthodes sont bien les mêmes sur les deux objets, si ?

[gorgonite]

Mais l'introspection ne résout pas le problème de savoir si les méthodes sont bien les mêmes sur les deux objets, si ?

étant donné qu'on peut avoir accès à "l'adresse" de la méthode, ou nom de la classe... je pense que si


Au passage, ceci était censé être une page de code source... on dérive un peu, donc ne vous étonnez pas si je construis d'ici demain matin 2/3 threads avec celui-ci
<hs>
enfin si jamais je réussis à finir mon ****** parseur
</hs>

[LLB]

Non : on a la garantie au moment de la compilation.

Si tu fais une classe qui encapsule un int et possède sa propre méthode de comparaison, le compilateur fera la différence entre les deux (et t'empêchera de les mélanger). L'introspection servirait juste à appeler la méthode Inf ou Sup lorsqu'elle est disponible. J'ai la flemme d'implémenter ça, mais ça semble marcher.

[SpiceGuid]

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

Dans List.for_all2 et List.map2 si les deux listes n'ont pas la même longueur.

[SpiceGuid]

Un TAD tableaux creux fonctionnels.
Implémenté comme un arbre binaire parfait.

L'indice (entier) est décomposé en base 2 puis, de droite à gauche:

• un bit à 0 aiguille le cheminement dans le sous-arbre gauche
• un bit à 1 aiguille le cheminement dans le sous-arbre droit

Les accesseurs get et set sont les composantes d'un enregistrement t_array.

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
(* efficient functionnal array *)
type 'a t =
  | Nil
  | Node of 'a t * 'a * 'a t

type 'a t_array =
  {
  set: int -> 'a -> 'a t_array;
  get: int -> 'a;
  }

let make init =
  let rec make_node node =
    let rec set i v =
      assert(i >= 0);
      let rec helper node i =
        match node with
        | Nil ->
          helper (Node(Nil,init,Nil)) i
        | Node(l,a,r) -> 
          if i = 1 then Node(l,v,r)
          else if i land 1 = 0 then Node(helper l (i asr 1),a,r)
          else Node(l,a,helper r (i asr 1))
      in make_node (helper node (succ i))  
    and get i =
      assert(i >= 0);
      let rec helper node i =
        match node with
        | Nil -> init
        | Node(l,a,r) -> 
          if i = 1 then a
          else if i land 1 = 0 then helper l (i asr 1)
          else helper r (i asr 1)
      in helper node (succ i)  
    in
    {
    set = set;
    get = get;
    }
  in make_node Nil

[gorgonite]

j'ai un GROS doute...

certes je suis très fatigué, mais quand je lis ton code j'ai l'impression que l'argument node de make_node n'est pas utilisé



par ailleurs, le principe d'un tableau est d'avoir un accès en temps constant à un élément... et avec ton arbre binaire, il sera certainement logarithmique
c'est normal ?

[gasche]

Si, il est utilisé par get et set, en tant qu'argument initial à leur fonction "helper' (puique c'est le node courant).

[gorgonite]

Si, il est utilisé par get et set, en tant qu'argument initial à leur fonction "helper' (puique c'est le node courant).

arf, effectivement...

par ailleurs, je n'aime pas la construction let rec set ... and get = ... in qui est normalement destinée pour les fonctions mutuellement récurives (odd / even par exemple). ça peut embrouiller les débutants ^^

[SpiceGuid]

par ailleurs, le principe d'un tableau est d'avoir un accès en temps constant à un élément... et avec ton arbre binaire, il sera certainement logarithmique

Le temps d'accès est proportionnel au nombre de bits de l'indice.
(donc oui logarithmique dans le pire des cas, c'est-à-dire la clé la plus grande)

Cette structure de données est sans doute "inutile", je ne le nie pas, cependant elle me paraît optimale. Je ne vois pas comment obtenir les mêmes propriétés (tableau creux et persistant) en un meilleur temps ou meilleur espace, même avec un style impératif.

[gorgonite]

Cette structure de données est sans doute "inutile", je ne le nie pas, cependant elle me paraît optimale. Je ne vois pas comment obtenir les mêmes propriétés (tableau creux et persistant) en un meilleur temps ou meilleur espace, même avec un style impératif.

ce ne serait pas un peu équivalent aux AVL ?

[NokyDaOne]

par ailleurs, le principe d'un tableau est d'avoir un accès en temps constant à un élément... et avec ton arbre binaire, il sera certainement logarithmique
c'est normal ?

Ça en fait c'est faux. Ce n'est vrai que parce qu'un tableau a une taille limitée. Si l'on veut un tableau de taille potentiellement infinie (en concaténant des barrettes de ram (architecture théorique, vu qu'elle est inutile)) on se retrouve avec un temps d'accès variable.

[SpiceGuid]

NokyDaOne
Effectivement mon tad est non borné (a une taille infinie), on pourrait mettre des Big_int en indice ça ne changerait rien à la complexité.

ce ne serait pas un peu équivalent aux AVL ?

Non, parce que si l'indice était un Big_int alors la comparaison entre deux indices ne se ferait pas en temps constant, au contraire de la lecture du bit suivant.

[InOCamlWeTrust]

Ça en fait c'est faux. Ce n'est vrai que parce qu'un tableau a une taille limitée. Si l'on veut un tableau de taille potentiellement infinie (en concaténant des barrettes de ram (architecture théorique, vu qu'elle est inutile)) on se retrouve avec un temps d'accès variable.

L'accès à un élément de tableau ne suppose aucunement que l'on en connaisse la taille : ce qui en fait l'attrait, c'est que, étant donné un indice i, l'adresse correspondant au ième élément est adresse_de_début_de_tableau + i * taille_des_éléments... à aucun moment on ne suppose connue la taille du tableau, et c'est d'ailleurs pour celà qu'en C, on s'en fout pas mal, parce que tous les tableaux sont potentiellement infinis (comprendre de taille aussi grande que l'on veut) !

Concernant ta concaténation de barettes de RAM, je ne peux que te conseiller de te précipiter urgemment sur le premier chapitre du livre d'O'Reilly expliquant le kernel Linux et les accès mémoire : les explications valent aussi pour tous les autres OS. Ca te permettra d'éviter ce genre de commentaires

[NokyDaOne]

L'accès à un élément de tableau ne suppose aucunement que l'on en connaisse la taille : ce qui en fait l'attrait, c'est que, étant donné un indice i, l'adresse correspondant au ième élément est adresse_de_début_de_tableau + i * taille_des_éléments... à aucun moment on ne suppose connue la taille du tableau, et c'est d'ailleurs pour celà qu'en C, on s'en fout pas mal, parce que tous les tableaux sont potentiellement infinis (comprendre de taille aussi grande que l'on veut) !

Non car ton int est limité à 32 bits ou 64 bits (donc ton tableau n'est en rélité qu'un objet de taille 2^32 (ou 2^64)). SI tu veux un vrai tableau de taille quelconque tu vas devoir passer à des tableaux chainés ou autre.

Concernant ta concaténation de barettes de RAM, je ne peux que te conseiller de te précipiter urgemment sur le premier chapitre du livre d'O'Reilly expliquant le kernel Linux et les accès mémoire : les explications valent aussi pour tous les autres OS. Ca te permettra d'éviter ce genre de commentaires

Je ne comprends pas ta remarque. Quand je parlais de concaténation de RAM, c'était pour pouvoir mettre autant de barrette de RAM que je veux et pouvoir y accéder comme je veux (donc adios los pointeros).