Comment fusionner récursivement des paires sautantes d'éléments d'une liste de listes? J'ai besoin d'avoir
'((abc) (edf) (ghi))
de
' ((ab) c (ed) f (gh) i)
Ma tentative
(f listi)
fonctionne si je définis
(définir listi '((ab) c (de) f))
d'où j'obtiens
((a b c) (d e f))
en faisant simplement
(define (f lst)
(if (or (null? lst)
(null? (cdr lst)))
'()
(cons (append (car lst) (list (cadr lst)))
(list (append (caddr lst) (cdddr lst))))))
mais cela ne fonctionne pas pour les listes plus longues. Je sais que j'ai besoin de récursivité mais je ne sais pas où insérer à nouveau f dans la dernière phrase de mon code.
3 Réponses :
Un cas plus simple où votre algorithme échoue: (f '((1 2) 3)) devrait entraîner ' ((1 2 3)) , mais le vôtre entraîne une erreur.
Nous allons d'abord définir certains termes:
Un "élément" est un élément régulier, comme 1 ou 'a.
Une "liste simple" est simplement une liste d '"éléments" sans liste imbriquée.
Par exemple, '(1 2 3) est une liste simple. '((1 2) 3) n'est pas une liste simple.
Une "liste simple" est soit:
liste vide contre d'un "élément" et la prochaine "liste simple" Une "liste de paires sautantes" est une liste de longueur paire où l'index impair a une "liste simple", et l'index pair a un élément. Par exemple, '((1) 2 (a) 4) est une "liste de paires sautantes". Une "liste de paires sautantes" est soit:
liste vide contre de
contre d'un "élément" et la prochaine "liste de paires sautantes" Nous en avons fini avec la terminologie. Avant d'écrire la fonction, commençons par quelques exemples:
(define (f lst)
(cond
[(empty? lst) empty] ;; the empty list case
[else ;; the cons case returns
;; the resulting list of "plain list" that we want
(cons (append (first lst) (cons (first (rest lst)) empty))
(f (rest (rest lst))))]))
Donc, f est une fonction qui consomme une "liste de paires sautantes" et renvoie une liste de "liste simple".
Nous allons maintenant écrire la fonction f:
(define (f lst)
(cond
[(empty? lst) empty] ;; the empty list case
[else ;; the cons case has:
???
;; the resulting "plain list" that we want
(append (first lst) (cons (first (rest lst)) empty))
;; the list of "plain list"
(f (rest (rest lst)))
;; that are available for us to use
???]))
Notez que le type de lst est une "liste de paires sautantes", nous allons donc effectuer une analyse de cas dessus directement:
(define (f lst)
(cond
[(empty? lst) empty] ;; the empty list case
[else ;; the cons case has:
???
;; the resulting "plain list" that we want
(append (first lst) (cons (first (rest lst)) empty))
;; the next "list of jumping pairs"
(rest (rest lst))
;; that are available for us to use
???]))
De l'exemple: p >
(f '((1 2) 3)) equivalent to (f (cons (cons 1 (cons 2 empty))
(cons 3
empty)))
should output '((1 2 3))
equivalent to (cons (cons 1 (cons 2 (cons 3 empty)))
empty)
nous savons que le cas vide doit renvoyer une liste vide, donc remplissons le trou en conséquence:
(define (f lst)
(cond
[(empty? lst) empty] ;; the empty list case
[else ??? ;; the cons case has
(first lst) ;; the "plain list",
(first (rest lst)) ;; the "element", and
(rest (rest lst)) ;; the next "list of jumping pairs"
???])) ;; that are available for us to use
De l'exemple :
(f '()) equivalent to (f empty)
should output '()
equivalent to empty
nous savons que nous voulons définitivement mettre "l'élément" à l'arrière de la "liste simple" pour obtenir la "liste simple" résultante que nous voulons:
(define (f lst)
(cond
[(empty? lst) ???] ;; the empty list case
[else ??? ;; the cons case has
(first lst) ;; the "plain list",
(first (rest lst)) ;; the "element", and
(rest (rest lst)) ;; the next "list of jumping pairs"
???])) ;; that are available for us to use
Il reste encore la prochaine "liste de paires sautantes" dont nous devons nous occuper, mais nous avons déjà un moyen de le gérer: f code >!
(define (f lst) ???)
Et puis nous pouvons renvoyer la réponse:
(f '()) equivalent to (f empty)
should output '()
equivalent to empty
(f '((1 2) 3)) equivalent to (f (cons (cons 1 (cons 2 empty))
(cons 3
empty)))
should output '((1 2 3))
equivalent to (cons (cons 1 (cons 2 (cons 3 empty)))
empty)
(f '((1 2) 3 (4) a)) equivalent to (f (cons (cons 1 (cons 2 empty))
(cons 3
(cons (cons 4 empty)
(cons 'a
empty)))))
should output '((1 2 3) (4 a))
equivalent to (cons (cons 1 (cons 2 (cons 3 empty)))
(cons (cons 4 (cons 'a empty))
empty))
Explication belle et détaillée. Le programme génère une erreur pour une "liste de paires sautantes" mal formée comme (f '(x y z)) - pas nécessairement une mauvaise chose, mais peut-être pas ce que l'OP veut. Je propose une alternative dans ma réponse.
Il n'y a pas de cas récursif dans votre code, il fonctionnera donc de manière statique pour une liste de 4 éléments. Vous devez prendre en charge les éléments suivants:
(f '()) ; ==> () (f '((a b c) d (e f g) h)) ; ==> (cons (append '(a b c) (list 'd)) (f '((e f g) h)))
Maintenant, cela nécessite exactement un nombre d'éléments pair et que chaque élément impair est une liste appropriée. Il n'y a rien de mal à cela, mais onw voudra peut-être s'en assurer en vérifiant le type ou en ajoutant du code pour ce qui devrait se passer quand ce n'est pas le cas.
Correspondance de modèle (en utilisant match ci-dessous ) est incroyablement utile pour ce genre de problème -
(f '((a b) c (e d) f (g h) i)) ;; '((a b c) (e d f) (g h i)) (f '((a b) c)) ;; '((a b c)) (f '((a b) c x y z)) ;; '((a b c)) (f '(x y z)) ;; '() (f '()) ;; '()
define / match offre du sucre de syntaxe pour ce style de procédure commun rendant les choses encore plus agréables -
XXX
Et une révision récursive de queue -
(define (f xs)
(define/match (loop acc xs)
[(acc (list (list a b) c rest ...))
(loop (cons (list a b c) acc)
rest)]
[(acc _)
acc])
(reverse (loop empty xs)))
La sortie de chaque programme est la même -
(define/match (f xs)
[((list (list a b) c rest ...))
(cons (list a b c)
(f rest))]
[(_)
empty])