Scratch

blob8108 wrote:

Okay, this is getting complicated. Are you thinking something like "set x to (1 in front of (2 in front of x))"?

No, in that case the circular part reaches all the way back to the head of the list.  You can't set up the thing I mean in one step.  It has to be

set X to (1 in front of (2 in front of X))
set Y to (a in front of (b in front of X))

Then Y is the list (a, b, 1, 2, 1, 2, ...)

Actually even that might not really work -- the SET X will fail because X doesn't already have a value.  Certainly it doesn't already have the right value.

Jens, we need a set-cdr! block.   

Or find whether a list is circular in time linear in the number of unique elements. 

I don't understand this one. (Which is probably ironic...  ) If it's not nested, you can just do:

    for item in list:
        if item is list:
            return item

Again, you are assuming that the circularity is at the head of the list.  For each item in the list, you have to check whether that item is either the list or any tail of the list.

It's not hard to solve this problem in quadratic time.  (But you have to be careful not to take infinite time if the list is, in fact, circular.  We want an answer either way, in finite time.)  Making it linear time (oh, and, btw, constant space) is one of those problems that hardly anyone gets -- someone has to show you, as part of your initiation into the mysteries.

I thought the same — I've been reading the first chapter of SICP over the past few days. (The new Kindles have this awful feature that predicts how long it will take you to finish, and for SICP it claims about 16 hours...) Maybe I should try some of the other exercises from that? Though I thought it was more about language theory...

SICP is about the deepest mysteries of the universe.  It explains the meaning of life.  Those who haven't read SICP are ignorant of computer science.  (Yes, ignoramuses are legion in highly paid jobs in the computer industry.)  (Ignorami?  Ignorames?)  They are callow youth, gambolling in the fields.

Do the exercises.  All of them.  It's not like your high school algebra book, with 50 identical-except-for-the-numbers equations to solve in the same way.  Every exercise teaches a specific new idea or skill.

Last edited by bharvey (2012-11-29 13:15:11)

bharvey wrote:

SICP is about the deepest mysteries of the universe.  It explains the meaning of life.

Where? On page 42? I didn't see it...

blob8108 wrote:

Okay, this is definitely making my brain hurt now. 

Always a good sign.

I think I understand Snap! lists a bit more. They're, so they either take the form of a "cons", having attributes:

    first -> first item
    rest -> a list containing the remaining items

Or a normal JS array, where all the items are found on the "contents" attribute.

Right? (Sorry, I'm being slow here.)

So what I think you're trying to do is set up a list "list" where "rest" = "list". Am I right?

You're not being slow.  I'm being slow, for not remembering that REPLACE ITEM (n) OF (list) WITH (value) converts the list into array format.  (Jens just emailed to remind me that I wrote this code.)  That's a misfeature, I now think.  I'll work on it.

The goal of the complexity of list implementation is that Scratch-style iterative list processing should continue to work efficiently (constant time, not linear time, for ITEM, INSERT, etc.), but also Scheme-style recursive functional list processing should work efficiently (constant time IN FRONT OF and ALL BUT FIRST OF).

The only thing that's inefficient is mixing styles with the same list, first doing ALL BUT FIRST OF and then doing INSERT etc, because then the list gets converted from one form to the other repeatedly.

What's confusing you is that when we agreed on this design, I had in mind that the use of car/cdr lists would always be purely functional.   So we didn't provide for SET-CAR! or SET-CDR! equivalents.  I'll work on that...  as soon as I get out from under writing grad school recommendation letters for Berkeley students.  It's that season, as you know.

So, don't feel bad, you're doing as well as possible, given the current limitations of Snap! list processing.

bharvey wrote:

Or find whether a list is circular in time linear in the number of unique elements. 

I don't understand this one. (Which is probably ironic...  ) If it's not nested, you can just do:

    for item in list:
        if item is list:
            return item

Again, you are assuming that the circularity is at the head of the list.  For each item in the list, you have to check whether that item is either the list or any tail of the list.

It's not hard to solve this problem in quadratic time.  (But you have to be careful not to take infinite time if the list is, in fact, circular.  We want an answer either way, in finite time.)  Making it linear time (oh, and, btw, constant space) is one of those problems that hardly anyone gets -- someone has to show you, as part of your initiation into the mysteries.

I did it in linear time and linear space (and JavaScript  ).

function isCircular(list) {
    var flag = {}; // any unique value
    !function f(list) {
        if (isEmpty(list) || isList(car(list)) && car(car(list)) === flag) return;
        setCar(list, cons(flag, car(list)));
        f(cdr(list));
    }(list);
    return function f(list) {
        if (isEmpty(list)) return false;
        if (!isList(car(list)) || car(car(list)) !== flag) return true;
        setCar(list, cdr(car(list)));
        return f(cdr(list));
    }(list);
}

I'm still working on constant space.

Last edited by nXIII (2012-11-30 07:26:36)

fullmoon wrote:

and the lack of first-class procedures is driving me nuts!

But of course lambda isn't all of SICP; it's in Chapter 1 (of 5).  Really understanding OOP, for example, comes in Chapter 3.  Understanding compilers in Chapter 5.  Declarative (logic) programming, Chapter 4.
And so on.

Found a linear time, constant space, tail recursive test for circularity written in scheme.

(define (circular? x) 
 (let race ((hare x) (tortoise x)) ;;hare and tortoise algorithm
     (if (pair? hare)
         (let ((hare (cdr hare))) 
            (if (pair? hare) 
                 (or (eq? hare tortoise)       
                     (race (cdr hare) (cdr tortoise)))
                 (circular-on-cars? x)) 
     (circular-on-cars? x))))

It's linear time because as it traverses the list the hare is one more ahead of the tortoise each time, so if it is circular it will go round the list once before it catches up, otherwise it will hit the end of the list.

My circular on cars procedure is linear space    (it probably has too many opening or closing parenthesis too but i can't be bothered to check)

(define (circular-on-cars? x)
 (let ((unique-value (cons '() '())))
       (let helper ((x x) (callback (lambda () #t)))
             (cond ((not (pair? x)) (callback) #f) ;;just call for the side effect of putting all the cars back and report false instead of true
                   ((eq? (car x) unique-value) (callback))
                   (else (let ((old-car (car x))) 
                               (set-car! x unique-value)
                               (helper (cdr x) (lambda () 
                                                    (set-car! x old-car)
                                                    (callback)))))))))

Last edited by joefarebrother (2012-12-07 17:13:39)

bharvey wrote:

joefarebrother wrote:

(let race ((hare x) (tortoise x)) ;;hare and tortoise algorithm

Great!  Does "found" mean, like, "found in Google," or did you independently invent this?

I found it when reading through a few CS textbooks but I changed a letrec for a named let and added circular-on-cars?

Last edited by joefarebrother (2012-12-07 17:15:33)

What would the cloud thing on snap eventually do when it works? Will it be saving projects in the cloud, or something like cloud variables in 2.0, or some way to connect projects like mesh via the cloud, or is it something else?

bharvey wrote:

So I can argue with Shadow about politics 

Looking forward to it. 

On my iPad (2 running iOS 6) Snap! works brilliantly (for a web app!), but it's dreadfully slow. Maybe I'm spoiled with Apple's fluid scrolling, but I would really like some speed optimizations.

You can now "snap" comments to blocks in http://snap.berkeley.edu/run, in the main scripting area. Then if you move the block the comment follows.
Enjoy!

I don't know if that is worth of interest or not ? I've installed on a Windows XP PC a server , xampp, which allows to use Snap! locally. It works pretty well, better with Firefox than Chrome. Snap! projects can be loaded and saved as usual.