Discussion :

[Alp]

Bonsoir,

Après quelques recherches, je ne trouve pas de bibliothèques/modules relatifs à l'IA en OCaml. Je chercherais même éventuellement des choses plus générales, permettant l'utilisation de stats et probas en OCaml... Cela existe-t-il ? Car je ne trouve rien de concluant.

[gorgonite]

déjà que la librairie standard manque de fonctionnalités basiques, comment peux-tu espérer avoir plus ?


en cherchant avec cet outil ?
http://caml.inria.fr//cgi-bin/hump.en.cgi

on trouve des trucs
algo genetique : http://thelackthereof.org/wiki.pl/OGPF

[Alp]

Bon si j'ai bien compris faudra que j'écrive tout ça moi-même.

[SpiceGuid]

t'as tout compris, c'est le meilleur langage pour l'écrire toi-même.

déjà que la librairie standard manque de fonctionnalités basiques, comment peux-tu espérer avoir plus ?

C'est particulièrement flagrant dans un module aussi basique que List où tu n'as même pas une fonction qui retourne le dernier élément, et les fonctions qui sont présentes lèvent une exception au lieu de renvoyer un type option.
Et je ne parle même pas du module String

[gasche]

C'est particulièrement flagrant dans un module aussi basique que List où tu n'as même pas une fonction qui retourne le dernier élément

Je comprends que tout le monde n'aie pas la même opinion que moi à ce sujet, mais je trouve que proposer sciemment une opération en O(N) dans une structure de donnée qui n'est clairement pas appropriée, c'est inciter ses utilisateurs à faire n'importe quoi. Empiriquement, j'observe que les utilisateurs des langages qui le font (eg. Python) ont plus tendance à faire n'importe quoi que les camleux.

Alp > il y avait à une époque des bindings pour le langage R, que je ne connais pas mais qui a l'air spécialisé dans les stats. Peut-être que, si ton mode d'utilisation le permet, ce serait un bon choix (faire les calculs statistiques à l'intérieur d'un sous-langage spécialisé) ?

[Garulfo]

Je comprends que tout le monde n'aie pas la même opinion que moi à ce sujet, mais je trouve que proposer sciemment une opération en O(N) dans une structure de donnée qui n'est clairement pas appropriée, c'est inciter ses utilisateurs à faire n'importe quoi. Empiriquement, j'observe que les utilisateurs des langages qui le font (eg. Python) ont plus tendance à faire n'importe quoi que les camleux.

Je suis d'accord avec toi sur ce point. De plus, si tu veux accéder à la fin de ta liste en permanence c'est un signe que tu n'as pas choisi la bonne structure de données me'semble.

Et le choix de renvoyer des exceptions est aussi cohérent vis-à-vis de l'implémentation des exceptions qui sont en OCaml fait pour être utilisés dans ce but, contrairement à Java/C++ et autre consort.

Tout ceci ne me stresse pas. Mais il est vrai qu'OCaml manque de bibliothèque cependant.

[Alp]

Je comprends que tout le monde n'aie pas la même opinion que moi à ce sujet, mais je trouve que proposer sciemment une opération en O(N) dans une structure de donnée qui n'est clairement pas appropriée, c'est inciter ses utilisateurs à faire n'importe quoi. Empiriquement, j'observe que les utilisateurs des langages qui le font (eg. Python) ont plus tendance à faire n'importe quoi que les camleux.

Ce point de vue me semble assez pertinent. Et personnellement, je ne reproche rien au module List. Ayant une forte tendance C++, je suis habitué à devoir aller voir ailleurs que la bibliothèque standard (pour le moment ) voir même à devoir faire les choses moi-même. Je souhaitais juste ne pas passer à côté d'un module existant et qui remplirait le rôle que je souhaite.

Alp > il y avait à une époque des bindings pour le langage R, que je ne connais pas mais qui a l'air spécialisé dans les stats. Peut-être que, si ton mode d'utilisation le permet, ce serait un bon choix (faire les calculs statistiques à l'intérieur d'un sous-langage spécialisé) ?

Il faudra que je me renseigne sur l'intéraction OCaml<->R mais ça peut être une piste... Surtout que je vois de plus en plus de personnes utiliser ce langage et il semble de plus être "fait pour" ce genre d'utilisation.

Merci tout le monde

[LLB]

