CODEWITHSUNDEEP
schemeracketfoldalternating
user2980932
user2980932

Reputation: 93

Alternating Sum Using Foldr/Foldl (Racket)

Back again with another Racket question. New to higher order functions in general, so give me some leeway.

Currently trying to find the alternating sum using the foldr/foldl functions and not recursion.

e.g. (altsum '(1 3 5 7)) should equal 1 - 3 + 5 - 7, which totals to -4.

I've thought about a few possible ways to tackle this problem:

  1. Get the numbers to add in one list and the numbers to subtract in another list and fold them together.
  2. Somehow use the list length to determine whether to subtract or add.
  3. Maybe generate some sort of '(1 -1 1 -1) mask, multiply respectively, then fold add everything.

However, I have no clue where to start with foldl/foldr when every operation is not the same for every item in the list, so I'm having trouble implementing any of my ideas. Additionally, whenever I try to add more than 2 variables in my foldl's anonymous class, I have no idea what variables afterward refer to what variables in the anonymous class either.

Any help or pointers would be greatly appreciated.

Upvotes: 1

Views: 1597

Answers (2)

Sylwester
Sylwester

Reputation: 48765

Your idea is OK. You can use range to make a list of number 0 to length-1 and use the oddness of each to determine + or -:

(define (alt-sum lst)
  (foldl (lambda (index e acc)
          (define op (if (even? index) + -)) 
          (op acc e))
        0
        (range (length lst))
        lst))

As an alternative one can use SRFI-1 List Library that has fold that allows different length lists as well as infinite lists and together with circular-list you can have it alterate between + and - for the duration of lst. 

(require srfi/1) ; For R6RS you import (srfi :1)

(define (alt-sum lst)
  (fold (lambda (op n result)
           (op result n))
         0
         (circular-list + -)
         lst))

(alt-sum '(1 3 5 7))
; ==> -4

Upvotes: 1

Óscar López
Óscar López

Reputation: 236114

We can leverage two higher-order procedures here: foldr for processing the list and build-list for generating a list of alternating operations to perform. Notice that foldr can accept more than one input list, in this case we take a list of numbers and a list of operations and iterate over them element-wise, accumulating the result:

(define (altsum lst)
  (foldr (lambda (ele op acc) (op acc ele))
         0
         lst
         (build-list (length lst)
                     (lambda (i) (if (even? i) + -)))))

It works as expected:

(altsum '(1 3 5 7))
=> -4

Upvotes: 1

Related Questions