Fonction de partition de listes

Bonsoir,

je me casse la tête depuis un moment avec une fonction que je dois développer.
Elle consiste à entrer une liste l et un entier n, et en sortie donner une liste de 2 sous listes, la 1ere sous liste contiendra les éléments de l < p, et la seconde tous les éléments >= p.
Voici un petit exemple pour illustrer le problème :
En entrée : (maFontion '(1 2 3 4 5 6 7 8) 4) --> '('(1 2 3) '(4 5 6 7 8))

Voila ce que j'ai commencé à faire mais le problème c'est qu'en sortie j'obtiens ceci : (1 2 3 ((((() 8) 7) 6) 5) 4), j'ai testé pleins de choses différentes et la je commence à en avoir marre.

merci d'avance pour votre aide, bonne soirée.

Il suffit de parcourir la liste en mettant les éléments (< e) dans une liste et les autres dans une autre liste, par exemple avec foldl :
Code:

1 2 3 4 5 6 7 8 9 10 (define (part e L) (foldl (lambda (a b) (let ([i (car b)] [s (cadr b)]) (if (< a e) (list (cons a i) s) (list i (cons a s)) ) ) ) '(() ()) L ) )
Pas sûr que ce soit la meilleure façon de le faire en Scheme toutefois, c'est nettement plus élégant en Haskell.

--
Jedaï

Merci pour cette réponse je vais tester ça tout de suite.
Bon dimanche.

Citation:

Envoyé par Jedai

Pas sûr que ce soit la meilleure façon de le faire en Scheme toutefois, c'est nettement plus élégant en Haskell.

En Haskell/Caml/F#, il y a la fonction "partition" qui fait ça très bien. Il n'y a pas de telle fonction avec Scheme ?

Sinon, l'approche récursive doit être plus simple à comprendre que le foldl, je pense.

Citation:

Envoyé par LLB

En Haskell/Caml/F#, il y a la fonction "partition" qui fait ça très bien. Il n'y a pas de telle fonction avec Scheme ?

Sinon, l'approche récursive doit être plus simple à comprendre que le foldl, je pense.

Je ne crois pas qu'il y ait une telle fonction dans R5RS, ensuite, ça doit dépendre des Scheme. D'un autre côté, le but est sans doute de la recoder de toute façon.

En Haskell, sans utiliser partition, ça donnerait simplement :

Code:

infsup e = foldr (\x ~(infs, sups)->if x < e then (e:infs,sups) else (infs, e:sups)) ([],[])

(la définition de partition dans le Prelude est pratiquement identique à ça remarque).

Effectivement une simple récursion pourrait être plus facile à comprendre pour qui n'est pas accoutumé aux fold :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 (define (part e L) (if (empty? L) '(() ()) (let* ([a (car L)] [L* (part e (cdr L))] [infs (car L*)] [sups (cadr L*)] ) (if (< a e) (list (cons a infs) sups) (list infs (cons a sups)) ) ) ) )
(Je n'ai pas fait beaucoup de Scheme, y a sûrement moyen d'améliorer)

--
Jedaï

Citation:

Envoyé par Salandar

Bonsoir,

je me casse la tête depuis un moment avec une fonction que je dois développer.
Elle consiste à entrer une liste l et un entier n, et en sortie donner une liste de 2 sous listes, la 1ere sous liste contiendra les éléments de l < p, et la seconde tous les éléments >= p.
Voici un petit exemple pour illustrer le problème :
En entrée : (maFontion '(1 2 3 4 5 6 7 8) 4) --> '('(1 2 3) '(4 5 6 7 8))

Voila ce que j'ai commencé à faire mais le problème c'est qu'en sortie j'obtiens ceci : (1 2 3 ((((() 8) 7) 6) 5) 4), j'ai testé pleins de choses différentes et la je commence à en avoir marre.

merci d'avance pour votre aide, bonne soirée.

Encore une fois je suppose que c'est un problème vu en classe non ?
Quel est l'énoncé exacte ?
Est ce que vous avez vu des choses particulières comme les fonctions « foldl », « foldr », « map » etc. ?
As tu demandé à ton prof avant ? Sioui qu'est ce que tu n'as pas compris ?

Et finalement, je pense que ton erreur est simplement dans le constructeur que tu as utilise. Probablement qu'en reverifiant ton code tu pourrais la retrouver: ta deuxième liste est simplement construite à l'envers ((((() 8) 7) 6) 5) 4), et la première n'est pas encapsulée dans un « list ».

http://srfi.schemers.org/srfi-1/srfi-1.html#partition

Citation:

Envoyé par GnuVince

http://srfi.schemers.org/srfi-1/srfi-1.html#partition

Si c'est une question de cours, le but n'est pas qu'il utilise une fonction toute faite -_- mais qu'il comprenne comment le faire. Cependant, comme plusieurs auteurs de questions ici, il semble qu'il (Salandar) a l'air de s'en foutre éperdumment.

Tiens en retombant sur ça je me suis dit « comment l'aurais-je écris ? »

ET bien comme ça
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 (define L '(1 3 5 7 89 42 7 9 4 7 3 7 87 43 7 8 367 23 24 8 9 3 3)) (define (e< n) (lambda (e) (< e n))) (define (filter2 p? L L1 L2) (if (null? L) (list L1 L2) (let ((h (car L)) (t (cdr L))) (if (p? h) (filter2 p? t (cons h L1) L2) (filter2 p? t L1 (cons h L2)))))) (filter2 (e< 10) L '() '())
Souvent je dis que le typage fort d'ocaml est chiant... mais un truc vraiment sympa, comme dans Haskell, c'est la curryfication. Dommage que ce ne soit pas automatique en scheme.

Et en caml :

Code:

let part e = List.partition ((<) e);;

:-)
Bon, soyons sérieux,

Code:

let part e l = List.partition ((<) e) l;;

est nettement plus clair.

Citation:

Envoyé par alex_pi

Et en caml :

Code:

let part e = List.partition ((<) e);;

:-)
Bon, soyons sérieux,

