CODEWITHSUNDEEP
scheme
Louis Koo
Louis Koo

Reputation: 31

Scheme: Using Abstract List Functions without Recursion

How can I write a function using abstract list functions (foldr, foldl, map, and filter) without recursion that consumes a list of numbers (list a1 a2 a3 ...) and produces the alternating sum a1 - a2 + a3 ...?

Upvotes: 2

Views: 1921

Answers (3)

Óscar López
Óscar López

Reputation: 235984

Here's a possible solution:

(define (sum-abstract-list-functions lst)
  (car
   (foldl
    (lambda (e acc)
      (cons (+ (car acc) (* e (cdr acc)))
            (- (cdr acc))))
    '(0 . 1)
    lst)))

I'm only using foldl, cons, car, cdr. The trick? accumulating two values: the actual sum (in the car part of the accumulator), and the current sign (+/-1 in the cdr part of the accumulator). The accumulator gets initialized in 0 for the sum and +1 for the sign, and at the end I return the sum, the car part of the accumulator. Use it like this:

(sum-abstract-list-functions (list 1 2 3 4 5))
> 3

EDIT :

As has been pointed out, this solution is the simplest of all:

(define (sum-abstract-list-functions lst)
  (foldr - 0 lst))

Upvotes: 1

Ryan Culpepper
Ryan Culpepper

Reputation: 10643

Here's a hint:

a1 - a2 + a3 - a4 ... aN

is the same as

a1 - (a2 - (a3 - (a4 - ... (aN - 0) ...)))

Is it obvious how to solve it now?

Upvotes: 8

Luis Casillas
Luis Casillas

Reputation: 30227

Is this homework? Well, we can split this problem into two subproblems:

  • Take a list (a1 a2 a3 a4 ... a2n-1 a2n) and alternately negate elements from it, to produce (a1 (- a2) a3 (- a4) ... a2n-1 (- a2n)).
  • Sum the elements of that resulting list.

The second part is the trivial one:

(define (sum xs)
  (foldl + 0 xs))

The first is the harder one, but it's not too hard. You need to transform the list while keeping a boolean state that indicates whether you're examining an even or an odd element, and negate or not accordingly. I can see three ways of doing this:

  • The mutational way: put the state into the closure that you pass to a map. The closure then modifies its environment from one call to the next.
  • Keep the state in the fold results: the fold result is a pair that contains the "real" result and the state as an element.
  • Use a different sort of abstract list function.

Here's an example of the third approach (and if this is for homework, I bet your teacher may well be incredulous you came up with it):

(define (contextual-foldr compute-next
                          compute-init
                          advance-context
                          left-context
                          xs)
  (if (null? xs)
      (compute-rightmost-result left-context)
      (compute-next left-context
                    (car xs)
                    (contextual-foldr compute-next
                                      compute-init
                                      advance-context
                                      (advance-context (car xs) left-context)
                                      (cdr xs)))))

(define (contextual-map contextual-fn advance-context left-context xs)
  (contextual-foldr (lambda (left elem rest)
                      (cons (fn left elem) rest))
                    '()
                    advance-context
                    left-context
                    xs))

(define (alternate-negations xs)
  (contextual-map (lambda (negate? elem)
                    (if negate?
                        (- elem)
                        elem))
                  not
                  #f
                  xs))

Upvotes: 1

Related Questions