Trier une liste en schéma

Question

Je veux créer une fonction qui trie la liste. Par exemple, j'ai cette liste :

x1, x2, x3 .... xn

ou

1, 2, 3, 4, 5, 6

Je veux afficher les chiffres dans cet ordre :

x1, xn, x2, xn-1

ou

1, 6, 2, 5, 3, 4

Pouvez-vous m'aider à rédiger cet exemple ?

Answer 1

En général, lorsque nous parlons de tri, nous nous référons au classement des éléments en fonction d'une caractéristique du contenu de l'élément, et non de la position de l'élément dans la liste. Je qualifierais votre situation de permutation, mais certaines personnes pourraient contester cet usage :-)

Voici comment vous pourriez aborder le problème :

1. Divisez la liste en son milieu (vous pouvez le faire en utilisant la tortue et le lièvre si vous ne voulez parcourir la liste qu'une seule fois) ; appelez ces listes head et tail si vous le souhaitez.
2. Inverser le tail et l'intercaler avec la liste head liste.

Une autre approche :

1. Inversez les paires de listes originales (appelons-les rev ).
2. Intercaler la liste originale avec rev en gardant la trace de l'élément traversé à chaque fois. Lorsqu'ils se rencontrent au milieu, arrêtez-vous.

Voici une démonstration de la deuxième approche (qui requiert SRFI 1 à charger) :

(define (zippy lst)
  (if (null? lst)
      '()
      (let recur ((lst lst)
                  (rev (pair-fold cons '() lst)))
        (cond ((eq? lst (car rev)) (list (car lst)))
              ((eq? (cdr lst) (car rev)) (list (car lst) (caar rev)))
              (else (cons* (car lst) (caar rev)
                           (recur (cdr lst) (cdr rev))))))))