Caml - Tous les decoupages d'une liste

[jnarhap]

Bonsoir,

Je dois rédigez en Caml une fonction :

Code : Tout sélectionner

decoupages : ’a list -> (’a list * ’a list) list

spécifiée comme suit: decoupages z construit la liste de tous les couples (x, y) de listes toutes deux non vides, vérifiant z = x @ y (au sens de la concaténation des listes).

J'ai fait une première version de cette forme

Code : Tout sélectionner

let rec decoupe = fun
     | [] -> [[],[]]
     | (h::q) -> let (a,b)::p = decoupe_av q in [[h],q]@[h::a, b];;

Mais celle-ci ne fonctionne pas, je n'arrive pas à saisir pourquoi...

J'ai essayé pour palier à ça de faire un fonction intermédiaire, qui renverait par exemple la découpe à droite pour une valeur donnée... Sauf qu'il nous est expressement interdit d'accéder à la longueur d'une liste... Donc pas moyen de faire évoluer le paramètre a dans l'algo suivant...

Code : Tout sélectionner

let rec decoupe_arr = fun
     | a [] -> []
     | 0 (h::q) -> q
     | a (h::q) -> decoupe_arr (a-1) q;;

Bref, je suis un peu perdu... J'avais aussi imaginé une fonction intervalle qui me renvoie une sous liste partant du a-ieme élément et s'arrêtant b éléments plus loin

Code : Tout sélectionner

let rec intervalle = fun
     | 0 0 l -> [] 
     | 0 b (h::q) -> h::(intervalle 0 (b-1) q)
     | a b (h::q) -> intervalle (a-1) b q
     | a b [] -> [];;

Mais même problème, aucun moyen de savoir comment faire évoluer a b...


Ho évidemment je n'ai droit qu'au récursif haha...

La réponse doit être assez simple je pense, mais je n'arrive vraiment pas à mettre le doigt dessus... Je ne suis pas contre un petit coup de pouce o/

[left_shift]

Tu n'est pas loin du tout avec ta première version. Je te donne un début de correction.

Note déjà que sachant que x et y doivent être non vides, le problème n'a pas de solution pour des listes de longueurs 0 ou 1, et a une unique solution pour une liste de longueur 2. Le code va donc ressembler à :

Code : Tout sélectionner

let rec decoupe = function
  | [] -> []
  | [a] -> []
  | [a; b] -> [([a], [b])]
  | h::q -> (* à compléter *)

Tu as bien compris que dans le dernier cas, outre la solution ([h], q), doivent se rajouter toutes les solutions obtenues par un appel récursif sur q, solutions pour lesquelles h doit être ajouté en tête de la première liste du couple.

La solution consiste à utiliser la fonctionnelle map : si f est une fonction, map f [a1; ...; an] renvoie la liste [f a1; ...; f an]. C'est ce qui va te permettre de modifier comme il faut le résultat de l'appel récursif sur q. Cela donne :

SPOILER:

Code : Tout sélectionner

let rec decoupe = function
  | [] -> []
  | [a] -> []
  | [a; b] -> [([a], [b])]
  | (h::q) -> ([h], q)::(map (function x, y -> (h::x, y)) (decoupe q)) ;;

[jnarhap]

Je suis un peu surpris que ça demande d'utiliser map, on ne l'a pas encore vu en cours...

Du coup j'ai fait deux versions, une avec map, et une autre qui fait un appel à une autre fonction qui reproduit le fonctionnement de map, et ça marche très bien !

Merci beaucoup pour cette réponse en tout cas