Discussion :

[BlueJack]

Cacophrene pardonne moi j'avais oublié de dire que dans le livre ou j'ai lu l'explication il l'appliquai à l'addition! Donc là pour essayé mon code j'ai utilisé l'addition!

Je note f pour fonction et ini pour valeur quelconque? x pour tête et tail pour queue?
Merci encore de votre aide, cela motive à progresser et je reprend l'habitude d'ouvrir un cahier de brouillon afin de chercher pour résoudre le problème. C'est aussi très important.

[Cacophrene]

Re !

Je note f pour fonction et ini pour valeur quelconque? x pour tête et tail pour queue?

Oh là non c'est pas aussi rigide que ça Tu peux utiliser les conventions que tu veux, surtout si elles aident à comprendre à quoi servent les variables.

Ce qui est sûr, c'est que les variables d'une seule lettre sont généralement problématiques et doivent donc être limitées à un contexte local, sinon le code perd vite en lisibilité (en OCaml et partout ailleurs). Parmi les notations qui font presque consensus, il y a f pour fonction, ce qui suit d'ailleurs la notation mathématique (avec f, puis g, h...).

Seule chose certaine : puisqu'on peut écrire des noms de variables de plusieurs lettres, autant ne pas s'en priver (sans tomber dans le travers des noms_très_longs_sans_aucun_intérêt_pour_comprendre_à_quoi_ça_sert). C'est un peu comme l'indentation. Il n'y a pas de règle absolue, mais plutôt des habitudes plus ou moins répandues.

Cordialement,
Cacophrène

[BlueJack]

A ce niveau là aurais tu des conseils sur l'indentation en OCaml?
Car cela ne se présente pas du tout comme un programme en C par exemple ou j'indentais mes blocks d'une tabulation généralement.

Merci encore

[gasche]

A ce niveau là aurais tu des conseils sur l'indentation en OCaml?

Tu trouveras un grand nombre de conseils, indications et discussions dans les Guidelines Caml. Il ne faut pas les prendre comme des règles absolues, mais c'est certainement un bon début.


Sinon, si tu veux continuer sur les listes et la récursion, tu peux essayer de coder les autres fonctions du module List (URL donnée plus haut). Tout n'est pas obligatoire et certaines sont moins intéressantes que les autres (tu peux sauter celles qui ont l'air vraiment identiques à celle d'avant), mais ça reste amusant.

Question subsidiare : comment coder "rev" sans écrire de fonction récursive, en utilisant la fonction myFold/fold_left que tu as définie ?

[BlueJack]

Je vais étudier le guidelines cette nuit.
Pour ta question subsidiaire je dois t'avouer que je block totalement dessus. Depuis tout à l'heure je suis dessus et je n'en fini pas de faire des croquis. Je continue de chercher!

Auriez vous des conseils sur quoi m'entrainer après les listes?

[tydaldus]

Je vais étudier le guidelines cette nuit.

Sinon une autre solution encore pour voir comment indenter et présenter du code caml c'est de lire du code caml écrit par d'autres programmeurs, tu peux en trouver dans le Hump dans la catégorie "Native OCaml libraries" ou dans les différentes catégories "Applications written in Caml" : [1], [2], [3], [4], [5], [6].

Pour ta question subsidiaire je dois t'avouer que je block totalement dessus. Depuis tout à l'heure je suis dessus et je n'en fini pas de faire des croquis. Je continue de chercher!

Si tu souhaites continuer de chercher ne lie pas la solution ci-dessous, sinon si tu en as marre de t'arracher les cheveux voici la solution, ce n'était pas très compliqué. En programmation fonctionnelle la fonction List.fold_left est très importante donc je te conseillerais de t'exercer à l'utiliser.

Code :

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

1
2
3
4
5
let rev li =
  List.fold_left (fun acc v -> v::acc) [] li
 
# rev [1; 2; 3; 4] ;;
- : int list = [4; 3; 2; 1]

Avec l'application partielle tu peux même écrire :

Code :

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

let rev = List.fold_left (fun acc v -> v::acc) [] ;;

Auriez vous des conseils sur quoi m'entrainer après les listes?

Ce que tu pourrais faire c'est d'essayer de réaliser les exercices donnés sur le site www.rosettacode.org sans regarder la solution ocaml, puis quand tu as réussis comparer ta version à celle qui est sur la page.

Tu peux aussi compulser le Pleac OCaml. D'ailleur à ce niveau aussi ce que tu peux faire c'est lorsque tu croises une fonction non tail-récursive la réécrire, comme par exemple la fonction split_every_n_chars donnée sur cette page.

