Wie berechnen Sie richtig paarweise Unterschiede in Scheme?

Question

eine Liste von Zahlen gegeben, sagen wir, (1 3 6 10 0), wie berechnet man Unterschiede (x _i - x _i-1), vorausgesetzt, Sie haben x _-1 = 0?

Ich habe diese Lösung gefunden (das Ergebnis in diesem Beispiel sollte (1 2 3 4 -10) sein) korrekt zu sein:

 
(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) 

Aber ich denke, es sollte aber nicht weniger flexible Lösung eleganter sein. Es ist einfach hässlich.

Ich bin neu in der funktionalen Programmierung und würde gerne Vorschläge für den Code hören.

Danke.

Answer 1

Ich habe keinen Plan in den Jahren des Hundes gemacht, aber das scheint mir ein typisches kleines Lisper-Typ-Problem.

I mit einer Base Definition gestartet (bitte Abhandenkommen von Pars ignorieren - ich praktisch keinen Scheme-Interpreter haben:

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

die Mist Fälle von null und Atom Diese Griffe und dann die Delegierten das Fleisch Fall ein Helfer:

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

Sie könnten umschreiben dieses „if“, aber ich bin fest verdrahtete cond verwenden

Es gibt zwei Fälle hier:. null Liste - das ist e asy und alles andere. Für alles andere greife ich den Kopf der Liste und contra dieses diff in den rekursiven Fall. Ich glaube nicht, dass es viel einfacher wird.

Answer 2

Nach Veredelung und Anpassung an den PLT Scheme plinth ‚s code, glaube, ich würde fast perfekte Lösung sein:

 
(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 mehrere Argumente übernimmt. So würde ich tun, nur

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

Wenn Sie es in einer Funktion bis wickeln wollen, sage

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

Das ist natürlich nicht der Kleine Schemer Weg, aber die Art und Weise, die das Schreiben Rekursion vermeidet dich selber. Wählen Sie, wie Sie das Beste mögen.

Answer 4

Haskell sagt mir zip zu verwenden;)

(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

abbildet nicht beenden, sobald die kürzeste Argumentliste erschöpft ist, sowieso?

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

bearbeiten: jleedev sagt mir, dass dies in mindestens einer Scheme-Implementierung nicht der Fall ist.Dies ist ein wenig ärgerlich, da es keine O (1) -Operation gibt, um das Ende einer Liste abzubrechen.

Vielleicht können wir reduce verwenden:

 
(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))))) 

(Haftungsausschluss: quick hack, ungetestet)

Answer 6

Dies ist die einfachste Art und Weise:

(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) 

Schreiben für jeden der Code Erweiterung aus Das Beispiel, um zu sehen, wie es funktioniert.

Wenn Sie daran interessiert sind, mit FP zu beginnen, lesen Sie unbedingt How To Design Program. Sicher ist es für Menschen geschrieben brandneu Programmierung, aber es hat Tonnen von guten FP Idiome innerhalb.

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)