mais je trouve que proposer sciemment une opération en O(N) dans une structure de donnée qui n'est clairement pas appropriée, c'est inciter ses utilisateurs à faire n'importe quoi.

Je suis plutôt d'accord, mais faudrait-il alors supprimer List.nth ? Cette fonction sert rarement, mais je n'ai pas non plus envie de la recoder, si jamais je dois accéder à un élément précis.

Je suis d'accord, une fonction last est vraiment peu utile ; il manque des fonctions plus importantes à mon goût (List.init, List.take, List.takewhile, beaucoup de fonctions sur les strings, en commançant par fold, que l'on retrouve dans extlib).

[gasche]

Je suis plutôt d'accord, mais faudrait-il alors supprimer List.nth ? Cette fonction sert rarement, mais je n'ai pas non plus envie de la recoder, si jamais je dois accéder à un élément précis.

Oui, je pense qu'on pourrait retirer List.nth. Je ne me souviens pas m'en être servi, et si par hasard tu en avais besoin rapidement pour un script ou quoi, let nth li = Array.get (Array.of_list li), ça ne mange pas de pain.

Pour les init/take et autres (filters sur les tableaux, etc.), une approche que je trouve plus intéressante est de passer toutes ces fonctions dans une structure de donnée commune, où elles seraient centralisées (Enum dans Extlib). Si la structure commune est performante, ça peut être efficace (moins efficace que les même hardcodées, mais dans la plupart des cas on peut perdre un peu en performance si on gagne beaucoup en généralité), tout en minimisant le travail sur chaque lib et en maximisant les mises en commun.

[Jedai]

Je comprends que tout le monde n'aie pas la même opinion que moi à ce sujet, mais je trouve que proposer sciemment une opération en O(N) dans une structure de donnée qui n'est clairement pas appropriée, c'est inciter ses utilisateurs à faire n'importe quoi.

C'est une question de choix, mais de temps en temps on est content d'avoir last ou nth et franchement si tu n'as pas confiance en tes programmeurs au point de craindre qu'ils n'utilisent last trop souvent, supprime aussi length parce que là pour le coup c'est une opération en O(n) qu'un tas de gens utilisent souvent sans se rendre compte du coût... Et puis supprime aussi fold_right parce que c'est pas récursif terminal, et puis de toute façon toutes ces fonctions d'ordre supérieur sont moins efficace que de récrire le processus avec des récursions de base en OCaml donc tu devrais juste toute les supprimer aussi, non ?

Sérieusement ? Et puis :

Code :

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

nth li = Array.get (Array.of_list li)

Me dis pas que c'est implémenté comme ça dans la stdlib ? Tu demandes le 10ème élément d'une liste de 100000 et pouf tu dois te taper l'allocation et la désallocation de 100000 éléments, non merci...

--
Jedaï

[SpiceGuid]

Oui, je pense qu'on pourrait retirer List.nth. Je ne me souviens pas m'en être servi, et si par hasard tu en avais besoin rapidement pour un script ou quoi, let nth li = Array.get (Array.of_list li), ça ne mange pas de pain.

du coup je comprends mieux pourquoi tu n'as pas besoin de last :

Code :

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

let last l = List.hd (List.rev l)

[alex_pi]

du coup je comprends mieux pourquoi tu n'as pas besoin de last :

Code :

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

let last l = List.hd (List.rev l)

C'est la même complexité hein

[Garulfo]

[...]supprime aussi length parce que là pour le coup c'est une opération en O(n) qu'un tas de gens utilisent souvent sans se rendre compte du coût... [...]
Jedaï

Est-ce le cas dans l'implémentation d'OCaml ? En Scheme par exemple, length est une primitive qui donne la taille en temps constant. Ainsi, on peut en abuser. La philosophie de Scheme est de dire que les listes étant la base de la plupart des structures de données en fonctionnel, les opérations fournies sont toutes ou presque optimisée. Je n'ai jamais cherché pour voir si c'était optimisé ou non en OCaml.

[alex_pi]

Est-ce le cas dans l'implémentation d'OCaml ? En Scheme par exemple, length est une primitive qui donne la taille en temps constant. Ainsi, on peut en abuser. La philosophie de Scheme est de dire que les listes étant la base de la plupart des structures de données en fonctionnel, les opérations fournies sont toutes ou presque optimisée. Je n'ai jamais cherché pour voir si c'était optimisé ou non en OCaml.