Tu peux aussi essayer de réimplémenter (sans toutes les options) certaines commandes de la ligne de commande courantes comme wc, tail, tree... (pour tree par exemple tu trouveras une base ici)

Tout celà devrait te faire avoir d'autres questions, alors n'hésites pas à revenir les poser sur ce forum !

[BlueJack]

Merci pour tout vos conseils.
J'ai essayer de faire la fonction qui retourne le maximum d'une liste d'entiers positifs.

Code :

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

1
2
3
4
5
let rec max_of max l = 
 match l with
 |[] -> max 
 |h::q -> if h > max then max_of h q
          else max_of max q;;

Ce qui nous donne:

Code :

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

1
2
max_of 0 [1;2;24;5;6;7];;
- : int = 24

Je me demande si il n'y aurait pas moyen de le faire avec un fold_left et un acc.
J'ai essayé dans ce style:

Code :

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

1
2
let max_of max = 
 List.fold_left (fun acc l -> if l > acc then acc = l) max l;;

Sans résultat.

[Cacophrene]

Salut !

J'ai essayé de faire la fonction qui retourne le maximum d'une liste d'entiers positifs

Ton code est bon mais on peut souhaiter ne pas avoir à passer le minimum (zéro) à chaque appel. Pour cela tu peux imbriquer les fonctions :

Code :

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

1
2
3
4
5
6
let max_of =
  let rec loop res = function
    | [] -> res
    | x :: t -> loop (if x > res then x else res) t
  in loop 0

Cela amène deux remarques générales à propos de caml :

• if ... then ... else peut être utilisé comme un opérateur ternaire, n'importe où dans le code.
• Dans le code ci-dessus, max_of est une fonction car loop 0 est une application partielle. En effet, loop attend deux arguments en entrée. Si je ne lui en donne qu'un, le résultat est une fonction à un argument. C'est un exemple de curryfication (mais c'est peut-être un peu tôt pour en parler davantage et tu peux ne pas y prêter d'attention tout de suite).

Je me demande s'il n'y aurait pas moyen de le faire avec un fold_left

C'est un bon réflexe car, effectivement, les fonctions de type fold (= replier, enrouler) servent précisément à ça. D'ailleurs max_of est une version spécialisée de List.fold_left.

Pour fixer les idées, fold_left f ini l calcule f (... (f (f ini l0) l1) ...) ln où l1, l2, ..., ln désignent les éléments de la liste l. Examinons la signature de la fonction List.fold_left pour comprendre son fonctionnement :

Code :

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

val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a

• Le premier argument de fold_left est une fonction f qui reçoit deux arguments en entrée : le premier est un résultat intermédiaire, et le second un élément de la liste. Elle renvoie elle-même un résultat intermédiaire, ce qui permet, de proche en proche, d'obtenir le résultat final.

• Le second argument de fold_left sert à appeler f avec le premier élément de la liste, lorsqu'aucun résultat intermédiaire n'est disponible. Lorsque f est un opérateur comme ( + ) ou ( * ), cet argument est presque toujours l'élément neutre associé (c.-à-d. 0 et 1, respectivement).

• Enfin, fold_left reçoit la liste à partir de laquelle le calcul doit être effectué.

Où est le problème dans ton code ? D'abord, la condition if foo then bar est synonyme de if foo then bar else (). Cela signifie que bar doit être de type unit, or ton code indique acc = l qui est de type bool. Le message d'erreur que tu as dû obtenir en testant ton code dans le toplevel est en rapport avec ça, sans pousser l'analyse plus loin. Bon, en ce qui me concerne, je présume que tu voulais modifier acc. Je te rappelle qu'il n'est pas possible de procéder ainsi en OCaml.

En fait, cette première erreur masque le vrai problème. La fonction passée à fold_left n'est pas correcte puisque ce n'est pas un booléen qu'on veut obtenir, mais la valeur du maximum, autrement dit un entier. Il suffit pour cela de se servir de la condition du code précédent :

Code :

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

if x > res then x else res

Ce qui donne :

Code :

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

let max_of = List.fold_left (fun res x -> if x > res then x else res) 0

Ci-dessous une réécriture de la version sans fold_left de max_of qui fait encore plus ressortir la ressemblance :

Code :

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

1
2
3
4
5
6
let max_of =
  let rec loop f res = function
    | [] -> res
    | x :: t -> loop f (f res x) t
  in loop (fun res x -> if x > res then x else res) 0

Un exemple déroulé à la main pour la liste [1; 9; 5], en se concentrant sur la fonction f passée à fold_left :

