hello again - what’s the cost of using things like first, second, third, etc.? do they scan the list linearly?

They are all O(1).

(second xs) is the same as (first (rest xs))

and (third xs) is the same as (first (rest (rest xs)))

thanks @soegaard2, I know they are, but are they literally like (first (rest (rest xs)))) - as in, following the car pointer, then following the new car pointer, etc.?

or does the implementation build pointers to point directly to the second item, the third, etc.?

Let’s for second assume that (second xs) literally is (first (rest xs)). Then we don’t need to know the underlying representation. We can simply say: time[second] = time[first]+time[rest]=O(1)+O(1)=O(1).

If we think in terms of the underlying representation in memory, then a pair consists of a type tag, a pointer to the first element and a pointer to the next pair.

(first xs) simply returns the first pointer in a pair and rest returns the second pointer in a pair.

This is slightly simplified (some values like booleans and fixnums are usually stored directly in a pair without needing a pointer instead of as a pointer to the value).

yes, so the implementation doesn’t keep a pointer to ‘second’, another one to ‘third’ etc., right?

right

If you need the last element of a list, you will need to follow all the next pointers and that will take time O(n), where n is the length of the list.

ok thanks - I guess it’s a similar thing for split-at?

in that case, the cost being O(n)

Yes.

The only surprising (if you are used to Scheme) fact is that list? runs in time O(1).

great, thank you!

hello, how do I plot a line from a list of points? say I have something like ’((1 2) (2 3) (3 4)) - I want to plot a line that connects these points

#lang racket
(require metapict)

(set-curve-pict-size 400 400)
(defv (xmin xmax) (values -2 10))
(defv (ymin ymax) (values -2 10))

(with-window (window xmin xmax ymin ymax)
  (ahlength (px 10))
  (draw (curve (pt 1 2) -- (pt 2 3) -- (pt 3 4))
        (draw-arrow (curve (pt xmin 0) -- (pt xmax 0)))
        (draw-arrow (curve (pt 0 ymin) -- (pt 0 ymax)))))

ah, very nice, thank you - can I pass the list of points as an argument?

(and perhaps add numbers to the axes too?)

(define (lines xs)
  (curve* (add-between (map (λ(p) (apply pt p)) xs) --)))

(with-window (window xmin xmax ymin ymax)
  (ahlength (px 10))
  (draw (lines '((1 2) (2 3) (3 4)))
        (draw-arrow (curve (pt xmin 0) -- (pt xmax 0)))
        (draw-arrow (curve (pt 0 ymin) -- (pt 0 ymax)))))

You can also use plot: https://docs.racket-lang.org/plot/index.html?q=plot

thank you!

I am getting comfortable with the base racket syntax, but I always learn best by reading other well structured code.

Could any one recomand any idiomatic open source projects which aren’t huge and are fairly self contained?

https://github.com/soegaard/breakout/blob/master/breakout.rkt

Also checkout the blog posts on http://racket-stories.com\|racket-stories.com

Flappy Bird is also available (the source becomes readable when you open it in DrRacket): https://github.com/soegaard/flappy-bird/blob/master/main.rkt

Thanks! Those look like fun projects to explore. I also had no idea about http://racket-stories.com\|racket-stories.com definitely going to keep up with it :slightly_smiling_face:

If you find interesting (old or new) blog posts on Racket, please submit them to Racket Stories.

will do!