How do you properly compute pairwise differences in Scheme?

Question

Hello,

Given a list of numbers, say, (1 3 6 10 0), how do you compute differences (x_i - x_i-1), provided that you have x_-1 = 0 ?

(the result in this example should be (1 2 3 4 -10))

I've found this solution to be correct:

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

However, I think there should be more elegant though no less flexible solution. It's just ugly.

I'm new to functional programming and would like to hear any suggestions on the code.

Thanks.

Answer 1

I haven't done scheme in dog's years, but this strikes me as a typical little lisper type problem.

I started with a base definition (please ignore misplacement of parens - I don't have a Scheme interpreter handy:

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

This handles the crap cases of null and atom and then delegates the meat case to a helper:

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

You could rewrite this using "if", but I'm hardwired to use cond.

There are two cases here: null list - which is easy and everything else. For everything else, I grab the head of the list and cons this diff onto the recursive case. I don't think it gets much simpler.

Answer 2

After refining and adapting to PLT Scheme plinth's code, I think nearly-perfect solution would be:

(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 takes multiple arguments. So I would just do

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

If you want to wrap it up in a function, say

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

This is of course not the Little Schemer Way, but the way that avoids writing recursion yourself. Choose the way you like the best.

Answer 4

Haskell tells me to use 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

Doesn't map finish as soon as the shortest argument list is exhausted, anyway?

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

edit: jleedev informs me that this is not the case in at least one Scheme implementation. This is a bit annoying, since there is no O(1) operation to chop off the end of a list.

Perhaps we can use 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)))))

(Disclaimer: quick hack, untested)

Answer 6

This is the simplest way:

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

Write out the code expansion for each of the example to see how it works.

If you are interested in getting started with FP, be sure to check out How To Design Program. Sure it is written for people brand new to programming, but it has tons of good FP idioms within.

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)