Je voudrais représenter une 'file' en ocaml...
Quelqu'un saurait comment ?
 
 

L'intérêt étant d'avoir une file avec une taille non fixée!
But :
Appliquer un traitement à la tête de la file, envoyer le résultat en queue de file, et itérer n fois (avec n fixé).

liste chaînée mutable avec sauvegarde du premier et dernier élément ?

J'ai ca en Scheme si tu veux (la syntaxe est similaire) :
 
C'est meme un generateur de file d'attente avec les operations en O(1)
 

argh... ca fait longtemps que j'ai pas fait de scheme xD
et j'ai l'impression que qd j'avais appris le scheme (dr scheme), y'avait pas de "else" 8-)
=> n'empeche que si je comprenais ça, ce serait super génial... je vais donc tenter qd mm...  
 
quant à la solution d'une liste chainée mutable, je crois que l'énorme défaut là en ocaml, c'est que pour rajouter un élément à la fin d'une liste, il faut parcourir toute la liste... :s
 
si quelqu'un est curieux de savoir pourquoi je veux faire ça, c'est d'une part parce que j'aime bcp OCAML, d'autre part parce que j'ai envie de résoudre un casse-tête...
et enfin parce que ça m'entraine pour l'algo...
 
Pour ce que j'ai déjà fait et que je suis en train de faire : http://mythoughts.free.fr/ocaml/projet_en_cours/
=> pour l'instant, j'ai choisi de représenter la file avec un tableau et 2 entiers pointant l'un sur la tete et l'autre sur la queue...
(avec un tableau initialisé à 1000000 d'éléments...)
(l'accès à un élément du tableau se fasant en temps constant d'après mon prof de caml)

Bon alors aujourd'hui j'ai appris qu'un module pour les files existait déjà... C'est le module "Queue"... Alors comme je n'avais vraiment pas pensé à traduire "File" par "Queue"...
Bon alors un ptit coup d'oeil dans le source... C'est représenté avec un enregistrement un peu bizarre... qui utilise le module Obj (qui n'a rien à voir avec les Objets => module "Oo" )
Bon... Je vais voir si c'est mieux que ma représentation avec un tableau... 8-)

iiiiiiiiiiiiiiiiirk  
 

 
Pourquoi ??? ça fait quoi ?
tu trouves qu'il n'est pas très stable ou quoi ?
c'est vrai que je viens de faire quelques tests dessus, et Obj.magic, c'est vraiment quelque chose de MAGIQUE !
je fais la supposition que le niveau du langage descend qd on utilise Obj.magic...
=> (Obj.magic 1) && true - : bool = true    
=> ca me rappelle le C...  

j'ai aussi re-regardé le source de Queue (queue.ml) ...
bah ça a l'air qd mm assez poussé...
Je fais confiance !
=> donc je reconverti tout ce que j'avais fait avec mon type de file (tout pourri avec un tableau de taille fixe...) en ce type Queue.t qui semble bien plus efficace...

c'est interdit d'utiliser Obj.magic.
 
C'est interdit d'utiliser Obj tout court, parce que sinon, je frappe !

mais dis pk ?!!  

dans le code source  
let create () = {
  length = 0;
  tail = Obj.magic None
}  
=> "Obj.magic None" est utilisé... sans doute parce que l'auteur ne savait pas quoi d'autre mettre dedans

passke c'est mal, c'est même marqué dans la doc :
http://caml.inria.fr/ocaml/htmlman/libref/Obj.html

ah oui c'est vrai
mais comme le module Queue est natif, chuis innocent
Et l'auteur de Queue a le droit
Oh et puis, tant que ca marche, chuis content    
(je n'utiliserai pas Obj, alors ne me frappe paaaaaaas ! oscouuuuuuur   )

j'vais peut-être même te taper préventivement ...

méchant !!!!!!!!!!!!!!
xD
 
dis, tu saurais (par hasard ) ce qui se passe si la taille de la file dépasse max_int ?

tu fais voir le code source stp ?

exception Empty
 
(* O'Caml currently does not allow the components of a sum type to be
   mutable. Yet, for optimal space efficiency, we must have cons cells
   whose [next] field is mutable. This leads us to define a type of
   cyclic lists, so as to eliminate the [Nil] case and the sum
   type. *)
 
type 'a cell = {
    content: 'a;
    mutable next: 'a cell
  }  
 
(* A queue is a reference to either nothing or some cell of a cyclic
   list. By convention, that cell is to be viewed as the last cell in
   the queue. The first cell in the queue is then found in constant
   time: it is the next cell in the cyclic list. The queue's length is
   also recorded, so as to make [length] a constant-time operation.
 
   The [tail] field should really be of type ['a cell option], but
   then it would be [None] when [length] is 0 and [Some] otherwise,
   leading to redundant memory allocation and accesses. We avoid this
   overhead by filling [tail] with a dummy value when [length] is 0.
   Of course, this requires bending the type system's arm slightly,
   because it does not have dependent sums. *)
 
type 'a t = {
    mutable length: int;
    mutable tail: 'a cell
  }
 
Source en entier : http://mythoughts.free.fr/queue.ml

c'est pour gagner de l'espace mémoire qu'il a fait ça, mais c'est pas top
 
Il aurait du faire un  
type 'a MayBe = Some of 'a | None
 
et typer la queue comme ça :
type 'a t = {
    mutable length: int;
    mutable tail: MayBe ('a cell)
  }

ça j'y avais pensé
mais... tu ne m'as pas dit ce qui se passerait si la taille de la file depasse max_int...    
 

heu, j'ai oublié la question ...
J'ai répondu à ce que j'avais envie.
 
'retourne voir et je te dis.

ayé, 'me souviens : ça fait le tour, parce que en o'caml, y'a pas d'exceptions synchrones (la flemme de réexpliquer pourquoi va voir sur la mailing list, X. Leroy l'avait expliqué à propos des réels).
 
http://pauillac.inria.fr/~levy/x/m2/0bis/

mouais...
en tous cas, je pense que la file continue tranquillement sa route, son compteur mutable "length" arrivera du côté des entiers négatifs...
certaines fonctions lèveront l'exception Empty, et d'autres (comme "for" par ex) ne feront pas ce qu'on attendrait d'elles...
bref... en tous cas, je viens de terminer ma conversion (file avec un tableau en file avec Queue), il ne me reste plus qu'à traiter la gestion des fichiers pour stocker mes résultats intermédiaire
(je fais un programme de recherche de toutes les solutions d'un casse-tête, ou peut-être devrais-je l'appeler un "passe-temps"... )
Merci nraynaud, en tous cas