Comment calculez-vous correctement les différences par paire dans Scheme?

Question

donné une liste de chiffres, disons, (1 3 6 10 0), comment calculer les différences (x _i - x _i-1), à condition que vous avez x _-1 = 0?

(le résultat dans cet exemple devrait être (1 2 3 4 -10))

J'ai trouvé que cette solution soit correcte:

 
(define (pairwise-2 f init l) 
    (first 
    (foldl 
    (λ (x acc-data) 
     (let ([result-list (first acc-data)] 
      [prev-x (second acc-data)]) 
     (list 
     (append result-list (list(f x prev-x))) 
     x))) 
    (list empty 0) 
    l))) 

(pairwise-2 - 0 '(1 3 6 10 0)) 
;; => (1 2 3 4 -10) 

Cependant, je pense qu'il devrait y avoir plus élégant que solution non moins flexible. C'est juste moche. Je suis novice en programmation fonctionnelle et j'aimerais avoir des suggestions sur le code.

Merci.

Answer 1

Je n'ai pas fait de schéma dans les années de chien, mais cela me frappe comme un petit problème typique de type lisper.

J'ai commencé avec une définition de base (s'il vous plaît ignorer un mauvais placement de parens - Je n'ai pas un interprète schéma pratique:

(define pairwise-diff 
    (lambda (list) 
     (cond 
     ((null? list) '()) 
     ((atom? list) list) 
     (t (pairwise-helper 0 list))))) 

Cela gère les cas de merde de nuls et atome, puis délègue l'affaire de viande une aide:

(define pairwise-helper 
    (lambda (n list) 
     (cond 
     ((null? list) '()) 
     (t 
      (let ([one (car list)]) 
       (cons (- one n) (pairwise-helper one (cdr list)))) 
     )))) 

Vous pouvez réécrire cela en utilisant « si », mais je suis d'utiliser câblé cond

Il y a deux cas ici. liste nulle - ce qui est e asy et tout le reste. Pour tout le reste, je prends la tête de la liste et compare ce diff au cas récursif. Je ne pense pas que cela devienne beaucoup plus simple.

Answer 2

Après le raffinage et l'adaptation au PLT Scheme de codeplinth, je pense que la solution presque parfaite serait:

 
(define (pairwise-apply f l0 l) 
    (if (empty? l) 
     '() 
     (let ([l1 (first l)]) 
     (cons (f l1 l0) (pairwise-apply f l1 (rest l)))))) 

Answer 3

map prend plusieurs arguments. Donc, je voudrais juste faire

(define (butlast l) 
    (reverse (cdr (reverse l)))) 
(let ((l '(0 1 3 6 10))) 
    (map - l (cons 0 (butlast l))) 

Si vous voulez envelopper dans une fonction, disons

(define (pairwise-call f init l) 
    (map f l (cons init (butlast l)))) 

Ceci est bien sûr pas la Petite Schemer Way, mais la manière qui évite l'écriture récursion toi même. Choisissez la façon dont vous aimez le mieux.

Answer 4

Haskell me dit d'utiliser zip;)

(define (zip-with f xs ys) 
    (cond ((or (null? xs) (null? ys)) null) 
     (else (cons (f (car xs) (car ys)) 
        (zip-with f (cdr xs) (cdr ys)))))) 
(define (pairwise-diff lst) (zip-with - (cdr lst) lst)) 

(pairwise-diff (list 1 3 6 10 0)) 
; gives (2 3 4 -10) 

Answer 5

ne correspond pas fini, dès que la liste des arguments le plus court est épuisé, de toute façon?

 
(define (pairwise-call fun init-element lst) 
    (map fun lst (cons init-element lst))) 

modifier: jleedev me informe que ce n'est pas le cas dans au moins une mise en œuvre du schéma.C'est un peu ennuyeux, puisqu'il n'y a pas d'opération O (1) pour couper la fin d'une liste.

Peut-être que nous pouvons utiliser reduce:

 
(define (pairwise-call fun init-element lst) 
    (reverse (cdr (reduce (lambda (a b) 
          (append (list b (- b (car a))) (cdr a))) 
         (cons (list init-element) lst))))) 

(Avertissement: hack, non testé)

Answer 6

Ceci est la façon la plus simple:

(define (solution ls) 
    (let loop ((ls (cons 0 ls))) 
    (let ((x (cadr ls)) (x_1 (car ls))) 
     (if (null? (cddr ls)) (list (- x x_1)) 
      (cons (- x x_1) (loop (cdr ls))))))) 

(display (equal? (solution '(1)) '(1))) (newline) 
(display (equal? (solution '(1 5)) '(1 4))) (newline) 
(display (equal? (solution '(1 3 6 10 0)) '(1 2 3 4 -10))) (newline) 

Dressez l'extension de code pour chacun des l'exemple pour voir comment cela fonctionne.

Si vous êtes intéressé à commencer avec FP, assurez-vous de vérifier comment concevoir un programme. Bien sûr, il est écrit pour les gens nouveau à la programmation, mais il a des tonnes de bons idiomes FP dans.

Answer 7

(define (f l res cur) 
    (if (null? l) 
    res 
    (let ((next (car l))) 
     (f (cdr l) (cons (- next cur) res) next)))) 

(define (do-work l) 
    (reverse (f l '() 0))) 

(do-work '(1 3 6 10 0)) 

==> (1 2 3 4 -10)