CODEWITHSUNDEEP
functional-programmingscheme
ansgri
ansgri

Reputation: 2156

How do you properly compute pairwise differences in Scheme?

Given a list of numbers, say, (1 3 6 10 0), how do you compute differences (xi - xi-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.

Upvotes: 2

Views: 960

Answers (7)

Fabien
Fabien

Reputation: 13406

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

Upvotes: 0

grettke
grettke

Reputation: 1417

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.

Upvotes: 0

Nathan Shively-Sanders
Nathan Shively-Sanders

Reputation: 18389

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.

Upvotes: 2

Svante
Svante

Reputation: 51501

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)

Upvotes: 1

Josh Lee
Josh Lee

Reputation: 177550

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)

Upvotes: 1

ansgri
ansgri

Reputation: 2156

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

Upvotes: 1

plinth
plinth

Reputation: 49179

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.

Upvotes: 1

Related Questions