[plt-scheme] mreverse!

From: Matthias Felleisen (matthias at ccs.neu.edu)
Date: Sat Jan 24 16:06:09 EST 2009

mreverse! reverses the list values, it does NOT change the  
association between any identifier and the value. Just imagine this:

  (define a (mlist 1 2 3 4))
  (define b a)
  (define c b)
  (define d a)
  (define e c)

  > (mreverse! d)

How do you think a function should find ALL possible pointers to the  
list and ensure that they now point to the other end? (This is an  
unsolvable problem by the way.)

So if you really need to reverse lst you want to say

  > (set! lst (mreverse lst)) ;; note the missing ! in mreverse

If you really really really need the efficiency of in-place reversals  
(unlikely until you get to the 1000s of items), you say

  > (set! lst (mreverse! lst))

-- Matthias



On Jan 24, 2009, at 3:57 PM, praimon wrote:

> hello,
>
> (require scheme/mpair)
>
> (define lst (mlist 1 2 3 4)
> (mreverse! lst)
>> {4 3 2 1}
> lst
>> {1}
>
> Unless I'm misunderstanding the point of mreverse!, that
> seems like the wrong answer. Shouldn't lst evaluate to
> {4 3 2 1}?
>
> Here's the code for the function:
>
> (define (mreverse! l)
>   (let loop ([l l][prev null])
>     (cond
>      [(null? l) prev]
>      [else (let ([next (mcdr l)])
>              (set-mcdr! l prev)
>              (loop next l))])))
>
> The original list stops mutating after the first iteration
> of the loop, i.e., after (set-mcdr! l null), which explains
> the above result.
>
> I tried fiddling with this (I assume the solution is very
> simple) without success. I did write a rube goldberg-like
> destructive reverse, but I'm eager to see what an elegant
> solution looks like.
>
> regards,
> praimon
> _________________________________________________
>   For list-related administrative tasks:
>   http://list.cs.brown.edu/mailman/listinfo/plt-scheme



Posted on the users mailing list.