Non, une liste est un type comme un autre. Length est en O(n) , nth pareil. Ils sont écrits dans la lib standard comme n'importe qui l'écrirait. directement.

C'est toujours difficile de faire des choix comme celui d'optimiser length. Effectivement, l'avoir en O(1), c'est plus rapide, mais ça augmente la taille (mémoire) des liste de 50%. Donc on y perd quand même pas mal de ce coté là.

[Jedai]

Est-ce le cas dans l'implémentation d'OCaml ? En Scheme par exemple, length est une primitive qui donne la taille en temps constant. Ainsi, on peut en abuser. La philosophie de Scheme est de dire que les listes étant la base de la plupart des structures de données en fonctionnel, les opérations fournies sont toutes ou presque optimisée. Je n'ai jamais cherché pour voir si c'était optimisé ou non en OCaml.

Ce n'est pas "optimisé" :

Code OCaml :

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

1
2
3
4
5
let rec length_aux len = function
    [] -> len
  | a::l -> length_aux (len + 1) l
 
let length l = length_aux 0 l

(list.ml)

Mais il faut voir que les listes en Scheme sont une structure "magique" à la base de toutes les autres alors qu'en OCaml ou en Haskell les listes ne sont qu'un type somme parmi d'autres, parfaitement ordinaire si on excepte quelques excentricités de syntaxe (surtout la notation [a, b, c], en Haskell c'est la seule chose qui les distingue).

Par ailleurs, généralement "length" n'est pas tellement utilisé par les programmeurs fonctionnels expérimentés, ou alors c'est que les listes simples n'étaient pas le bon choix de structure de donnée (encore une fois cela ne s'applique pas vraiment aux "listes" de Scheme/Lisp, qui sont fort différentes).

--
Jedaï

[gasche]

Il me semble que si on a "length" en O(1), alors on a forcément un "cons" plus lent : en OCaml, cons c'est juste une allocation, donc très rapide. Si on maintient un invariant de taille, j'ai l'impression que quel que soit le degré d'"optimisation" de l'implémentation, tu vas avoir du travail en plus pour le maintenir après le cons (par exemple l'accès à un champ "taille", puis ajout d'un à une variable).

Dans un contexte d'utilisation "usuelle" des listes, on utilise _beaucoup_ cons (c'est l'opération à la base de toutes les primitives construisant des listes comme map/filter etc..), et assez peu length. Il me semble donc justifié de privilégier un cons rapide à un length en O(1), dans la plupart des cas. Dans les autres, rien ne t'empêche de construire tes propres listes avec tailles :

Code :

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

1
2
3
4
5
type 'a lenlist = { lenght : int; list : 'a cell }
and 'a cell = ('a * 'a lenlist) option
 
let nil = { length = 0; list = None }
let cons x xs = { length = succ xs.length; list =  Some (x, xs) }

[Garulfo]

[...]
C'est toujours difficile de faire des choix comme celui d'optimiser length. Effectivement, l'avoir en O(1), c'est plus rapide, mais ça augmente la taille (mémoire) des liste de 50%. Donc on y perd quand même pas mal de ce coté là.

Il me semble que si on a "length" en O(1), alors on a forcément un "cons" plus lent :[...]

C'est étrange vos remarques. Pour avoir un length en O(1) il me semble qu'il suffit d'avoir un structure de donnée { taille:int, elements:listes } comme le propose bluestorm. Un cons est certes un tantinet plus lent puisqu'il doit en plus ajouter 1 à la taille et la mémoire est un peu plus grande mais pas forcément de 50% quand même. Tout dépendant de ce qu'on met dedans. Non ? Alors oui on peut faire les siennes à la main. Mais c'est quand même agréable de ne pas avoir à tout refaire. L'overhead n'est quand même pas énorme là. Je ne sais pas comment ils les ont implémentés exactement en Lisp/Scheme, mais à mon avis l'optimisation doit être suffisamment pertinente pour qu'elle soit resté au bout des nombreuses révisions.

Maintenant je suis d'accord avec Jedaï sur le fait que la liste est la base de tout en Scheme ce qui explique le choix. J'aime leurs nouvelles décisions d'avoir pris de base des listes non mutables. Avant c'était un peu merdique.

[gasche]

Si tu dois stocker la taille pour chaque paire dans ta liste, alors le surcoût mémoire est effectivement de 50%. On pourrait imaginer de stocker uniquement la taille en tête de liste, mais ça augmente encore un peu plus le prix en temps, puisque l'opération "tail" devient plus coûteuse.