Code:

let part e l = List.partition ((<) e) l;;

est nettement plus clair.

Pourquoi ? La première exprime clairement que "part e" effectue une partition sur le prédicat (e <), la seconde ne rajoute rien... Je ne suis pas un fana du style "point-free" mais dans ce cas, rajouter le point n'apporte aucune clarté supplémentaire.

--
Jedaï

Je pense que savoir si l'on met tous les arguments dans la définition de fonction releve vraiment de la sensibilité personnelle, et du cas par cas. Pour moi, ça dépend beaucoup du contexte dans le programme entre autre. Par exemple, une fonction auxiliaire, j'aurais tendance à ne pas mettre les arguments inutiles, pour une fonction "de librairie", j'aurais plus tendance à les mettre. Disons que ça permet de ne pas avoir à lire le code de la fonction pour connaitre les arguments, ce qui peut être aventageux !
Bref, tout ça est discutable au cas par cas me semble-t-il :)

Citation:

Envoyé par alex_pi

Je pense que savoir si l'on met tous les arguments dans la définition de fonction releve vraiment de la sensibilité personnelle[...]

En pratique, moi, j'aurais fait une fonction qui encapsule ça c'est clair.
Car je n'aime pas avoir trop de paramètre inutile
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 (define (part n L) (define (filter2 p? L L1 L2) (if (null? L) (list L1 L2) (let ((h (car L)) (t (cdr L))) (if (p? h) (filter2 p? t (cons h L1) L2) (filter2 p? t L1 (cons h L2)))))) (let ((e< (lambda (m) (< m n)))) (filter2 (m< 10) L '() '())) )
Ici je n'ai pas pris le temps de le faire.

Pour ta version... le but était, si tu relis le début du message, de la faire explicitement et non d'utiliser une fonction qui faisait déjà ça. ;)

Vu qu'on a toujours le polymorphisme avec ta première version, je préfère la première version quant à moi. Mais je suis assez d'accord, c'est un peu une préfèrence personnelle. Je ne vois pas de bon argument pour dire que ton « l » est de trop :mrgreen:

Citation:

Envoyé par Garulfo

Pour ta version... le but était, si tu relis le début du message, de la faire explicitement et non d'utiliser une fonction qui faisait déjà ça. ;)

Et en plus, c'était de le faire en Scheme ;-)

Si j'avais une remarque à faire sur le code Caml, ce serait plutôt l'application partielle sur l'opérateur < (quand on n'est pas habitué, on risque de le lire "à l'envers"). Une fonction anonyme permet de rendre le sens moins ambigü, ici.

Citation:

Envoyé par LLB

Si j'avais une remarque à faire sur le code Caml, ce serait plutôt l'application partielle sur l'opérateur < (quand on n'est pas habitué, on risque de le lire "à l'envers"). Une fonction anonyme permet de rendre le sens moins ambigü, ici.

Je suis bien d'accord, c'est pour ça que j'aime bien les sections en Haskell, bien qu'il ne s'agisse que de sucre syntaxique, je trouve que ça donne un code à la fois lisible et concis pour les applications partielles d'opérateurs.

--
Jedaï