Hi all, I have been trying to get the hang of racket syntax by implementing some simple algorithms. One of them was reversing a list. First I implemented a function which takes in an immutable list and returns the reversed list: (define (reverse-list-rec iml) (define/match (do-reverse-list iml acc) [('() acc) acc] [((cons head tail) acc) (do-reverse-list tail (cons head acc))]) (do-reverse-list iml '())) then I tried implementing a function which takes in a mutable list, reverses it in-place and also returns the reversed list: (define (reverse-list-iter! ml) (let loop ([prev '()] [curr ml]) (cond [(null? curr) prev] [else (let ([next (mcdr curr)]) (set-mcdr! curr prev) (loop curr next))]))) The issue here is that it does return the reversed list but the in-memory mutation is not equal to the reversed list: >> (define mutable-list (mlist 1 2 3 4 5)) >> (reverse-list-iter! mutable-list) (mcons 5 (mcons 4 (mcons 3 (mcons 2 (mcons 1 '()))))) >> mutable-list (mcons 1 '())

So I thought I would refer to the official implementation of mreverse! : https://github.com/racket/compatibility/blob/5b67b56fe7f5b1a717e2aacf797a603ad4fed68d/compatibility-lib/compatibility/mlist.rkt#L153 which to my surprise is similar to mine and has the same behavior: >> (define mutable-list (mlist 1 2 3 4 5)) >> (mreverse! mutable-list) (mcons 5 (mcons 4 (mcons 3 (mcons 2 (mcons 1 '()))))) >> mutable-list (mcons 1 '())

Now I am not sure if mreverse! is supposed to behave like this but I would appreciate any help in regards to how would I go about writing a function which can reverse a mutable-list in-place. That would help me understand mutability a bit more in racket (even though its not the rackety way of doing things). Thanks

@abhirag The problem is that (define mutable-list ...) points to the first pair in the original list.

After the list is reversed, mutable-list still points at the same pair - but since the list is reversed, that pair is now the last pair in the list.

So (mcons 1 ()) means that the last pair of the reversed list is a list with a single 1.

And that’s correct.

So to see the reversed list, you will need to store where the last pair is, before reversing the list.

#lang racket
(require compatibility/mlist)

(define mutable-list (mlist 1 2 3 4 5))
(define last-pair (mcdr (mcdr (mcdr (mcdr mutable-list)))))
last-pair
(mreverse! mutable-list)
last-pair

The output is:

(mcons 5 '())
(mcons 5 (mcons 4 (mcons 3 (mcons 2 (mcons 1 '())))))
(mcons 5 (mcons 4 (mcons 3 (mcons 2 (mcons 1 '())))))

Thanks a lot @soegaard2 :slightly_smiling_face:

I understand what’s happening now, to make sure that ml actually points to the last-pair in your explanation, I probably would have to do an assignment before the return of the function if I am understanding stuff correctly

I think mutability is confusing me, probably a (set! ml prev) before return might fix this, I’ll try it out

Mutability is confusing.

Luckily you are experimenting in Racket.

I remember the good old days with single linked lists in C. A mistake always led to a crash.

yeah at this point of time, immutability makes compete sense to me but still wanted to make sure that I understood mutability in racket case I absolutely need it

thanks a lot for helping out, I’ll have to try and understand this a bit more

(set! ml prev) inside the function doesn’t seem to be doing anything, mutability is the worst

The reason (set! ml prev) doesn’t work is that ml is only visible inside your reverse function.

Try:

#lang racket
(require compatibility/mlist)

(define (mlast-pair xs)
  (cond
    [(null? xs)        #f]
    [(null? (mcdr xs)) xs]
    [else              (mlast-pair (mcdr xs))]))

(define xs (mlist 1 2 3 4 5))
(define last-pair (mlast-pair xs))
(mreverse! xs)
last-pair

I understand that part now, but I guess trying to make sure that xs returns the last-pair on return of the function wouldn’t be possible

becuase xs remains out of scope to that function

in python I would use something like nonlocal or global to qualify that identifier

but I guess I can’t do that in racket

Instead you can make (reverse-list-iter! ml) return the last pair.

apologies if I am not making my self clear, I might be confused, returning xs would be alright, but I can’t rebind xs outside

from insode the fucntion right?

so that when I return from the function

You can use set! to change a global binding.

the outside binding also points to the reversed list

I think I get it now, I’ll try and understand the whole thing including all the pointers you gave :slightly_smiling_face:

thanks a lot again @soegaard2

No problem.

Python’s nonlocal declarations prevent its = from acting as a local variable declaration. Racket’s set! never acts as a local variable declaration, so in a sense it’s always nonlocal.

It sounds like you want a variant of mreverse! that mutates every reference to the given mutable cons cell so that it refers to a different mutable cons cell instead. Generally that’s not possible since there may be references reverse-list-iter! has no way to get at.

There are some other ways to approximate that:

• Your utility could mutate the mcar of each cell in the list instead of the mcdr, so that the reversed list still starts with the same mutable cons cell.

• Your utility could be a syntax transformer where (reverse-list-iter! xs) means (set! xs (reverse xs)). This way the xs variable is modified and you don’t even need a mutable list.