Version imprimable
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).
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 !
tout dépend la manière dont tu effectues ta comparaison...Citation:
Envoyé par SpiceGuid
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 ;))
Citation:
Envoyé par NokyDaOne
ben non justement, qui te dit qu'une adresse n'est représenté que par un mot mémoire...Citation:
Envoyé par SpiceGuid
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 :aie:
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 ;)Citation:
Envoyé par SpiceGuid
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)
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.Citation:
Envoyé par InOCamlWeTrust
Le problème n'est pas là.Citation:
Envoyé par alex_pi
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 !
Le codage en OCaml des entiers de Church-Girard:
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.Code:
2
3type 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)}
PS: pour être honnête l'idée de ce code n'est pas de moi, je l'ai "empruntée" à Alain Prouté.
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 :
Edit :Code:
2
3
4
5
6
7
8
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).
:oops: bien sûr que j'aurais du écrire Caml Light, j'en suis désolé.Citation:
Ah, j'ai compris. "ne fonctionne pas en Caml" ça veut dire "ne fonctionne pas en Caml Light" !
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:
Un exemple de session (quit. pour quitter) :Code:ocamlopt -o coquelicote lex.ml coquelicote_txt.ml
L'archive:Code:
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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 ?
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 ?).
:aie: j'attends toujours mon exemplaire de Monads for dummies.Citation:
Envoyé par Brian
Sinon, existe-t-il un équivalent F# de http://planet.ocamlcore.org et http://planet.haskell.org ?
(:aie: c'est lundi noir, quasiment impossible de poster sur dvp)
Ce sont juste des collections de flux RSS ? Je connaissais cette page : http://babelnova.net/planetCitation:
F# est présent et je suis abonné à ce flux : http://feeds.feedburner.com/planet_fsharp?format=xml
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.Citation:
j'attends toujours mon exemplaire de Monads for dummies.
Merci, c'est ce que je cherchais.Citation:
Envoyé par LLB
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.
Code:
2
3
4let 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)
- "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
-Citation:
# palindrome "";;
Exception: Invalid_argument "index out of bounds".
Code:
2
3
4
On défini ici:
- un type grid (indispensable pour ne pas intervertir lignes et colonnes)
- le type des expression matricielles
- quelques opérateurs élémentaires (identité,transposition,somme,produit ordinaire,produit tensoriel) susceptibles d'influer sur la dimension
- un évaluateur qui renvoie la dimension d'une expression matricielle
Code:
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
31type 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:
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}
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:
2
3
4(define (rev ls) (if (null? ls) ls (append (rev (cdr ls)) (cons (car ls) '()))))
- A l'aide d'un accumulateur
Note : Avec cette méthode, on doit, en plus de la liste, passer en argument la valeur de l'accumulateur.Code:
2
3
4(define (rev ls acc) (if (null? ls) acc (rev (cdr ls) (cons (car ls) acc))))
Par exemple :
Code:
2
3
4
- Récursion terminale (tail-rec)
Ou alors en faisant simplement un appel à rev-append afin de la rendre réutilisable :Code:
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 '()))
Code:
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:
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)))))
Tu as oublié (mais c'est peut-être volontaire) la définition avec fold, tirée de la doc en ligne
Code:
2
3(define reverse (lambda (l) (foldl cons '() l)))
Tout interpréteur Scheme conforme au R6RS (et même aux RxRS) accepte le point comme indicateur de paramètres optionnels.Citation:
Envoyé par So.Ta
http://www.r6rs.org/final/html/r6rs/...ode_sec_11.4.2
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.