destructively changing the cdr of a sublist in a function

[ccc31807]

This question is related to the one I asked the other day about summing list elements.

Suppose you have a data structure that looks like this:
(defparameter list-1 '((0 . 2)(1 . 3)(2 . 4)(3 . 0)))

I want to write a function that captures the value of the cdr of an arbitrary sublist but then sets that place to 0. for example, suppose my target in list-1 is (nth list-1 1). I want to set num-values to 3 and set that element to (1 . 0).

Ultimately, I want to return a new list with various substitutions, but I've figured that out (I hope). The problem I'm having is setting up the initial environment for the execution of the function.

I can think of three ways to do it, maybe. The problem is that either it doesn't work, or I'm making silly mistakes that don't work. Unfortunately, I don't know which it is!

1. (defun func-1 (list place)
(let* ((target (nth list place)
(num-values (cdr target))
(new-place (setf (cdr target 0))) ?????
...)

2. (defun func-1 (list place)
(setf target (nth list place)
(setf num-values (cdr target))
(setf (cdr target 0))
(setf (nth list place) target)) ???
... ;recursive calls don't work here)

3. same as 2 but use a helper function rather than a recursive call.

BOTTOM LINE: A simple requirement is to take a list that looks like this:
((0 . 1)(1 . 0))
and return a list that looks like this:
((0 . 0)(1 . 1))
in a generalized function that takes an arbitrarily long list and an arbitrary place.

Any suggestions on how to do this?

Thanks, CC.
...)

[Barry Margolin]

In article <fda827c8-98e9-4980...@googlegroups.com>,

ccc31807 <cart...@gmail.com> wrote:

> This question is related to the one I asked the other day about summing list
> elements.
>
> Suppose you have a data structure that looks like this:
> (defparameter list-1 '((0 . 2)(1 . 3)(2 . 4)(3 . 0)))
>
> I want to write a function that captures the value of the cdr of an arbitrary
> sublist but then sets that place to 0. for example, suppose my target in
> list-1 is (nth list-1 1). I want to set num-values to 3 and set that element
> to (1 . 0).
>
> Ultimately, I want to return a new list with various substitutions, but I've
> figured that out (I hope). The problem I'm having is setting up the initial
> environment for the execution of the function.
>
> I can think of three ways to do it, maybe. The problem is that either it
> doesn't work, or I'm making silly mistakes that don't work. Unfortunately, I

You're making a silly mistake, see below.

> don't know which it is!
>
> 1. (defun func-1 (list place)
> (let* ((target (nth list place)
> (num-values (cdr target))
> (new-place (setf (cdr target 0))) ?????
> ...)

The syntax of SETF is:

(setf <place> <new-value>)

Compare that to what you wrote. Fix the discrepancy and your function
will work.

There's one other thing: you shouldn't perform destructive modification
of a data structure created using a literal (i.e. quoted) expression.
So change your DEFPARAMETER to use functions to create fresh object, i.e.

(defparameter list-1 (list (cons 0 2) (cons 1 3) ...))

--
Barry Margolin, bar...@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***

[ccc31807]

On Friday, November 9, 2012 11:40:06 AM UTC-5, Barry Margolin wrote:
> You're making a silly mistake, see below.

Yes, thanks, I see that.

> The syntax of SETF is:
> (setf <place> <new-value>)
> Compare that to what you wrote. Fix the discrepancy and your function
> will work.
>
> There's one other thing: you shouldn't perform destructive modification
> of a data structure created using a literal (i.e. quoted) expression.
> So change your DEFPARAMETER to use functions to create fresh object, i.e.
> (defparameter list-1 (list (cons 0 2) (cons 1 3) ...))

I'm trying my hand at a mancala type game (by way of explanation). Here is what I finally came up with. I won't ask you for comments, but would appreciate it if you have any.

-------------code--------------------
(defun drop-pebbles (state square)
(let* ((factor (length state)) ;this is the factor for the modulus operation
(target (car (subseq state square (1+ square)))) ;finds the target element for further processing
(num-pebbles (cdr target)) ; get the number of pebbles to drop
(start-square (mod (1+ square) factor))
(new-state (copy-alist state)))
(setf (cdr (nth square new-state)) 0)
(drop-pebbles-helper new-state num-pebbles start-square factor)))

(defun drop-pebbles-helper (new-state num-pebbles start-square factor)
(do ((pebbles num-pebbles (1- pebbles))
(element start-square (1+ element)))
((zerop pebbles) new-state)
(progn
(incf (cdr (nth (mod element factor) new-state))))))
----------------run twice-------------------
* list-1

((0 . 2) (1 . 1) (2 . 0) (3 . 0) (4 . 3) (5 . 1))
* (drop-pebbles list-1 2)
0: (DROP-PEBBLES ((0 . 2) (1 . 1) (2 . 0) (3 . 0) (4 . 3) (5 . 1)) 2)
1: (DROP-PEBBLES-HELPER ((0 . 2) (1 . 1) (2 . 0) (3 . 0) (4 . 3) (5 . 1)) 0
3 6)
1: DROP-PEBBLES-HELPER returned
((0 . 2) (1 . 1) (2 . 0) (3 . 0) (4 . 3) (5 . 1))
0: DROP-PEBBLES returned ((0 . 2) (1 . 1) (2 . 0) (3 . 0) (4 . 3) (5 . 1))
((0 . 2) (1 . 1) (2 . 0) (3 . 0) (4 . 3) (5 . 1))
* (drop-pebbles list-1 5)
0: (DROP-PEBBLES ((0 . 2) (1 . 1) (2 . 0) (3 . 0) (4 . 3) (5 . 1)) 5)
1: (DROP-PEBBLES-HELPER ((0 . 2) (1 . 1) (2 . 0) (3 . 0) (4 . 3) (5 . 0)) 1
0 6)
1: DROP-PEBBLES-HELPER returned
((0 . 3) (1 . 1) (2 . 0) (3 . 0) (4 . 3) (5 . 0))
0: DROP-PEBBLES returned ((0 . 3) (1 . 1) (2 . 0) (3 . 0) (4 . 3) (5 . 0))
((0 . 3) (1 . 1) (2 . 0) (3 . 0) (4 . 3) (5 . 0))
*

[Barry Margolin]

In article <66a0c0cc-9407-4822...@googlegroups.com>,

ccc31807 <cart...@gmail.com> wrote:

> On Friday, November 9, 2012 11:40:06 AM UTC-5, Barry Margolin wrote:
> > You're making a silly mistake, see below.
>
> Yes, thanks, I see that.
>
>
> > The syntax of SETF is:
> > (setf <place> <new-value>)
> > Compare that to what you wrote. Fix the discrepancy and your function
> > will work.
> >
> > There's one other thing: you shouldn't perform destructive modification
> > of a data structure created using a literal (i.e. quoted) expression.
> > So change your DEFPARAMETER to use functions to create fresh object, i.e.
> > (defparameter list-1 (list (cons 0 2) (cons 1 3) ...))
>
> I'm trying my hand at a mancala type game (by way of explanation). Here is
> what I finally came up with. I won't ask you for comments, but would
> appreciate it if you have any.

If you find yourself using NTH frequently, an array is often a better
container than a list.

[WJ]

Racket:

(dict-ref '((a . 1)(b . 2)(c . 3)) 'b)
--> 2
(dict-set '((a . 1)(b . 2)(c . 3)) 'b 0)
--> '((a . 1) (b . 0) (c . 3))

[WJ]

Racket:

(define the-board (vector 2 1 0 0 3 1))

;; Caution. Modifies board.
(define (drop-pebbles board cup)
(let ((divisor (vector-length board))
(pebbles (vector-ref board cup)))
(vector-set! board cup 0)
(for ([i pebbles])
(dict-update! board (modulo (+ 1 i cup) divisor) add1))))

(drop-pebbles the-board 4)
the-board

--> '#(3 2 0 0 0 2)

[Pascal J. Bourguignon]

Try:

(defun display-mancala (state &optional (stream *standard-output*))
(let* ((n/2 (truncate (length state) 2))
(above (subseq state 0 n/2))
(below (reverse (subseq state n/2))))
(format stream
"~{+~*-----~}+~%~:*~{|~3D ~}|~%~{+~*-----~}+~%~:*~{|~3D ~}|~%~:*~{+~*-----~}+~%"
(mapcar (function cdr) above)
(mapcar (function cdr) below))))

(display-mancala '((0 . 2) (1 . 1) (2 . 0) (3 . 0) (4 . 3) (5 . 1)))
+-----+-----+-----+
| 2 | 1 | 0 |
+-----+-----+-----+
| 1 | 3 | 0 |
+-----+-----+-----+

If you encapsulate your lists in clos objects, then you can write a
print-object method so that the debugger prints this ASCII-art instead
of the a-lists:


(defclass mancala ()
((state :type list :initarg :state :accessor mancala-state)))

(defmethod print-object ((self mancala) stream)
(if *print-readably*
(print-unreadable-object (self stream))
(display-mancala (mancala-state self) stream))
self)

(make-instance 'mancala :state '((0 . 2) (1 . 1) (2 . 0) (3 . 0) (4 . 3) (5 . 1)))
+-----+-----+-----+
| 2 | 1 | 0 |
+-----+-----+-----+
| 1 | 3 | 0 |
+-----+-----+-----+


--
__Pascal Bourguignon__
http://www.informatimago.com

[WJ]

Racket:

(define the-board (vector 2 1 0 5 3 1))

(define (stones-picture n)
(define-values (doubles singles) (quotient/remainder n 2))
(~a #:width 5 #:align 'center
(make-string doubles #\:) (make-string singles #\.)))

(define (row-of-stones row)
(apply format "|~a|~a|~a|" (map stones-picture row)))

(define (draw-board board)
(define board-list (vector->list board))
(display-lines
(list
"+-----+-----+-----+"
(row-of-stones (take board-list 3))
"+-----+-----+-----+"
(row-of-stones (reverse (drop board-list 3)))
"+-----+-----+-----+")))

(draw-board the-board)
+-----+-----+-----+
| : | . | |
+-----+-----+-----+
| . | :. | ::. |
+-----+-----+-----+

[Madhu]

* Barry Margolin <barmar-2C45DE....@news.eternal-september.org> :
Wrote on Fri, 09 Nov 2012 14:07:51 -0500:

| If you find yourself using NTH frequently, an array is often a better
| container than a list.

Here is a "stupid idea" in that case: put each cons cell of the list into an
array:

(make-array (length LIST)
:initial-contents (loop for a on LIST by #'cdr collect a))

and use (CAR o ELT). In theory this would work when 1) the list
structure does not change heavily, 2) the algorithms operating on the
data structure mainly want a linked list as the underlying sequence, and
3) use NTH heavily

Has anyone found themselves in a situation where they ended up doing
this?

--- Madhu

[Zach Beane]

Looks neat, I don't remember needing a trick like this, but maybe I will
now that I know it.

Minor nit: I think I'd create the list like so:

(maplist #'identity list)

Would that be equivalent?

But if using LOOP, couldn't you omit the "by #'cdr" part anyway, due to
ON?

Zach

[Daniel Rupis]

Another, perhaps better option, is to use a hash with keys the index and value the cons of the list.

(defun list->hashcons(l)
(loop with h = (make-hash-table :size (length l))
for i from 0 for cons on l do (setf (gethash i h) cons)
finally (return h)))

Time to eat, no time for debugging.

[Pascal J. Bourguignon]

I've put conses in lists, but I didn't have to put them in a vector.

(coerce (maplist 'identity '(1 2 3)) 'vector)
--> #((1 . #1=(2 . #2=(3))) #1# #2#)