Défi N°1 : Génération des ensembles de nombre dont la somme est identique

[millie]

Bonjour,

Pour ce premier défi, l'équipe de developpez.com vous propose un challenge assez simple pour débuter.

Le problème étant le suivant :

Challenge :
Soit un entier n en entrée,
Déterminer tous les ensembles de nombre entier positif dont la somme vaut n.

Par exemple pour 5, tous les ensembles de nombre dont la somme vaut 5 sont :

• 5
• 4 1
• 3 2
• 3 1 1
• 2 2 1
• 2 1 1 1
• 1 1 1 1 1

A noter que l'on souhaite des ensembles, il n'y a donc pas de doublon (on a une seule fois (3,2), et pas : (3,2) et (2,3) par exemple).

Il n'y a pas de règle sur le format de sortie. Le format standard pour les langages fonctionnels pourra par exemple être une liste de liste :
[[5], [4,1], [3,2], [3,1,1], [2,2,1], [2,1,1,1], [1,1,1,1,1]]

Pour un langage impératif, la sortie pourra simplement être écrite sur la sortie standard.


Les règles

Il n'y a pas de règle particulière (évidemment, il faut que la solution proposée fonctionne). Vous pouvez proposer des solutions aussi bien dans des langages fonctionnels (caml, haskell, scheme, lisp...) qu'impératif. Le public pourra ainsi juger du code suivant divers critères :

• la maintenabilité
• la simplicité
• le fait qu'il soit optimisé

Le public pourra également juger les différences entre une solution fonctionnelle et une solution impérative. Il lui sera ainsi plus facile de voir, pour un même problème, les différences entre divers paradigmes.

Pour répondre, il vous suffit de poster à la suite.

A vos claviers
de votre participation.

__________________________
Sujet proposé par Jedaï

[LLB]

Solution en F# :

Code F# :

1
2
3
4
5
let sums n =
  let rec sumrec = function
   | 0, _ -> [[]]
   | n, m -> [for i in 1 .. min n m ->> [for j in sumrec((n - i), i) -> i :: j]]
  sumrec(n, n)

Exemple d'appel :

Code :

1
2
3
> sums 5;;
val it : int list list
= [[1; 1; 1; 1; 1]; [2; 1; 1; 1]; [2; 2; 1]; [3; 1; 1]; [3; 2]; [4; 1]; [5]]

[Jedai]

Effectivement, c'est l'algorithme le plus naturel à mon avis, et les "list comprehension" permettent de l'exprimer de façon compacte :

Code Haskell :

1
2
3
4
sums n = csums n n
    where
      csums 0 _ = [[]]
      csums n m = [x:xs | x <- [1..min n m], xs <- csums (n-x) x ]

J'explique la solution :
On utilise une fonction auxiliaire csums() qui prend deux paramètres n et m et renvoie la liste des ensembles de nombres inférieurs à m dont la somme est n.
Cette fonction marche de la façon suivante :
Si n = 0, on considère que l'ensemble vide est la seule solution (dans ce problème on n'utilise pas le 0 dans les solutions, sinon il y en aurait une infinité), d'où le :

Code :

csums 0 _ = [[]]

