[plt-scheme] creating nested lists in DrScheme

From: Stephen Bloch (sbloch at adelphi.edu)
Date: Fri May 7 23:39:27 EDT 2010

On May 7, 2010, at 10:42 PM, Aniket Karmarkar wrote:

> This is what I am trying to do.
> Write the function partialpaths, of two arguments. The first  
> argument is a list of lists, representing a graph(adjacency list  
> representation of a graph). The second argument is a partial path  
> in the reverse order, for example the path "from a to b to c" is  
> represented by the list (c b a). The function should return a list  
> of sublists containing all possible expansions of this partial path  
> by one node. For example: (partialpaths '( (a b c) (b c d) (c d a)  
> (d)) '(b a)) should return: ( (c b a) (d b a))
> I get the (b c d) part now I need to attach the cdr of this to b a  
> multiple times so I try putting it in a loop.
> Here's what I have:
> (define nod ())
> (define ma '('()))
> (define (partialpaths L1 L2)
>   (set! nod (equal L1 L2))
>   (do()
>     ;exit test
>     ((null? (cdr nod)))
>     (list ma (attach(cdr nod)L2))
>     (set! nod (cdr nod))
>   )
>   ma
> )

Yigg.  Are the loop, the mutation, and the global variables really  
necessary?  With all due respect, this doesn't look like Scheme code  
to me :-)

> (define (attach List1 List2)
>   (list (car List1) List2)
> )

This almost certainly doesn't do what you think it does.

Seems to me what you want to do is extract the first (i.e. last)  
element of the path, find the row of the table that starts with it,  
and cons each of the other elements of that row onto the path.

So off the top of my head, I would define a variable equal to (car  
path), then another equal to the row (if any) in the adjacency matrix  
whose car matches it (this may require a helper function), then map  
over the cdr of the row a function which conses its argument onto the  
path.  I did this in about six lines (not counting test cases) with  
no loops, no mutation, no global variables, and only one recursion  
(in the helper function).

Stephen Bloch
sbloch at adelphi.edu

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20100507/cce75e03/attachment.html>

Posted on the users mailing list.