Je pense qu'il n'y a pas de vraie bonne solution pour avoir des listes et "length" en O(1). J'ai été suffisamment convaincu pour aller vérifier, et je crois qu'en fait le "length" du Scheme n'est pas O(1) :
- ce n'est pas naturel
- ce n'est pas dans le standard (ou alors je n'ai pas trouvé), ni dans aucune documentation que j'aie trouvé
- ça ne correspond pas à ce que je suis allé chercher dans les sources de deux compilateurs Scheme :

Chicken :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
C_regparm C_word C_fcall C_pair(C_word **ptr, C_word car, C_word cdr)
{
  C_word *p = *ptr,
         *p0 = p;
 
  *(p++) = C_PAIR_TYPE | (C_SIZEOF_PAIR - 1);
  *(p++) = car;
  *(p++) = cdr;
  *ptr = p;
  return (C_word)p0;
}

"Pair" (ie. cons) sans manipulation de taille.

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
C_regparm C_word C_fcall C_i_length(C_word lst)
{
  int n = 0;
 
  if(lst != C_SCHEME_END_OF_LIST) {
    if(!C_immediatep(lst) && C_block_header(lst) == C_PAIR_TAG) {
      do {
        lst = C_u_i_cdr(lst);
        ++n;
      } while(!C_immediatep(lst) && C_block_header(lst) == C_PAIR_TAG);
    }
    else barf(C_BAD_ARGUMENT_TYPE_ERROR, "length", lst);
  }
 
  return C_fix(n);
}

"length" en O(N)


Stalin :

Code :

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

1
2
3
    (define (list-length list)          ;Extension to R4RS.
     (let loop ((k 0))
      (cond ((null? list) k) (else (set! list (cdr list)) (loop (+ k 1))))))

(je n'ai pas trouvé le code pour pair/cons, il est caché par une primitive "make-structure" horriblement compliquée et optimisante)

[SpiceGuid]

Oui, je pense qu'on pourrait retirer List.nth. Je ne me souviens pas m'en être servi

Ça mérite quand même d'y revenir un instant.
Tu nous dis quel "pattern" tu utilises et, plaisanterie à part, je respecte ton style.
Seulement je pense qu'il y a d'autres styles possibles, d'autres façons d'atteindre la même qualité, ou bien encore d'autres cheminements (qui peuvent passer par des étapes plus naïves) pour y parvenir.
Je pense comme Jedaï, qu'une fonction inefficace n'est pas un piège pour le débutant, le débutant qui ne commence pas par écrire match l with est perdu quelque soit la manière, ce n'est pas en lui enlevant des tentations qu'on va le sauver.

Et le choix de renvoyer des exceptions est aussi cohérent vis-à-vis de l'implémentation des exceptions qui sont en OCaml fait pour être utilisés dans ce but, contrairement à Java/C++ et autre consort.

Les exceptions c'est la façon impérative de traiter les erreurs, et parfois ça manque de composabilité sémantique.
Quand tu dois unifier deux listes de termes et que List.map2 unify l1 l2 lève une exception Invalid_argument (listes de longueur différentes) au lieu de te renvoyer None ça te paraît beaucoup moins cohérent (avec ta sémantique).

Là encore c'est une question de style, je conçois très bien que pour d'autres usages celà fasse sens que List.map2 lève une exception. Mais c'est à moi qu'il revient d'en décider, au cas par cas, pas à quelqu'un qui aurait déjà choisi son camp.

[alex_pi]

Quand tu dois unifier deux listes de termes et que List.map2 unify l1 l2 lève une exception Invalid_argument (listes de longueur différentes) au lieu de te renvoyer None ça te paraît beaucoup moins cohérent (avec ta sémantique).

Là encore c'est une question de style, je conçois très bien que pour d'autres usages celà fasse sens que List.map2 lève une exception. Mais c'est à moi qu'il revient d'en décider, au cas par cas, pas à quelqu'un qui aurait déjà choisi son camp.

En même temps, dans une lib standard, il faut bien prendre des décisions. Le seul moyen d'éviter les décisions d'autrui, c'est de tout recoder soit même... :-\
Et sinon.

Code :

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

1
2
3
 
let my_map2 f l1 l2 = 
  try Some (List.map2 f l1 l2) with | Invalid_argument _ -> None