(le _ peut reconnaître n'importe quoi, on ne se soucie pas de la valeur de m dans ce cas)
Sinon si n > 0 (on ne vérifie pas ici à vrai dire, mais la structure de la fonction fait que si n < 0, elle renverra [], la liste vide, ce qui est correct), alors on utilise un générateur de liste par compréhension, qui ressemble beaucoup à une définition d'ensemble en mathématiques.
En gros la définition mathématiques correspondante serait :
ensemble des "x suivi de xs" tels que x appartient à l'ensemble des entiers de 1 au minimum de n et m et xs appartient à l'ensemble des ensembles de nombres inférieurs à x dont la somme est (n - x).

Code :

csums n m = [x:xs | x <- [1..min n m], xs <- csums (n-x) x ]

le (:) rajoute x au début de la liste xs, vous pouvez voir <- comme "appartient à", et [a..b] signifie "l'ensemble des entiers de a à b" (ça marche aussi avec les autres types énumérables).
En notation mathématique :


Cette algorithme s'appuie donc sur une récursion dont le cas de base est n = 0, ce qui est correct puisqu'à chaque appel récursif le n est diminué mais reste supérieur ou égal à 0. De plus il génère des listes triées dans l'ordre décroissant, ce qui évite les doublons.

--
Jedaï

[Trap D]

Une solution Prolog, simple mais pas optimisée puisqu'elle balaie toutes les solutions, le nettoyage se faisant par un tri puis une élimination des doublons avec le setof.

Code :

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
32
% le Predicat d'appel
% N : le nombre a decomposer
% L : la liste des décompositions possibles
decomposition(N, L) :-
	% le setof permet la collecte de tous les resultats
        % et le nettoyage des doublons
	setof(L1, une_decomposition(N,L1), L).

% Le predicat qui fournit une decomposition en somme 
% N : le nombre a decomposer,
% L : la liste resultat triee dans l'ordre naturel croissant
une_decomposition(N, L) :-
	% Le predicat central qui cree la decomposition en somme
	% N  : le nombre à decomposer
	% LN : la liste resultat
	somme(N, LN), 
	% tri de la liste obtenue
	msort(LN, L).

% La condition d'arret du prédicat recursif somme
% Le nombre 0 possède une decomposition vide.
somme(0, []) :- !.


somme(N, [N1 | LN]) :-
	% on prend un nombre quelconque entre 1 et N
	% premier élément de la liste résultat
	between(1, N, N1),
	N2 is N - N1,
	% on complete la liste résultat avec la décomposition
	% du complément à N du premier nombre
	somme(N2, LN).

[Jedai]

Les plus exigeants d'entre vous auront peut-être remarqué que pour l'instant aussi bien ma solution que celle de LLB répètent inutilement certains appels à la fonction auxiliaire (csums dans mon cas, sumrec dans le cas de LLB) durant la récursion... Ces appels pourraient être éliminés en mémorisant les résultats intermédiaires.

Voici une solution utilisant cette optimisation en Haskell :

Code Haskell :

1
2
3
4
5
6
sums n = a ! (n,n)
    where
      a = array ( (0,0), (n, n) ) 
          $ ( (0,0), [[]] ) : populateList
      populateList = [( (k,l), [x:xs | x<-[1..l], xs<-a!(k-x, min (k-x) x)] )
                          | k<-[1..n], l<-[1..k]]

a est un tableau (array), ou plutôt une matrice, dont les indices vont de (0,0) à (n,n) (le premier argument de la fonction array donne les bornes de ses indices), et dont les valeurs sont données par la liste associative en second argument.
Une liste associative est une liste de paire (a,b) où a est la clé et b la valeur associée à la clé. Si (a,b) se trouve dans la liste associative, le tableau produit par array() aura la valeur b à l'indice a.
Ici tout le travail est effectué dans cette liste associative : à l'indice (k,l) (pour k variant de 1 à n et l variant de 1 à k), elle associe le résultat de csums k l, sauf qu'au lieu d'appeler récursivement une fonction, elle récupère directement les résultats intermédiaires dont elle a besoin dans le tableau a...

Nous voyons ici l'une des force d'Haskell puisque la définition du tableau a utilise le tableau a. Ceci n'est possible que grâce à la paresse d'Haskell, qui ne calcule une valeur que s'il en a besoin. En conséquence de quoi, les éléments de ce tableau a ne sont calculés qu'à partir du moment où on les utilises, ce qui est le cas lorsqu'on demande "a ! (n,n)" (l'équivalent de a[n][n] ou a[n,n] dans d'autres langages). L'ordre des éléments dans la liste associative n'a aucune importance (bien qu'ici ils soient "dans le bon ordre" par pure coïncidence, cela n'a aucune influence sur l'ordre d'exécution).

Cette version bien que légèrement plus compliquée (mais néanmoins tout à fait abordable puisque j'ai écris cette fonction en moins d'une minute), a des performances très nettement supérieur à la précédente.

Je précise que cette fonction reste complètement dans le paradigme fonctionnel, d'ailleurs le tableau a est fonctionnel puisque immuable.

--
Jedaï

PS : Certains d'entre vous auront peut-être remarqué que la moitié du tableau reste inoccupée et inutile. Il est facile de remédier à cela en définissant un nouveau type Pair x y où x >= y et en en faisant une instance de la type class Ix (Index), mais il s'agit là de sujets avancés d'Haskell, qui ne relèvent pas vraiment du sujet.

[gorgonite]

Une implémentation "triviale" en OCaml... histoire de donner un exemple

Code :

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
32
33
let rec build_list n m = if n>m then [] else n::(build_list (n+1) m);;

let rec sumrec n =
	match n with
		0 -> [[]]
		|1 -> [[1]]
		|n -> 
			let intervalle = build_list 1 (n-1) in
			List.concat 
				(List.map 
					(fun i -> List.map 
							(fun l -> (n-i)::l) 
							(sumrec (n-i))) 
					intervalle)
;;

let rec print_list l =
	match l with
		[] -> ()
		|a::q -> Printf.printf "%d " a ; print_list q
;;

let rec print lst = 
	match lst with
		[] -> ()
		|a::q -> Printf.printf "[ " ; print_list a ; Printf.printf "] \n" ; print q
;;

let main () =
	print (sumrec (int_of_string Sys.argv.(1)))
;;

main ();;

nb: seule la fonction en gras est nécessaire... mais le reste vous permettra de le compiler, de l'exécuter et de visualiser le résultat tel quel



la complexité temporelle est exponentielle en le premier argument, et l'occupation mémoire l'est aussi (mais c'est le problème qui le veut ) => j'arrive à calculer jusqu'à 17 puis stack overflow

si j'ajoutais la mémorisation des résultats précedemment calculer (on se sert en effet de toutes les valeurs de sumrec i pour 0<i<n pour calculer sumrec n), le temps de calcul serait linéaire, mais la mémoire exploserait plus tot

[LLB]

Gogonite > j'ai testé ton code, mais ça marche pas vraiment (ou y a un truc que j'ai pas compris ?).

Code :

1
2
3
$ ocaml sum.ml 3
[ 2 1 1 ]
[ 1 1 ]

Si certains veulent tester ma version F#, il faut ajouter "#light" (pour prendre en compte l'indentation) et ajouter à la fin la ligne :

Code :

Sys.argv.(1) |> int_of_string |> sums |> print_any

Pour l'explication de mon code, je renvoie à celle de Jedai : c'est la même chose (des list comprehensions).

[Jedai]

Bon, en dehors de quelques petits problèmes dans la fonction (genre (n-i) à la place de i), quelques remarques :

la complexité temporelle est exponentielle en le premier argument, et l'occupation mémoire l'est aussi (mais c'est le problème qui le veut ) => j'arrive à calculer jusqu'à 17 puis stack overflow

Comme on cherche les ensembles et non les n-uplets, la complexité n'est pas aussi catastrophique que ça... Et de mon côté j'arrive à calculer au moins jusqu'à 70 (en 12 secondes en interprété pour ma fonction utilisant un tableau, elle utilise à peu près 500 Mo de RAM). Mais bien sûr ta fonction trouve les n-uplet, elle, ce qui effectivement est nettement plus méchant...
De mon côté j'ai la fonction suivante pour les n-uplets, elle monte jusqu'à 24 en 18 secondes (toujours en interprété) et avec 500 Mo de RAM au moins d'occupé... Là je n'ose pas la pousser plus loin ! (on notera bien sûr que pour 24, il y a 2^23 n-uplets solutions, l'occupation en RAM est plutôt honnête et même étrange, compte tenu que cela fait 8_388_608 liste de longueur moyenne 12.5... Autrement dit 104857600 * 8 octets (en espérant que les Int soient boxés, ce qui en mode interprété Haskell n'est pas probable)... Impossible n'est-ce pas (cela fait déjà plus de 500 Mo) ? Nous y reviendrons).

Code Haskell :

nsums = [[]]:[[x:xs | x <- [1..n], xs <- nsums !! (n - x) ] | n <- [1..]]

Ma fonction n'en est pas une, c'est une liste infinie (mais paresseuse, donc tout va bien ne vous inquiétez pas). Pour trouver l'ensemble des n-uplets de nombres dont la somme est 24, il suffit de regarder au 24ème indice de cette liste :

Code :

nsums !! 24

( liste !! 0 renvoie le premier élément d'une liste, tableau ! i renvoie la valeur à l'indice i d'un tableau en Haskell)

Mais la mémoire devrait éclater avec toutes les listes intermédiaires, non ? En fait il y a un "truc" (dont devrait aussi bénéficier Gorgonite, c'est pourquoi je suis étonné qu'il ait un problème à 17 éléments), réfléchissez bien !!


--
Jedaï

[Jedai]

La fonction de Gorgonite en Haskell (ou du moins sa copie conforme, l'algorithme est strictement le même) :

Code :

1
2
nsums 0 = [[]]
nsums n =  concatMap (\m -> map (m:) $ nsums $ n-m) [1..n]

le $ est l'opérateur d'application, autrement dit il fait la même chose que l'espace, "f $ x" est strictement équivalent à "f x", mais son intérêt réside en sa très faible priorité (la plus faible de tous les opérateurs Haskell), qui permet de se passer de parenthèses dans nombre de cas, comme ici autour de "sums $ n-m" et de "n-m". Pour ceux qui ont fait du shell, vous pouvez voir ça comme un pipe à l'envers : "n-m" passe à "sums", qui passe à "map (m:)".

Cette fonction est légèrement plus lente que la liste infinie et occupe à peu près autant de place.

--
Jedaï

[Jedai]

Puisque tout le monde mets une version compilable de son programme, je vais en mettre une également :

Code Haskell :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
module Main where
import System -- pour getArgs
import Data.Array

main = do
  argv <- getArgs
  print $ sums $ read $ argv !! 0

-- ou si vous préférez le style "point-free" (autrement dit sans variable)
-- main = getArgs >>= print . sums . read . (!! 0)

sums n = a ! (n,n)
    where
      a = array ( (0,0), (n, n) ) 
          $ ( (0,0), [[]] ) : populateList
      populateList = [( (k,l), [x:xs | x<-[1..l], xs<-a!(k-x, min (k-x) x)] )
                          | k<-[1..n], l<-[1..k]]

Notez bien que cette version ne pourra pas vous servir de benchmark : tout ce que vous mesurerez c'est la vitesse des IO sur votre console... Rajoutez plutôt un length après le print si vous voulez mesurer les vitesses d'exécution.

read() est une fonction qui prend une chaîne en argument et essaie de la parser de façon à produire le type exigé par le contexte (ici il s'agit de Int).

--
Jedaï

[gasche]

> Mais la mémoire devrait éclater avec toutes les listes intermédiaires, non ?
> En fait il y a un "truc" (dont devrait aussi bénéficier Gorgonite, c'est
> pourquoi je suis étonné qu'il ait un problème à 17 éléments), réfléchissez
> bien !!

Le 'truc' me semble être le partage implicite des listes.

Comme tu travailles sur une liste paresseuse, si pour deux mêmes valeurs de (n - x), la liste renverra bien le même élément (physique), il y aura donc partage des queues de liste.

Cependant, je pense que contrairement à ce que tu dis, Gorgonite n'en profite pas :

Code :

List.map (fun l -> (n-i)::l) (sumrec (n-i))

Les listes l (au passage, mes yeux te remercieraient de mettre "li" la prochaine fois, gorgonite) ne sont pas les mêmes à chaque application de cons, il n'y a pas de partage (et les têtes sont dupliquées).
Pour obtenir un partage des listes, il faudrait construire la fonction "à l'envers", en passant (n-i) en argument supplémentaire à sumrec, comme on le fait pour les fonction tail-récursives, afin qu'il l'ajoute au *fond* de toutes les listes générées, où il pourrait effectivement être partagé.
(En gros, ses listes formes un arbre implicite, mais dans le mauvais sens : il faut le retourner, pour que la racine coincide avec les queues des listes)

[gasche]

Histoire de vérifier ces histoires de partage, j'ai fait le test sur mon ordinateur.

Voici ma version, que j'espère "avec partage".
Attention, j'ai aussi fait joujou avec la syntaxe, histoire de (re)voir à quel point on pouvait faire aussi rigolo que père Curry. Je suis assez satisfait.

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
open List

let ( @$ )f x = f x
let ( @@ ) f g x = f @$ g x

let seq n = Array.to_list @$ Array.init n @$ ( + ) 1

let sumrec = 
  let rec sumrec fond = function
    0 -> [fond]
  | 1 -> [1::fond]
  | n -> concat @$ map (fun i -> sumrec ((n - i) :: fond) (n - i)) @$ seq (n - 1)
  in sumrec []

let () = 
  iter (print_newline @@ iter @$ Printf.printf "%d\t") @$ sumrec @$ read_int ()

Sur mon ordinateur, compilé en natif, avec comme entrée "21", cette version met 10 secondes, alors que la version de gorgonite en met 14. Ma version consomme 43 Mo de mémoire, celle de gorgonite en demande 100.

Je dois avouer que je suis un peu décu, je m'attendais à des résultats plus différents encore. Je dois avoir raté quelque chose.

[LLB]

Envoyé par Jedai

Les plus exigeants d'entre vous auront peut-être remarqué que pour l'instant aussi bien ma solution que celle de LLB répètent inutilement certains appels à la fonction auxiliaire (csums dans mon cas, sumrec dans le cas de LLB) durant la récursion... Ces appels pourraient être éliminés en mémorisant les résultats intermédiaires.

Tout à fait.

Et juste pour exemple, j'ai traduit le code de Jedai en F# : (fichier complet et exécutable)

Code :

1
2
3
4
5
6
7
8
9
#light
let sums n =
  let rec a = Array2.init (n+1) (n+1) populate
  and populate k l =
    lazy if k = 0 then [[]]
         else [for x in 1 .. min k l ->> [for xs in a.[k-x, x].Force() -> x :: xs]]
  a.[n,n].Force()

Sys.argv.(1) |> int_of_string |> sums |> print_any

Populate est le nom de la fonction d'initialisation du tableau. L'opérateur |> correspond en gros au pipe du Shell (donc, le $ de Haskell à l'envers ). Et comme on fait de la paresse alors que le langage est strict par défaut, il faut appeler la méthode Force (et le mot-clé "lazy").

Utiliser l'évaluation paresseuse n'est pas dans mes habitudes, et je n'y aurais probablement pas pensé sans Jedai, mais je suis plutôt satisfait du résultat. Le code n'est finalement pas trop compliqué.

(Évidemment, les solutions données pour OCaml fonctionnent aussi bien sous F#)

[gasche]

Je trouve d'ailleurs qu'un tableau est plus adapté qu'une liste pour une solution de mémoization générique comme utilisé ici (évidemment, la définition récursive de la liste est très élégante, et si on a besoin de calculer sums plusieurs fois de suite la solution est bien meilleure).

En écrivant concatMap à la main (et oui, pas de déforestation chez nous :p), la consommation mémoire passe à 33 Mo, soit trois fois moins que la version intiale.

(Évidemment, les solutions données pour F# fonctionnent aussi bien sous OCaml)

[Jedai]

Envoyé par bluestorm

> Mais la mémoire devrait éclater avec toutes les listes intermédiaires, non ?
> En fait il y a un "truc" (dont devrait aussi bénéficier Gorgonite, c'est
> pourquoi je suis étonné qu'il ait un problème à 17 éléments), réfléchissez
> bien !!

Le 'truc' me semble être le partage implicite des listes.

Tout à fait, le partage implicite des listes rend cette liste infinie moins chère temporairement que la fonction type Gorgonite (effectivement tu as raison, il n'y a pas partage dans son cas, non plus qu'avec ma fonction équivalente d'ailleurs).

Malheureusement la fonction de bluestorm donne des résultats fantaisistes... pour l'instant.

--
Jedaï

[Jedai]

Envoyé par bluestorm

Je trouve d'ailleurs qu'un tableau est plus adapté qu'une liste pour une solution de mémoization générique comme utilisé ici (évidemment, la définition récursive de la liste est très élégante, et si on a besoin de calculer sums plusieurs fois de suite la solution est bien meilleure).

Vu la taille réelle que pourra atteindre cette liste, j'ai jugé qu'une liste était parfaitement appropriée et puis une liste infinie c'est quand même nettement plus beau qu'un tableau, même fonctionnel, et comme tu le dis, c'est surtout approprié si on a besoin de refaire le calcul très souvent, sinon on localise la mémoization à une seule invocation.

Envoyé par bluestorm

(Évidemment, les solutions données pour F# fonctionnent aussi bien sous OCaml)

Hmm... Il n'y a pas de compréhension de liste sous OCaml, je ne suis pas sûr non plus que la paresse y soit implémenté exactement de la même façon (quoique ça soit probable), il va donc falloir modifier un peu le F# pour obtenir le même résultat en OCaml.

Par ailleurs je répète ici que pour benchmarker vos fonction, il vaut mieux leur faire afficher la longueur de la liste résultat : si vous affichez la liste elle-même, la seule chose que vous benchmarkez c'est la vitesse d'affichage dans votre console...

--
Jedaï

[gasche]

Oui évidemment (enfin maintenant qu'on me le dit), ce n'est pas
sumrec ((n - i) :: fond) (n - i)
mais sumrec (i :: fond) (n - i)
Et en plus, elle renvoie des solutions identiques, donc elle est vraiment à jeter

Cependant, j'estime bénéficier de circonstances particulièrement atténuantes :
1) la faute vient initialement de gorgonite, j'ai juste recopié son code;
2) mes tests fort sérieux ont montré que pour 0, 1 et 2, le résultat était correct.

Hmm... Il n'y a pas de compréhension de liste sous OCaml

http://oandrieu.nerim.net/ocaml/#pa_compr
(#light ressemble à une directive préprocesseur. Tous les coups sont permis !)

si vous affichez la liste elle-même, la seule chose que vous benchmarkez c'est la vitesse d'affichage dans votre console...

dans /dev/null ? ^^

[Jedai]

Ok, pas si tu rediriges la sortie vers /dev/null.

Voici en tout cas une version correcte du code de bluestorm, bien qu'il génère encore les n-uplets et pas les ensembles :

Code OCaml :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
open List

let ( @$ )f x = f x
let ( @@ ) f g x = f @$ g x

let seq n = Array.to_list @$ Array.init n @$ ( + ) 1

let sum = 
  let rec sumrec fond = function
    0 -> [fond]
  | n -> concat @$ map (fun i -> sumrec (i :: fond) (n - i)) @$ seq n
  in sumrec []

let () = 
  iter (print_newline @@ iter @$ Printf.printf "%d\t") @$ sum @$ read_int ()

--
Jedaï

[gorgonite]

bon, c'était la saint gorgonite cette nuit on dirait... pour infos, le coup du (n-i) au lieu de i était une erreur de recopie (mon code était un peu plus moche, car je testais des listes mutables & cie pour éviter de dupliquer les bouts de listes )

Code ocaml :

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
32
33
34
35
36
37
let rec build_list n m = if n>m then [] else n::(build_list (n+1) m);;
let min a b = if a<b then a else b;;

let sums n =
	let rec sumrec n m =
		match n with
			0 -> [[]]
			|n -> 
				let intervalle = build_list 1 (min m n) in
				List.concat (
					List.map (
						fun i -> List.map (fun li -> i::li) 
						(sumrec (n-i) i)
					) 
					intervalle
				)
	in
	sumrec n n
;;

let rec print_list l =
	match l with
		[] -> ()
		|a::q -> Printf.printf "%d " a ; print_list q
;;

let rec print lst = 
	match lst with
		[] -> ()
		|a::q -> Printf.printf "[ " ; print_list a ; Printf.printf "] \n" ; print q
;;

let main () =
	Printf.printf "%d\n" (List.length (sums (int_of_string Sys.argv.(1))))
;;

main ();;

finalement, je suis revenu sur une solution proche de celle de Jedai et LLB (j'avais testé jusqu'à 2... et n'avait pas fait gaffe qu'au delà, ça renvoyait les nuplets et non les ensembles)

pour infos, cela met
+ 19ms pour calculer le résultat pour 21
+ 10s pour 54
+ stack overflow pour 55

[LLB]

Envoyé par bluestorm

http://oandrieu.nerim.net/ocaml/#pa_compr
(#light ressemble à une directive préprocesseur. Tous les coups sont permis !)

En pratique, ce n'est pas un préprocesseur dans F# (il n'y en a hélas pas encore), c'est plutôt géré dans le parseur. Pour les différences avec Caml, il y en a un certain nombre dans mon code (alors que copier coller le code Caml dans F# fonctionne sans changer le moindre caractère). À titre indicatif, voilà les différences entre les 2 langages utilisées dans mon code :

• #light pour utiliser l'indentation et s'affranchir de certains mots-clés ("in", etc.)
• list comprehensions (à noter que le ->> fait un append d'une liste, alors que -> ajoute un élément)
• l'opérateur |>, qui se définit par : let (|>) x f = f x. On peut donc l'avoir aussi en Caml, mais c'est une pratique très courante en F# (il y a également l'opérateur <| qui correspond au $ de haskell et << et >> qui servent à composer les fonctions).
• a.Force() est utilisable à la place de Lazy.force a.
• Petite différence dans la bibliothèque standard : on utilise Array2 pour les tableaux à 2 dimensions (et petite différence dans l'accès au tableau).
• print_any, qui affiche n'importe quelle valeur
• lazy (faut mettre des parenthèses autour dans Caml) a un comportement un peu différent. La récursion mutuelle que j'ai faite entre le tableau et sa fonction d'initialisation est acceptée dans F#. En Caml, ça me renvoie systématiquement un "This kind of expression is not allowed as right-hand side of `let rec'". Je ne sais pas si on peut le contourner simplement.

L'esprit est le même, mais il y a quand même pas mal de raccourcis syntaxiques. Maintenant, si tu arrives à avoir le comportement de F# en utilisant Camlp4, je serais vraiment ravi.



EDIT

Non, décidément, je n'arrive pas à convenir ma fonction en Caml. Le problème vient de la récursion mutuelle entre le tableau et son initialisation. Même un code aussi simpliste que :

Code :

1
2
3
let rec a = Array.init 10 foo
and foo x = 0;;
This kind of expression is not allowed as right-hand side of `let rec'

est refusé. Quelqu'un a une solution (paresseuse et sans faire d'effet de bord) ?