How does scramble function works? (Chapter 1 of The Seasoned Schemer)

Question

According to the book, this is what the function definition is,

The function scramble takes a non-empty tuple in which no argument is greater than its own index and returns a tuple of same length. Each number in the argument is treated as a backward index from its own position to a point earlier in tuple. The result at each position is obtained by counting backward from the current position according to this index.

And these are some examples,

; Examples of scramble
(scramble '(1 1 1 3 4 2 1 1 9 2))       ; '(1 1 1 1 1 4 1 1 1 9)
(scramble '(1 2 3 4 5 6 7 8 9))         ; '(1 1 1 1 1 1 1 1 1)
(scramble '(1 2 3 1 2 3 4 1 8 2 10))    ; '(1 1 1 1 1 1 1 1 2 8 2)

Here is the implementation,

(define pick
  (λ (i lat)
    (cond
      ((eq? i 1) (car lat))
      (else (pick (sub1 i)
                  (cdr lat))))))

(define scramble-b
  (lambda (tup rev-pre)
    (cond
      ((null? tup) '())
      (else
       (cons (pick (car tup) (cons (car tup) rev-pre))
             (scramble-b (cdr tup)
                         (cons (car tup) rev-pre)))))))

(define scramble
  (lambda (tup)
    (scramble-b tup '())))

Do you have a more specific question? The code is there, so you can work through it to understand how it works. So yes, what _specifically_ don't you understand? — ndc85430, Jun 18 '22 at 07:58
I don't understand how we came to the result. Like what does, “Each number in the argument is treated as a backward index from its position to a point earlier in the tuple. The result at each position is obtained by counting backward from the current position according to this index.” mean? My understanding is if the value at index 6 is 2 then we need to go 2 indices back and then go back again if we get another value like 3 and whenever we get something like 1 at position 1 we stop and that should be the output. But this is not the case like in this example, (scramble '(1 1 1 3 4 2 1 1 9 2)) — Hermann, Jun 18 '22 at 08:22
In terms of one-indexed arrays, `output[i] = input[i - input[i]]`. (You don't go back and forth, or mutate the input.) — molbdnilo, Jun 18 '22 at 08:51
@cypherbeep If you consider that "no argument is greater than its own index" and that the first element is 1, you know that the indexing starts at 1. — molbdnilo, Jun 20 '22 at 09:46

score 1 · Accepted Answer · answered Jun 18 '22 at 09:21

This is a case where using a very minimal version of the language means that the code is verbose enough that understanding the algorithm is not perhaps easy.

One way of dealing with this problem is to write the program in a much richer language, and then work out how the algorithm, which is now obvious, is implemented in the minimal version. Let's pick Racket as the rich language.

Racket has a function (as does Scheme) called list-ref: (list-ref l i) returns the ith element of l, zero-based.

It also has a nice notion of 'sequences' which are pretty much 'things you can iterate over' and a bunch of constructs whose names begin with for for iterating over sequences. There are two functions which make sequences we care about:

in-naturals makes an infinite sequence of the natural numbers, which by default starts from 0, but (in-naturals n) starts from n.
in-list makes a sequence from a list (a list is already a sequence in fact, but in-list makes things clearer and there are rumours also faster).

And the iteration construct we care about is for/list which iterates over some sequences and collects the result from its body into a list.

Given these, then the algorithm is almost trivial: we want to iterate along the list, keeping track of the current index and then do the appropriate subtraction to pick a value further back along the list. The only non-trivial bit is dealing with zero- vs one-based indexing.

(define (scramble l)
  (for/list ([index (in-naturals)]
             [element (in-list l)])
    (list-ref l (+ (- index element) 1))))

And in fact if we cause in-naturals to count from 1 we can avoid the awkward adding-1:

(define (scramble l)
  (for/list ([index (in-naturals 1)]
             (element (in-list l)))
    (list-ref l (- index element))))

Now looking at this code, even if you don't know Racket, the algorithm is very clear, and you can check it gives the answers in the book:

> (scramble '(1 1 1 3 4 2 1 1 9 2))
'(1 1 1 1 1 4 1 1 1 9)

Now it remains to work out how the code in the book implements the same algorithm. That's fiddly, but once you know what the algorithm is it should be straightforward.

Will Ness · Answer 2 · 2022-06-29T06:26:05.827

If the verbal description looks vague and hard to follow, we can try following the code itself, turning it into a more visual pseudocode as we go:

pick i [x, ...ys] = 
  case i { 
     1 --> x ;
     pick (i-1) ys }
==>
  pick i xs = nth1 i xs
     (* 1 <= i <= |xs| *)

scramble xs = 
   scramble2 xs []

scramble2 xs revPre =
 case xs {
   [] --> [] ;
   [x, ...ys] -->
     [ pick x [x, ...revPre],
       ...scramble2 ys
              [x, ...revPre]] }

Thus,

scramble [x,y,z,w, ...] 
 =
  [ nth1 x [x]       (*x=1..1*)
  , nth1 y [y,x]     (*y=1..2*)
  , nth1 z [z,y,x]   (*z=1..3*)
  , nth1 w [w,z,y,x] (*w=1..4*)
  , ... ]

Thus each element in the input list is used as an index into the reversed prefix of that list, up to and including that element. In other words, an index into the prefix while counting backwards, i.e. from the element to the left, i.e. towards the list's start.

So we have now visualized what the code is doing, and have also discovered requirements for its input list's elements.

How does scramble function works? (Chapter 1 of The Seasoned Schemer)

2 Answers2