Discussion :

[SpiceGuid]

Ben oui, dans le cas le plus général on ne veut pas limiter l'intervalle d'indices par la taille d'un mot machine. Et dans ce cas l'accès en temps constant est impossible, c'est dans ce sens que mon tad est "optimal" (même si bien entendu en pratique il reste trop médiocre pour un usage réaliste).

[InOCamlWeTrust]

Vous n'avez strictement rien compris ! Mais bon, on ne va pas se battre.

Les choses se passent en machine (CPU) de façon bien différente de ce que vous faites dans vos codes !

[gorgonite]

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.

tout dépend la manière dont tu effectues ta comparaison...
une manière "naïve" et efficace est en effet de passer par une "émulation" d'un entier via des "tableaux chainés", ce qui revient à une complexité logarithme en la taille des paquets
mais je crois qu'il explique des templates de "Big_int" en C++ qui sont mieux faits (à vérifier )

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.

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

Ben oui, dans le cas le plus général on ne veut pas limiter l'intervalle d'indices par la taille d'un mot machine.

ben non justement, qui te dit qu'une adresse n'est représenté que par un mot mémoire...


c'est un peu le problème des "experts" qui affirmaient qu'un programme ne pouvait manipuler plus de 64Ko de mémoire en Ram à l'époque des processeurs 16 bits... et à qui l'on sortait des programmes qui n'utilisaient pas de swap, et qui manipulait près d'1Mo de données

Et dans ce cas l'accès en temps constant est impossible, c'est dans ce sens que mon tad est "optimal" (même si bien entendu en pratique il reste trop médiocre pour un usage réaliste).

si l'on considère que la ram est infinie et que le tableau est mappé dessus, on va arriver à un accès en temps logarithmique
mais pour une machine donnée, on peut toujours sortir une structure manipulant plus de mémoire que l'on peut l'imaginer naïvement, et garder un temps d'accès en O(1)

[alex_pi]

Vous n'avez strictement rien compris ! Mais bon, on ne va pas se battre.

Les choses se passent en machine (CPU) de façon bien différente de ce que vous faites dans vos codes !

Quelle est la proportion de programme où il est important que le codeur ai en tête que l'espace mémoire virtuellement contiguë est en fait découpé en plage physique réparties "n'importe où" en mémoire par l'OS ? Dans quel cas doit il connaître sur le bout des doigt la taille des table de traduction du MMU et les temps typique de l'appel système de mis à jour ? genre 0,01% ? A la rigueur se préoccuper des défaut de page du cache quand on a une matrice bidimensionnelle, pourquoi pas, mais le reste, on s'en fout royalement.

[InOCamlWeTrust]

Quelle est la proportion de programme où il est important que le codeur ai en tête que l'espace mémoire virtuellement contiguë est en fait découpé en plage physique réparties "n'importe où" en mémoire par l'OS ? Dans quel cas doit il connaître sur le bout des doigt la taille des table de traduction du MMU et les temps typique de l'appel système de mis à jour ? genre 0,01% ? A la rigueur se préoccuper des défaut de page du cache quand on a une matrice bidimensionnelle, pourquoi pas, mais le reste, on s'en fout royalement.

Le problème n'est pas là.

Au passage, la fréquence des horloges système ayant augmenté moins vite que celle des CPU (donc ayant baissé, relativement parlant), le phénomène de gruyèrisation de la RAM et donc les problèmes de localité commencent à être de plus en plus pris en compte par les programmeurs, tout simplement parce que les défauts de cache coûtent de plus en plus. Mais c'est un autre débat !

[SpiceGuid]

Le codage en OCaml des entiers de Church-Girard:

Code :

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

