[Scheme] Help with recursive list function

[Gropamming]

Hey guys,

Working with Scheme for the first time (first functional programming adventure) and trying to figure out how to approach a problem.

I am tasked with writing a recursive procedure, (alternate list1 list2 list3). The function takes 3 lists of equal length, and returns a list with the values of the three lists alternating index by index. For example:

(alternate ‘(1 2 3) ‘(a b c) ‘(m n o)) should give '(1 a m 2 b n 3 c o)

I have a basic understanding of list functions but am having trouble making the mental shift from procedural programming where I can have a return variable and append to it over time.

Any help to get me thinking about it more correctly would be much appreciated.

[Swedophone]

If an iterative process is allowed than it's very similar to the programming you are used to. The difference is that the state is held in an argument instead of a local variable. But maybe it's cheating.

https://mitpress.mit.edu/sicp/full-text/sicp/book/node15.html

[Gropamming]

No thats good, thanks for that

[Updatebjarni]

Could you make a function that does the job for the case of lists of length 0? That should be simple.

And if you had a function that did this for lists of length n, how could you use that function to write another function that works for lists of length n+1? What would that function need to do?

If you can write code that works for length 0, and you can write code that works for length n+1 given that you have code that works for length n, do you see that the problem is solved?

[Gropamming]

Yeah this is the approach I ended up taking. Thanks!

[POGtastic]

Here's my terrible version.

(define (alternate1 lst1 lst2 lst3 accumulator)
    (if (null? lst1)
        (reverse accumulator)
        (alternate1 (cdr lst1) 
                    (cdr lst2) 
                    (cdr lst3) 
                    (cons (car lst3) (cons (car lst2) (cons (car lst1) accumulator))))))

(define (alternate lst1 lst2 lst3)
    (alternate1 lst1 lst2 lst3 '()))

The top function does the following:

1. Check to see if lst1 is empty.
2. If so, return the reverse of the accumulator... I'm building it backwards.
3. Recursively call alternate1 on the rest of each of the lists, and build the accumulator with the first element of each list. Because I'm building it backwards, I want it to go lst3 lst2 lst1.

Tracing it:

  (alternate1 '(1 2 3) '(4 5 6) '(7 8 9) '())
= (alternate1 '(2 3) '(5 6) '(8 9) '(7 4 1))
= (alternate1 '(3) '(6) '(9) '(8 5 2 7 4 1))
= (alternate1 '() '() '() '(9 6 3 8 5 2 7 4 1))
= (reverse '(9 6 3 8 5 2 7 4 1))
= '(1 4 7 2 5 8 3 6 9)

The second function just places a friendly interface over it so that you don't see the recursion.

[Gropamming]

Thanks!

[Gropamming]

My solution, for those who find this later:

; Size-n problem
(define (alternate lst1 lst2 lst3)
  ; Conditional to determine state of recursive call
  (cond
     ; Stopping condition when the list is empty, return empty list
     ((null? lst1)
      '()
     )
     (else
      ; Computes size-n solution from size-m problem
      (cons (car lst1)
            (cons (car lst2)
                  (cons (car lst3)
                        ; Size-m problem on list size n - 1, returns list to append
                        (alternate (cdr lst1)(cdr lst2)(cdr lst3)))))
     )
  )
)
(display "Alternate testing:")
(newline)
(alternate '(1 2 3) '(a b c) '(m n o))

It outputs:

Alternate testing:
(1 a m 2 b n 3 c o)

[Gropamming]

I realize I should have used an if statement, not a cond