CODEWITHSUNDEEP
listschemeracketmutablecircular-reference
user963395
user963395

Reputation:

Mysterious scheme procedure for cycling through lists

There is this procedure giving me trouble:

(define (pro lst)
  (define (inner l)
    (if (null? (mcdr l))
        (set-mcdr! l lst)
        (inner (mcdr l))))
  (inner lst)
  lst)

Using (mlist 1 2 3) as parameter I get #0={1 2 3 . #0#} returned. (mcdr (pro (mlist 1 2 3))) returns #0={2 3 1 . #0#}, (mcdr (mcdr (pro (mlist 1 2 3)))) returns #0={3 1 2 . #0#} and so on.

So obviously this is for cycling through lists by returning a pair of a list and another procedure. But how does this work? I only see that it replaces the final'() with the parameter lst but not with any obscure lambda function ... What do #0 and #0# mean anyway?

Upvotes: 2

Views: 395

Answers (2)

Óscar López
Óscar López

Reputation: 236114

In the expression #0={1 2 3 . #0#}, think of #0= as an anchor and #0# as a link to that anchor - that is, in the list the first three elements are 1 2 3 but the fourth element is a pointer to the start of the list, therefore forming a three-element circular list. If you keep advancing over that list (by successive mcdrs), you'll see a three element list in a cycling pattern 1 2 3 1 2 3 ..., always showing that the fourth element jumps back to the first.

Studying the above function makes it clear why this is happenning. The pro procedure simply calls inner on the lst parameter (a proper list, a list with null as its last element) and then returns the modified lst, the interesting part is what happens in inner:

  • (if (null? (mcdr l)): If we're on the last non-null element of the list, replace the next element (which should be a null in a proper list), by a reference to the first element, which we know is in the lst parameter: (set-mcdr! l lst)
  • Otherwise, keep advancing over the list: (inner (mcdr l))

To summarize: the pro procedure gets as its input a proper list and returns the same list but with the last element pointing back to its first element - a circular list.

Upvotes: 2

nadeem
nadeem

Reputation: 721

The #0= indicates a shared marker to some data, and #0# indicates a reference to the data previously marked. See the examples at the bottom of http://docs.racket-lang.org/reference/shared.html . Your function doesn't return a pair of things, just a single value - the last expression in the body of the definition, which is lst. But as you perhaps realize, the lst at the end has potentially been mutated so that it is different than what it was when initially passed to the function. (You use the term "cycling" which is exactly what this function does, but not quite in the sense that you've applied it in your question.)

Upvotes: 2

Related Questions