Code :

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

1
2
3
4
5
6
7
 
f 0 1 -> if 1 > 0 then 1 else 0
  Renvoie 1
f 1 9 -> if 9 > 1 then 9 else 1
  Renvoie 9
f 9 5 -> if 5 > 9 then 5 else 9
  Renvoie 9

Cordialement,
Cacophrène

[BlueJack]

Merci pour ta réponse:

Code :

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

if ... then ... else peut être utilisé comme un opérateur ternaire, n'importe où dans le code

Merci pour cette information extrêmement importante car je ne l'avais toujours pas bien enregistré. C'est pour cela que j'ai essayé avec acc = l.

Wikipedia à propos de la curryfication:

En programmation fonctionnelle, la curryfication désigne l'opération qui fait passer d'une fonction à plusieurs arguments à une fonction à un argument et qui retourne une fonction qui prend le reste des arguments.

Je dois t'avouer que j'ai du mal à comprendre.

Code :

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

let max_of = List.fold_left (fun res x -> if x > res then x else res) 0

C'est uniquement la première fois que fold_left prend 0?

Merci de ton soutient.

[Jedai]

Tu peux également décomposer ta solution en plusieurs fonctions, c'est une façon de faire qui est encore plus efficace et raisonnable en Haskell, mais c'est tout de même déjà applicable en OCaml ou autre langage fonctionnel :

Code OCaml :

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

1
2
3
4
5
let max x y = if x > y then x else y
 
let maximum = function
  | []     -> failwith "maximum of an empty list\n"
  | h :: t -> List.fold_left max h t

(tu remarqueras que j'ai un peu modifié le sens de maximum, pour qu'elle marche mieux avec une liste de nombres négatifs, par exemple)

J'ai choisi ce langage pour essayer de faire un petit projet sur du sequençage de molécule d'ADN, et d'autres projets en biologie.

Dans cette optique, tu as intérêt à utiliser une librairie qui gère les formats et algorithmes courants dans ce domaine, OCaml a eu quelques tentatives dans ce champ, mais aucune ne semble très active actuellement. Par comparaison, Haskell, un langage relativement similaire à OCaml (encore que plus orienté fonctionnel pur et à évaluation paresseuse) dispose d'un certain nombre de librairies bioinformatiques, dont certaines activement entretenues et capables. Éventuellement ça peut t'inspirer, même si Haskell n'a pas l'heur de te plaire.

--
Jedaï

[Cacophrene]

Salut !

Tu peux également décomposer ta solution en plusieurs fonctions, c'est une façon de faire qui est encore plus efficace et raisonnable en Haskell

Je pense que c'est une bonne habitude de programmation, ne serait-ce que pour augmenter la lisibilité du code, indépendamment des considérations d'efficacité.

@BlueJack> Quand tu parles d'un projet en rapport avec le séquençage d'ADN, tu comptes faire quoi ? Chercher des séquences (ORF putatives, sites de coupure par des endonucléases, îlots CpG, etc.), faire de l'alignement, etc. ? C'est clair que selon tes besoins tu risques de passer longtemps à coder toi-même les algorithmes faute de bibliothèque dédiée (attention : ce n'est pas un mal en soi, mais cela dépend du temps dont tu disposes, de ta motivation, des performances que tu souhaites atteindre, et de bien d'autres choses encore).

En gros si tu veux faire un clone de pDraw tu ne devrais pas rencontrer trop de difficultés. En revanche si tu veux faire une sorte de BLAST ou pire ClustalW... ce sera moins facile. Sans parler des outils de visualisation de protéines à partir des fichiers PDB, bien entendu

Cordialement,
Cacophrène

[BlueJack]

Merci Jedai pour ta réponse très intéressante. J'aimerais réagir sur le domaine de la biologie. Penses tu qu' Haskell serait plus intéressant dans ce domaine de part son nombre de bibliothèques? Car cela est le master que je vais prendre l'année prochaine (bioInfo).

EDIT: J'aimerai travailler sur l'alignement de séquence en me basant sur l'algorithme de Needleman-Wunsch pour le moment. Etant donné que je débute en fonctionnel, je commencerai par des choses plus simples bien entendu ( pcr & co ).

Merci!

[Jedai]

Wikipedia à propos de la curryfication:

En programmation fonctionnelle, la curryfication désigne l'opération qui fait passer d'une fonction à plusieurs arguments à une fonction à un argument et qui retourne une fonction qui prend le reste des arguments.

Je dois t'avouer que j'ai du mal à comprendre.