1
2
3
type church = {c: 'a.('a -> 'a) -> ('a -> 'a)}
let  zero = {c = fun f x -> x}
let  succ n = {c = fun f x -> f (n.c f x)}

Remarque: ce code ne fonctionne pas en Caml Light, car Caml Light ne possède pas la capacité d'introduire une nouvelle variable de type à l'intérieur de la définition d'un enregistrement.

PS: pour être honnête l'idée de ce code n'est pas de moi, je l'ai "empruntée" à Alain Prouté.

[gasche]

Pourrais-tu expliciter ce qui ne marche pas ? Ça a sûrement à voir avec la conservation du polymorphisme, mais de loin ce n'est pas évident de voir le problème.

En tout cas, à l'utilisation ils sont tout à fait aimables :

Code :

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

1
2
3
4
5
6
7
8
# let rec from_int = function 0 -> zero | n -> succ (from_int (n - 1));;
val from_int : int -> church = <fun>

# let to_int church = church.c ((+) 1) 0;;
val to_int : church -> int = <fun>

# to_int (from_int 8);;
- : int = 8

Edit :
Ah, j'ai compris. "ne fonctionne pas en Caml" ça veut dire "ne fonctionne pas en Caml Light" !
J'ai été induit en erreur par le fait que, pour moi, Caml désigne un langage commun dont Caml Light et OCaml sont deux implémentations un peu différentes (et le passage de Caml Light à OCaml correspond à un ajout de fonctionnalités au langage Caml).

[SpiceGuid]

Ah, j'ai compris. "ne fonctionne pas en Caml" ça veut dire "ne fonctionne pas en Caml Light" !

bien sûr que j'aurais du écrire Caml Light, j'en suis désolé.

[SpiceGuid]

Le fichier joint contient un typeur en ocaml pour le [quizz] fonctions et démonstrations du forum fonctionnel.
Remerciements à Alain Prouté pour m'encourager à utiliser sa contribution.

Ce petit exemple illustre assez bien, sur un langage suffisamment élémentaire, les techniques de base pour l'interprétation en ocaml :

• l'analyse lexicale, y compris sur des opérateurs muti-caractères comme |->
• l'analyse grammaticale descendante récursive LL(1)
• la construction d'un arbre de syntaxe abstraite
• le typage fort
• les messages d'erreurs (lexicales, grammaticales, de nommage, de typage)

Le langage accepté par l'interpréteur ne comprend que les constructeurs de types élémentaires |->, O et W, il ne comprend pas les opérateurs =>, ~, &, |, !, 1! et +.

Pour compiler en code natif:

Code :

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

ocamlopt -o coquelicote lex.ml coquelicote_txt.ml

Un exemple de session (quit. pour quitter) :

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
> coquelicote
Coquelicote Text v0.1
# ?q:O q.
: O
# ?f:O -> O ?x:O f(x).
: O
# q:O |-> x:W(q) |-> x.
: W(?q:O ?x:W(q) q)
# q:W(E) -> W(F) |->
  x:W(E) |->
  q(x).
: W(?q:W(E) -> W(F) ?x:W(E) F)
# f:W(?x:W(E) ?q:O q) |->
  q:O |->
  x:W(E) |->
  f(x)(q).
: W(?f:W(?x:W(E) ?q:O q) ?q:O ?x:W(E) q)
# g:W(?q:O ?x:W(E) q) |->
  x:W(E) |->
  q:O |->
  g(q)(x).
: W(?g:W(?q:O ?x:W(E) q) ?x:W(E) ?q:O q)
# quit.
>

L'archive:

[LLB]

J'ai résolu un petit problème : évaluer une main au poker Hold'em et déterminer le gagnant. Je ne suis pas convaincu que ce soit utile pour quelqu'un, mais ça donne un exemple de code F# (100 lignes).

Je mets juste le lien (pour avoir la coloration syntaxique) :
http://laurent.le-brun.eu/site/index...amming-problem

Il y a des solutions en Ruby disponibles (suivre les liens) et ça pourrait faire un sujet de défi, non ?

[SpiceGuid]

Sympathique le commentaire de Brian Hurt

Du coup j'ai découvert son blog, la série sur les catamorphismes est très intéressante, il contrôle la récursion grâce à des continuations.
Dans mon tutoriel (partie VIII) j'ai simplement utilisé la paresse, c'est suffisant pour arrêter la récursion, mais la généralisation est sans doute intéressante (même sans kung-fu monadique ?).

F# computation expressions are a syntax sugar for writing code where a portion of that code deals with a particular monad.

j'attends toujours mon exemplaire de Monads for dummies.

Sinon, existe-t-il un équivalent F# de http://planet.ocamlcore.org et http://planet.haskell.org ?

( c'est lundi noir, quasiment impossible de poster sur dvp)

[LLB]

Sinon, existe-t-il un équivalent F# de http://planet.ocamlcore.org et http://planet.haskell.org ?

Ce sont juste des collections de flux RSS ? Je connaissais cette page : http://babelnova.net/planet
F# est présent et je suis abonné à ce flux : http://feeds.feedburner.com/planet_fsharp?format=xml

j'attends toujours mon exemplaire de Monads for dummies.

Je peux faire des articles sur l'utilisation des monades en F#. Le mieux pour comprendre est de regarder des exemples d'utilisation, parce que c'est une fonctionnalité assez abstraite dont l'intérêt ne saute pas toujours aux yeux.

[SpiceGuid]

Ce sont juste des collections de flux RSS ? Je connaissais cette page : http://babelnova.net/planet F# est présent et je suis abonné à ce flux : http://feeds.feedburner.com/planet_fsharp?format=xml

Merci, c'est ce que je cherchais.

Pour les monads, il ne manque pas de bons tutoriels, ce qui me manque c'est soit un peu plus de bonne volonté, soit un besoin plus pressant.

[SpiceGuid]

Code OCaml :

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

1
2
3
4
let palindrome s =
  let rec loop min max =
    s.[min] = s.[max] && (min >= max or loop (min+1) (max-1))
  in loop 0 (String.length s -1)

[gasche]

- "or" c'est moche (parce que "and" ne marche pas, et les priorités sont louches), "||" for the win.

- (..+1) (...-1), en fait il n'y a qu'un index qui varie (l' "éloignement par rapport aux bords"), c'est donc un peu redondant

-

# palindrome "";;
Exception: Invalid_argument "index out of bounds".

Code OCaml :

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

1
2
3
4
let palindrome s =
    let max = String.length s - 1 in
    let rec loop k = 2 * k >= max || s.[k] = s.[max - k] && loop (k+1) in
    loop 0

[SpiceGuid]

On défini ici:

1. un type grid (indispensable pour ne pas intervertir lignes et colonnes)
2. le type des expression matricielles
3. quelques opérateurs élémentaires (identité,transposition,somme,produit ordinaire,produit tensoriel) susceptibles d'influer sur la dimension
4. un évaluateur qui renvoie la dimension d'une expression matricielle

Code Caml :

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
type grid =
  {rows: int; columns: int}

type mat_expr =
  | Mat of grid
  | MatUnary of (grid -> grid option) * mat_expr
  | MatBinary of (grid -> grid -> grid option) * mat_expr * mat_expr


let mat_id g = Some g (* négation, puissance, scalaire *)
let mat_trans g = Some {rows=g.columns;columns=g.rows}

let mat_sum g1 g2 = if g1 = g2 then Some g1 else None  
let mat_product g1 g2 = Some {rows=g1.rows;columns=g2.columns}
let mat_tensorial g1 g2 = Some g1


let rec mat_size mat_expr = 
  match mat_expr with
  | Mat g ->
      Some g
  | MatUnary(f,m) ->
      ( match mat_size m with
      | Some g -> f g
      | None -> None )
  | MatBinary(f,m1,m2) ->
      ( match mat_size m1,mat_size m2 with
      | Some g1,Some g2 -> f g1 g2
      | None,_ -> None
      | _,None -> None )

L'opposé d'une matrice et la puissance entière d'une matrice ne sont pas gérées car, du point du vue des dimensions, ces opérations sont similaires à l'identité.

Le produit d'Hadamard de deux matrices n'est pas géré car, du point du vue des dimensions, cette opération est similaire à l'addition.

Exemple:

Code Caml :

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

1
2
3
4
# let grid x y = {rows=y;columns=x}
  in  mat_size (MatBinary(mat_product,Mat(grid 2 3),Mat(grid 4 2)))
  ;;
- : grid option = Some {rows = 3; columns = 4}

[So.Ta]

Voici plusieurs façons de (re)coder la fonction reverse qui permet d'inverser tous les éléments d'une liste qu'on lui passe en argument.

• Récursion simple
  

  Code :

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

  1
  2
  3
  4
   (define (rev ls)
      (if (null? ls)
          ls
          (append (rev (cdr ls)) (cons (car ls) '()))))

• A l'aide d'un accumulateur
  

  Code :

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

  1
  2
  3
  4
   (define (rev ls acc)
      (if (null? ls)
          acc
          (rev (cdr ls) (cons (car ls) acc))))

  Note : Avec cette méthode, on doit, en plus de la liste, passer en argument la valeur de l'accumulateur.
  Par exemple :
  

  Code :

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

  1
  2
  3
  4
  > (rev '(1 2 3) '())
  (3 2 1)
  > (rev '(1 2 3) '(4 5 6))
  (3 2 1 4 5 6)

• Récursion terminale (tail-rec)
  

  Code :

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

  1
  2
  3
  4
  5
  6
   (define (rev ls)
      (define (rev-append ls acc)
        (if (null? ls)
            acc
            (rev-append (cdr ls) (cons (car ls) acc))))
      (rev-append ls '()))

  Ou alors en faisant simplement un appel à rev-append afin de la rendre réutilisable :
  

  Code :

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

  1
  2
  3
  4
  5
  6
  (define (rev-append ls acc)
     (if (null? ls)
         acc
         (rev-append (cdr ls) (cons (car ls) acc))))
  
  (define (rev ls) (rev-append ls '()))

• Récursion simple avec valeur de l'accumulateur en argument optionel
  Note : Je ne sais pas si il existe un véritable "opérateur" permettant de mettre des arguments optionnels dans le Scheme standard. Si vous faites du MIT/GNU Scheme renseignez-vous sur l'opérateur #!optional .
  

  Code :

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

  1
  2
  3
  4
  5
  6
  7
  8
  9
   (define (rev ls . acc)
      (let ((acc
             (if (pair? acc)
                 (car acc)
                 '())
             ))
        (if (null? ls)
            acc
            (rev (cdr ls) (cons (car ls) acc)))))

[Trap D]

Tu as oublié (mais c'est peut-être volontaire) la définition avec fold, tirée de la doc en ligne

Code :

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

1
2
3
(define reverse
    (lambda (l)
      (foldl cons '() l)))

[Garulfo]

[...]
Note : Je ne sais pas si il existe un véritable "opérateur" permettant de mettre des arguments optionnels dans le Scheme standard. Si vous faites du MIT/GNU Scheme renseignez-vous sur l'opérateur #!optional .[...]

Tout interpréteur Scheme conforme au R6RS (et même aux RxRS) accepte le point comme indicateur de paramètres optionnels.

http://www.r6rs.org/final/html/r6rs/...ode_sec_11.4.2

[So.Ta]

Trap D> J'ai omis l'utilisation de foldl volontaire car je ne connais pas cette fonction.

Garulfo> En parlant de "véritable" opérateur (bien que ici, la formulation est loin du sens que je voulais lui donner), je voulais dire un opérateur permettant de donner une valeur par défaut de manière plus simple qu'à coups de let.