Reprenons l'exemple de max :

Code :

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

let max x y = if x > y then x else y

Contrairement à l'impression erronée que tu as probablement, ce max n'est pas une fonction à deux arguments... Pour avoir une fonction à deux arguments, similaire à la façon dont max est défini dans la plupart des autres langages, il faudrait écrire :

Code :

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

let max (x,y) = if x > y then x else y

Comparons les types de ces deux fonctions (pour simplifier on fixera le type manipulé à int, bien que max soit en fait polymorphe), la seconde version a le type :

Code :

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

val max : (int, int) -> int

C'est un type qui ressemble pas mal à ce que tu peux voir dans d'autres langages : max prend deux entiers en argument et renvoie un entier.

Maintenant la première version :

Code :

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

val max : int -> int -> int

En fait il y a des parenthèses implicites dues à l'associativité de (->) :

Code :

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

val max : int -> (int -> int)

Dans cette version, max est donc une fonction qui prend un entier en argument et renvoie une deuxième fonction qui prend un entier en argument et renvoie un entier...

En fait notre premier code aurait pu être écrit :

Code :

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

let max x = fun y -> if x > y then x else y

et dans la plupart des langages qui supporte les fonctions anonymes c'est ainsi qu'il aurait dû être écrit, la notation initialement employée n'est qu'un sucre syntaxique offert par OCaml pour écrire plus facilement des fonctions curryfiée.

En effet, toute fonction à plusieurs arguments peut-être soumise à cette même transformation en fonction à un argument qui renvoie une fonction et cette forme curryfiée présente de nombreux avantages, dont le fait qu'elle rende très facile l'application partielle d'une fonction pourvu que l'ordre des arguments s'y prête. Par exemple, si on veut corriger une liste d'échantillon en ramenant ceux qui sont trop bas à une valeur minimale, on peut écrire avec la fonction curryfiée :

Code :

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

let newSamples = List.map (max 5) samples

Alors qu'avec la version "classique" de max, il faut utiliser une fonction anonyme :

Code :

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

let newSamples = List.map (fun y -> max (5,y)) samples

Le gain est minimal dans ce cas, mais en favorisant la définition de fonction curryfiées par défaut grâce à son sucre syntaxique, OCaml favorise en fait un style de programmation plus orienté vers la manipulation de fonctions et les fonctions d'ordre supérieur (qui prenne des fonctions en paramètre, comme fold_left), un style fonctionnel en bref !

--
Jedaï

[Jedai]

Merci Jedai pour ta réponse très intéressante. J'aimerais réagir sur le domaine de la biologie. Penses tu qu' Haskell serait plus intéressant dans ce domaine de part son nombre de bibliothèques? Car cela est le master que je vais prendre l'année prochaine (bioInfo).

EDIT: J'aimerai travailler sur l'alignement de séquence en me basant sur l'algorithme de Needleman-Wunsch pour le moment. Etant donné que je débute en fonctionnel, je commencerai par des choses plus simples bien entendu ( pcr & co ).

Disons qu'avoir quelques bibliothèques de base au moins pour la lecture et la manipulation des formats employés en BioInformatique te permet d'aborder sereinement et directement la partie algorithmique (la partie intéressante donc...) du domaine, donc je compterai effectivement l'existence de la bibliothèque "bio" en Haskell comme un avantage. Je dois mentionner que "bio" contient au moins trois implémentations de Needleman-Wunsh (deux avec raffinements), apparemment très courtes (bien qu'incompréhensibles pour toi pour l'instant, je n'en doute pas), par exemple la version standard :

Code Haskell :

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

1
2
3
4
5
6
7
-- | Calculate alignments.
global_align :: (Num a, Ord a) => SubstMx t a -> a -> Sequence t -> Sequence t -> EditList
global_align mx g s1 s2 = reverse . snd . last . last 
                          $ columns (g_align mx g) (0,[]) s1 s2
 
g_align :: (Num a, Ord a) => SubstMx t a -> a -> Selector (a,EditList)
g_align mx g cds = maximumBy (compare `on` fst) [(s+eval mx g e,e:a) | ((s,a),e) <- cds]

Ce code utilise principalement des fonctions standards d'Haskell, les seuls fonctions provenant de "bio" étant eval() et columns(). Je n'essaierais pas de commenter le code plus avant, la bioinformatique n'étant pas du tout mon domaine, je dirais juste qu'il s'agit là de code Haskell typique : les lignes avec "::" sont des signatures de types (non nécessaire comme en OCaml, mais souvent rajoutées à titre de documentation) et les fonctions elles même sont des compositions ((.) est l'opérateur de composition, souvent appelé "rond" comme dans "f rond g" en Mathématiques) de fonctions simples.

--
Jedaï

[BlueJack]

Me conseillerais tu alors de me rediriger vers Haskell? Il est vrai que les bibliothèques de base me seront très utiles notamment à la fac (cela serait une perte de temps de devoir tout refaire à la main alors que la bibliothèque ferme à 19h! (bien que je travaille à longueur de temps chez moi)). Merci pour vos réponses très complètes.

[LLB]

Pour ma part, je te conseillerais de te renseigner dans des milieux bio-informatiques, plutôt qu'ici. Comme tu ne maitrises ni Caml, ni Haskell, il est encore envisageable de changer de langage (ce que tu as appris jusqu'ici te sera tout de même utile). Utiliser les même outils que tes collègues et bénéficier des bibliothèques testées par beaucoup de monde te sera plus utile que les détails du langage (inférence de type, application partielle et "oh ! c'est fonctionnel"). Même si le langage en lui-même est moins bien, je pense que tu gagneras quand même du temps.

Renseigne-toi donc dans ces milieux pour voir les alternatives sérieuses qu'on te propose. Ensuite, si tu hésites, on pourra te conseiller l'autre ou l'autre des choix. Pour ma part, je ne serai pas surpris si tu te diriges vers Perl (il y a même des livres "Beginning Perl for Bioinformatics" et "Mastering Perl for Bioinformatics") ou Java.

[BlueJack]

Je regarde tout ça merci beaucoup!
Je ne connais pas du tout PERL et je vois sur wikipédia qu'est c'est fonctionnel. Avez vous des avis sur ce langage? Avantages, inconvénient par rapport à OCaml ou Haskell par exemple? Je lis sur le net que Python est en train de surpasser PERL. Est ce le cas en bio info?

[Jedai]

Je regarde tout ça merci beaucoup!
Je ne connais pas du tout PERL et je vois sur wikipédia qu'est c'est fonctionnel. Avez vous des avis sur ce langage? Avantages, inconvénient par rapport à OCaml ou Haskell par exemple? Je lis sur le net que Python est en train de surpasser PERL. Est ce le cas en bio info?

Qualifier Perl (pas tout en majuscules) de fonctionnel est un peu excessif... Disons que cela fait partie des paradigmes qu'il est capable d'utiliser, parmi d'autres plus présent en général (Impératif procédural et POO). Python supporte aussi le style fonctionnel mais de façon encore plus limité que Perl.

Ces deux langages sont aussi nettement moins performants que Haskell ou OCaml dans l'état actuel des choses (souvent il y a même un ordre de magnitude de différence), lesquels sont à peu près comparable sur ce plan et compétitifs par rapport à des langages de plus bas niveau comme le C/C++ ou Java.

Je ne saurais trop dire ce qu'il en est dans le monde de la bioInformatique en particulier, ce n'est pas mon domaine et je n'ai pas essayé toutes les solutions. Il est certain que tu trouveras plus de ressources, plus éprouvées (pas toujours d'excellente qualité néanmoins) dans des langages plus mainstream (C/C++, Java, Perl, Python...), mais si tu cherches à rester dans les langages fonctionnels alors OCaml et surtout Haskell sont sans doute plutôt bien adaptés. Mon sentiment par rapport à ce monde c'est que sa mentalité est encore très "bricolo" avec des librairies et des scripts relativement fragiles et ad-hoc et pas toujours dans des langages aussi performants que le domaine d'application paraîtrait le justifier, dans cette optique, le choix d'Haskell m'apparaît comme intéressant si tu es capable de maîtriser le langage, il t'offrira sans doute des avantages par rapport à la plupart de tes collègues.

--
Jedaï

[Cacophrene]

Salut !

Mon sentiment par rapport à ce monde c'est que sa mentalité est encore très "bricolo" avec des librairies et des scripts relativement fragiles et ad-hoc et pas toujours dans des langages aussi performants que le domaine d'application paraîtrait le justifier

+1000.
Un joli script en R de 2000 "petites" lignes sans aucune indentation ni documentation associée, avec comme en-tête "Useful R script".

Cordialement,
Cacophrène

[BlueJack]

J'ai déjà fais un peu de Python et du Java en cours. Par conséquent je vais commencer à regarder le Haskell grâce a tes arguments assez convaincants (comment ça se fait que le python est utilisé dans ces domaines alors que le temps d'éxecution n'est pas tip top à ce que j'ai entendu dire)