Summary ¹.

First off, this is not a post on how to solve LeetCode problems.

This post is intended to be a showcase of the funny edge cases you’ll inevitably run into doing something like this, with practically zero Racket-experience. This was an exercise in blogging (and an excuse for me to offer my unsolicited opinions on a relatively obscure programming language, when used in a domain it was never really intended for.)

Since this article ended up pretty long, here’s a short summary of some (more or less) interesting findings:

• Using Racket, you’ll always score at the very top of the LeetCode leaderboards: Better than 100% of solutions with regard to speed and memory usage.
• There’s a whole bunch of LeetCode problems which are, as stated, impossible. You can beat them anyway, by bending the rules.
• Racket code is generally handled top-to-bottom like Python, except when you define variables, whose non-existence will travel back in time.²
• Weird floating point issues are fun, especially when coupled with a fraction type.
• Unexpected eager evaluation of iterators is a fun performance footgun.

Background

You already know what LeetCode is, but for the sake of completeness: It’s a website primarily used by (aspiring) software engineers to practice short algorithmic problems (FizzBuzz, but harder) in preparation of job interviews. The primary languages used for this are (presumably, I have no concrete data for this, and I don’t think LeetCode makes it easily accessible) Java, Python, C++, Javascript: All big names, commonly featured in ’top programming languages’ lists, and used in services across the world.

Like many others, I used LeetCode to prepare for job interviews.

Unlike many others, and for reasons incomprehensible even to myself I eventually decided to complete LeetCode’s daily problems using Racket.

Racket looks like this:

; Definition for a binary tree node.
; val : integer?
; left : (or/c tree-node? #f)
; right : (or/c tree-node? #f)
(struct tree-node
  (val left right) #:mutable #:transparent)

(define/contract (all-possible-full-binary-trees n)
  (-> exact-integer? (listof (or/c tree-node? #f)))
  (if (= n 1)
    (list (tree-node 0 #f #f))
    (flatten
      (for/list ([k (in-range 1 (- n 1))])
        (map
          (lambda (vals) (apply tree-node vals))
          (cartesian-product
            (list 0)
            (all-possible-full-binary-trees k)
            (all-possible-full-binary-trees (- n (+ k 1)))))))))

Racket can reasonably be described as ‘obscure’. It’s a type of Lisp (a ‘dialect of Scheme’, if you want to be precise). Racket is younger than Python, which stands in pretty stark contrast to the family of Lisps as a whole, which happens to be significantly older than C. (Honestly, I found that to be a pretty shocking revelation when I first heard it.)

(You might think that this makes Racket a nice, modern language, but no, not really? Not by Go’s or Rust’s standards. It has a lot of what I presume to be Scheme-baggage. Why yes, my 1995 programming language uses obscure assembly keywords from the late 50s, how could you tell?)

Looking at the yearly Stackoverflow Developer Survey, the only Lisps represented are “Lisp” (presumably a broad catch-all term) and Clojure, both with slightly over 1% usage.

Going into this, all I knew about Lisps are a few historical tidbits (did you know that Lisp essentially invented many features we take completely for granted nowadays?), and that they (supposedly) have a bomb-ass macro system that will take several months to truly internalize, and which will grant you dark, deep powers once you’ve finally gotten there.

Frankly, the fact that Racket, a language with remarkably little enterprise industry adoption, and whose code looks like arcane gibberish to anyone who’s only ever used Python or C is even an option on LeetCode should make you pause. I am not complaining, though. Props to the LeetCode people for putting in the work.

So, what’s Racket’s “pitch”? Most languages have a pretty good one as they come into existence.

If you ask around, you’ll frequently hear that Racket’s primary purpose is the design of (domain-specific) programming languages. In fact, some people write outrageous, wonderful, elaborate jokes whose punchline boils down to “Let’s use a Lisp to do something unhinged you could never do in any other language.”

It’s a good punchline! This is what Racket excels at. You start with a simple language concept, and are able to prototype it, and use Racket’s macros to ‘rewrite the syntax’ to seamlessly transpile your language into Racket at runtime. In other words, “just” using any other language (referencing Matthew Butterick’s ‘Beautiful Racket’) is something you can do in Racket (with all the work that entails, of course), and which would be essentially impossible anywhere else.

#lang basic
10 x = 2 : y = 3 : z = 5
20 print f(3, 4)
30 print f(f(3, g(2)), 2)
40 def f(x, y) = x * y * z
50 def g(i) = i + i
60 print y

Sadly, in this post we’re not going to do anything of that, instead we’ll use Racket to bash our head against silly, algorithmic puzzles.

However, since my experience can be summed up as “a few days of fucking around and finding out”, I apologize in advance for my terrible code. Feel free to skip over code as you please, it’s really not critical to understand it in detail.

A first problem, and a quick primer on Racket

735. ‘Asteroid Collision’ (2023-07-20)

For the sake of intellectual honesty, here is my very first Racket program. Behold:

(define/contract (asteroid-collision asteroids)
  (-> (listof exact-integer?) (listof exact-integer?))
  (let loop
    (
      [head empty]
      [tail asteroids]
    )
    (if (empty? tail)
      (reverse head)
      (if (or (empty? head) (negative? (car head)))
        (loop (append (list (car tail)) head) (cdr tail))
        (if (negative? (car tail))
          (cond
            [(= (abs (car head)) (abs (car tail))) (loop (cdr head) (cdr tail))]
            [(< (car head) (abs (car tail))) (loop (cdr head) tail)]
            [else (loop head (cdr tail))]
          )
          (loop (append (list (car tail)) head) (cdr tail))
        )
      )
    )
  )
)

In the interest of everyone else, here is a significantly cleaner solution by the single other person on LeetCode who is using Racket. Sadly, they’re now even-more impossible to track down due to changes in LeetCode’s interface, so it’s hard to give credit.

(define (asteroid-collision asteroids)
  (let loop ((asteroids asteroids) (acc '()))
    (cond
      ((null? asteroids)
        (reverse acc))
      ((or (null? acc) (positive? (car asteroids)) (negative? (car acc)))
        (loop (cdr asteroids) (cons (car asteroids) acc)))
      ((= (- (car asteroids)) (car acc))
        (loop (cdr asteroids) (cdr acc)))
      ((< (- (car asteroids)) (car acc))
        (loop (cdr asteroids) acc))
      (else
        (loop asteroids (cdr acc))))))

What this code is doing is (essentially) ‘iterating’ through the input list asteroids, while keeping track of a second list (acc) of already considered asteroids. At each step we consider if some new asteroid collides with those on our new list or not.

If you’ve never interacted with Racket before, here’s a summary you might find insightful:

• Everything is an expression, ie. returns a value.
  • A Racket file is evaluated top to bottom. Each line is evaluated and its output is printed. If you’ve ever used Python’s Read-Eval-Print-Loop (REPL), you get the idea. In practice, this isn’t quite correct. Racket macros (which are indistinguishable from ordinary function calls) get expanded before any evaluation happens. For example, the and macro (boolean operator) gets expanded to a chain of nested if expressions. (Isn’t that kind of crazy?)
• Everything is a (linked) list.
  • The function call (do-stuff x y) expression is a list whose first element is the name of the function we want to call, followed by the arguments.³
  • Even common logical or mathematical operators are written as lists: (< x y).
  • In each case, the first element of the list (the head) is applied to the rest (the tail).
  • Many languages have special syntax to define new variables, eg. let a: i32 = 0;. In Racket, let and define are “called” like functions: (define a 0).
  • To write a “list literal” (ie. a “normal” list of integers) you need to write (list 1 2 3). Otherwise, Racket will complain that 1 is not a procedure and cannot be applied to the tail of the list.
• Everything is based on recursion.
  • As far as I can tell, there are no ’traditional’ for loops, it’s all just syntactic sugar for recursion.
  • If you’ve done functional programming before, you’ll feel right at home using foldl.
• Everything is weird.
  • Using arrays or hash maps is incredibly painful.
  • In Racket, you can redefine the define and the let functions: (define define "Huh?"). (Don’t do it, it’s a terrible idea.)
  • There are many, many helper functions that do exactly what they say they do, eg. negative?.
  • There are many helper functions whose naming is complete gibberish, eg. car (which returns the first element of a list), and cdr (which returns the entire rest of the list), as well as caar, cadr, cdar, cddr, caaar, caadr, cadar, caddr, cdaar, cdadr, cddar, cdddr, caaaar, caaadr, caadar, caaddr, cadaar, cadadr, caddar, cadddr, cdaaar, cdaadr, cdadar, cdaddr, cddaar, cddadr, cdddar and cddddr. (Yes, really. Yes, these are all just shorthands for repeated applications of car and cdr.)
  • Discoverability is kind of bad. You know how in a lot of languages you can write foo., and your editor will give you a nice list of available options? Yeah, that’s kind of difficult here. I’m spoiled by modern LSPs, of course, but it’s hard to imagine Lisp-languages ever bridging this gap.

Now let’s return to our code, this time with annotations:

(define/contract (asteroid-collision asteroids) ; define a function 'asteroid-collision' with a single argument.
  (-> (listof exact-integer?) (listof exact-integer?)) ; define contract ('types'). throw on violation
  (let loop ; define a function 'loop' in this scope, then immediately evaluate it
    (
      (asteroids asteroids) ; pass 'asteroids' to loop
      (acc '()) ; pass an empty list as the 'accumulator' to loop
    )
    (cond ; if-elseif chain. Match based on first true expression
      ((null? asteroids) ; if asteroids is null, we're done.
        (reverse acc)) ; return reversed accumulator once we're done
      ((or
          (null? acc)
          (positive? (car asteroids))
          (negative? (car acc))
       ) ; if any condition is met, move the first element from asteroids to acc, then call loop
        (loop (cdr asteroids) (cons (car asteroids) acc)))
      ((= (- (car asteroids)) (car acc)) ; if two asteroids with same weight hit each other
        (loop (cdr asteroids) (cdr acc))) ; then remove both
      ((< (- (car asteroids)) (car acc)) ; otherwise, if right-moving asteroid is larger
        (loop (cdr asteroids) acc)) ; remove the first asteroid moving to the left
      (else ; else remove the first asteroid moving to the right
        (loop asteroids (cdr acc))))))

If you’ve paid close enough attention, you’ve already seen me slip one cute edge case past you without even bothering to mention it, and on top of that, it’s in the very first line.

(define (asteroid-collision asteroids)
  ; ...
)
; vs.
(define/contract (asteroid-collision asteroids)
  (-> (listof exact-integer?) (listof exact-integer?))
  ; ...
)

The standard Racket LeetCode template will start you off with define/contract, and ask you to fill in the blanks. define/contract and define are (for our purposes) really not particularly different. The contract just tells us that we have certain expectations when it comes to the data passed into and returned from this function. This is not static typing, it just inserts runtime checks, and will cause function calls to throw if the contract has been violated during execution.

The funny thing is that there’s really nothing that forces us to use the contract LeetCode started us off with. We can just…remove it. The function signature looks typed, it will throw if the contract is violated, but nothing stops us from changing the contract, and this is not checked by whatever LeetCode uses to evaluate our code.

You might think “So what’s the big deal? It’s not statically typed, just runtime-enforced contracts.” and you’re completely right. That said, the trick is going to come in handy soon.

Other than this, it’s worth pointing out that–when completing a LeetCode problem in Racket–you can generally expect to receive perfect scores of “beats 100% of other users” for both runtime and memory, for the simple reason that the number of people who regularly use this language is somewhere in the respectable single digits. The new UI will even state “Sorry, there are not enough accepted submissions” and refuse to plot a graph.

Apart from all of that, there’s so far nothing weird going on. We’ll get to that soon.

More problems!

For now, two cute smaller problems just to warm ourselves up.

894. ‘All Possible Full Binary Trees’ (2023-07-23)

Recursion. This is where Racket excels, at least in theory. Oh also! We get to see how structs in Racket are defined, exciting! (Yes, structs in fact exist in Racket. Not everything is a list, apparently. I was as shocked as you are. No, we’re not going to use them after this point.)

; Definition for a binary tree node.
; val : integer?
; left : (or/c tree-node? #f)
; right : (or/c tree-node? #f)
(struct tree-node
  (val left right) #:mutable #:transparent) ; don't ask me what 'transparent' means

(define/contract (all-possible-fbt n)
  (-> exact-integer? (listof (or/c tree-node? #f)))
  (if (= n 1)
    (list (tree-node 0 #f #f))
    (flatten
      (for/list ([k (in-range 1 (- n 1))])
        (map
          (lambda (vals) (apply tree-node vals))
          (cartesian-product
            (list 0)
            (all-possible-fbt k)
            (all-possible-fbt (- n (+ k 1)))))))))

It’s honestly not too bad, I think. I’m thinking about how incredibly painful it’d be to write this sort of thing in C, and honestly? I think I prefer this.

Nothing to see/say here, let’s look at something slightly funnier:

50. ‘Pow(x, n)’ (2023-07-24)

“Implement pow(x, n), which calculates x raised to the power n.”

Alright, let me just…

(define/contract (my-pow x n)
  (-> flonum? exact-integer? flonum?)
  (expt x n)
)

Looking good.

Line 1: Char 19: my-pow: broke its own contract
promised: flonum?
produced: 1

Huh? Oh. Well, I guess 1 is technically not a floating point number, so how about…

(define (my-pow x n) (expt x n))

And done. Thinking outside of the box. If you can’t make it work, just change the type signature. We can also solve this problem legitimately, it’s just annoying:

(define (my-pow x n)
  (if (negative? n)
    (/ 1. (power x (- n)))
    (power x n)))

(define (power x n)
  (cond
    [(zero? n) 1.]
    [(= n 1.) x]
    [(even? n) (let ([val (power x (/ n 2))]) (* val val))]
    [else (* (power x (floor (/ n 2))) (power x (ceiling (/ n 2))))]
  )
)

And when I say ‘annoying’ I genuinely mean ‘bad for my continued sanity’. It’s probably just a familiarity issue, but staring at a mess of parentheses while debugging sooner or late just hurts my head, and sometimes it gets remarkably fiddly in ways you just aren’t going to see coming.

There’s reasons why people use bespoke IDEs for Lisps (Dr Racket, Emacs, etc.): Anything that makes it easier to see where exactly one expression ends and the next begins helps.

Onwards:

673. ‘Number of Longest Increasing Subsequence’ (sic!) (2023-07-21)

A variation on a classic, with a description short enough that we might as well just quote it: “Given an integer array nums, return the number of longest increasing subsequences. Notice that the sequence has to be strictly increasing.”

My code is quite terrible. Not just because I’m terrible at writing Racket (with approximately three hours of experience at that point), and also not just since I (on a whim) decided to see if it’d be possible to go for a ’traditional’ imperative, side-effect-heavy approach with a vector and for-loops (no fancy recursion tricks, as god intended).

You’ll also see that my formatting is all over the place. (I’m pretty sure in certain Lisp-circles you’ll get crucified for putting closing parentheses onto their own lines.)

Feel free to read the code and see if you can figure out how it works, but I don’t think there’s any insights here. It’s not too complicated–the syntax is weird, but this could be translated to Python or even C++ in a pretty straight-forward manner.

(define/contract (find-number-of-lis nums) (-> (listof exact-integer?) exact-integer?)
  (define nums_v (list->vector nums))
  (define n (length nums))
  (define len (make-vector n 1))
  (define count (make-vector n 1))
  (for ([i (in-range n)])
    (for ([j (in-range i)])
      (if (< (vector-ref nums_v j) (vector-ref nums_v i))
        (begin
          (if (< (vector-ref len i) (+ 1 (vector-ref len j)))
            (begin
              (vector-set! len i (+ 1 (vector-ref len j)))
              (vector-set! count i 0)
            )
            empty
          )
          (if (= (vector-ref len i) (+ 1 (vector-ref len j)))
            (vector-set! count i (+ (vector-ref count i) (vector-ref count j)))
            empty
          )
        )
        empty
      )
    )
  )
  (let ([max_length (vector-argmax identity len)])
    (apply +
      (for/list (
        [x count]
        [l len]
        #:when ((lambda (y) (= y max_length)) l))
        x
      )
    )
  )
)

Anyway, during my journey I discovered that ‘redefining’ a variable, or ‘shadowing’ is just not…particularly well-supported by Racket. I’m still unsure on the details, you’ll see what I mean.

So, it turns out that apparently the whole (define ...) statement which we love to use (it lets us define variables) apparently has some really weird, gnarly global interactions which (essentially) make it look like parts of your code are travelling back in time to cause trouble.

Let me explain: Essentially, if I’m understanding it correctly, all (define ...) statements in a scope are handled before the expressions. This is, presumably just part of macro-expansion happening at pre-evaluation time.

The consequence of this is the following: If you try to re-define a variable that already was defined, you’ll get an “already defined” error.

If, however, you try to re-define a variable which hasn’t been defined (for example, you’re in a function call, and this variable was a parameter), then this will essentially ’erase’ the variable before the definition point. In other words, the (define ...) statement retroactively makes it impossible to use the variable before define is used.

For example:

; Completely fine
(define (fun1 x)
  (define y x)
  ; (define x 1)
  x)

; Completely fine
(define (fun2 x)
  ; (define y x)
  (define x 1)
  x)

; bad
(define (fun3 x)
  (define y x) ; throws a "can't use before initialization" error on THIS line
  (define x 1)
  x)

(fun1 '(1 2 3))
(fun2 '(1 2 3))
(fun3 '(1 2 3))

To me, this is pretty confusing. If Racket just wanted to disallow variable shadowing, that’d be fine. If it just stepped through the commands one-by-one and it’d work as expected, also fine.

It’s worth pointing out that Racket is a compiled language here, which makes this behavior doubly confusing. In most compiled languages, ‘use before initialization’ bugs are caught at compile-time. This one here is similar, except that when you run

#lang racket
(define (fun x)
  (define y x)
  (define x 1)
  x)

(displayln "Hello!")

It will happily compile and run the program, with no errors at all. In other words, despite the broken code, and despite a compile-time define statement, the error isn’t discovered unless our code runs into the exact line where it happens.

There’s probably reasons for this, but they’re beyond me at my the broken code, and despite a compile-time define statement, the error isn’t discovered unless our code runs into the exact line where it happens.

There’s probably reasons for this, but they’re beyond me at my current level. For me, it just makes me think that I can’t imagine Racket macros are remotely easy to debug.

But, let’s step back for a second. Even apart from the weird, wacky behavior of define, I feel like writing certain types of code in Racket just doesn’t feel particular good to me so far.

Granted, this is my own fault, but it’s worth pointing out that Racket is weird. Lisps are weird. Vectors and arrays feel a bit like second-class citizens, which is strange coming from literally any other mainstream and general purpose language. I can only imagine how much worse hash maps would be.

Imagine, if you will, that you’re a young programmer who’s just started to learn how to code, and who hears about Lisp for the very first time.

You’ve seen memes about the Wizard Book, you’ve heard of Lisp’s powerful metaprogramming and macro powers, you’ve written some Python (and aren’t as good at it as you think you are), you’ve dabbled with some C (and are pretty proud of your quicksort implementation, while still struggling to read function pointer declarations). You’re ready to delve into this mystical, dark language, the masterful language in which Hackernews and Reddit are or were written in at some point.

You’re ready to have your mind blown. You’re ready to ascend, ready for enlightenment, maybe even ready to use Emacs.

You write your first little toy program just to get your fingers wet, and eventually write your very first

(vector-set! v i (+ (vector-ref v i) (vector-ref v j))) ; v[i] += v[j]

You stare at it for a good two minutes, blink, and close your laptop.

…Sorry, I’m being facetious. Lisp means List Processing for a reason. That everything, including your source code is just a tree of nested list is part of its “superpowers”. (Racket sure likes to bend that rule, but I assume that anything that doesn’t look like a list in Racket is just somehow part of a macro, and will be syntax-transformed into a list.)

Second, these tiny, frequently imperative algorithmic challenges are just not built with a language such as Racket in mind (nor was Racket built with them in mind). This becomes increasingly clear in the following problem:

852. ‘Peak Index in a Mountain Array’ (2023-07-25)

Very simple. You get handed an array of integers. The elements are in strictly increasing order, then eventually hit a ‘peak’, and from that point they are in strictly decreasing order. Find the peak.

Also, uh, “You must solve it in O(log(arr.length)) time complexity.”

There it is. That means some sort of binary search. Do you see the problem yet?

(define/contract (peak-index-in-mountain-array arr)
  (-> (listof exact-integer?) exact-integer?)
  ; ...
)

Racket’s primary data structure is a (linked) list. We receive a linked list for this problem (as opposed to a vector/array). We cannot index into a linked list in O(1)-time, therefore it’s impossible to solve this problem within O(log(n)) time.

Case shut and closed, it’s literally impossible.

All of this feels, in a sense, like a funny, cruel inversion of a classic Rust-joke: “You can’t write a linked list in Rust” (and variations on the theme). In Racket, it’s apparently incredibly hard to use anything but linked lists.

Anyway, this is fine, we can still write a linear-time solution, which iterates through the entire array once and tells us the index of the largest element. We might do this as follows:

(define/contract (peak-index-in-mountain-array arr)
  (-> (listof exact-integer?) exact-integer?)
  (index-of
    (for/list ; roughly: [ x < y for x, y in zip(arr[1:], arr) ]
      ([y arr]
       [x (cdr arr)])
      (< x y)
    )
    #t ; this is a boolean False
  )
)

This code works, and passes with flying colors (and excellent performance metrics, as expected).

When playing around with this code, I started benchmarking, comparing it to running Python code, and eventually stumbled upon the following unexpected footgun.

For this, let’s benchmark a simple example:

(current-process-milliseconds) ; milliseconds since startup. no `displayln` needed on top-level
(let ([huge-list (range 1e7)]) ; roughly, Python's range(10_000_000)
  (begin ; "execute multiple statements in a row". Necessary for prints.
    (displayln (current-process-milliseconds))
    (first ; return first element of a list, equivalent to 'car'
      (map ; apply function to each element of a list
        add1 ; yes, `add1` is a real function
        huge-list))
    (displayln (current-process-milliseconds))
  )
)

In Racket, we frequently use idioms such as for/list, or map. Most of these have a functional vibe to them. These sort of ‘Stream/iterator’ operators are common and idiomatic in many modern languages (with the exception of Go, of course, no I’m not salty why do you ask). If you’ve used them before, you might assume that the above code translates to something like this:

from time import thread_time_ns

t0 = thread_time_ns()
print(thread_time_ns() - t0)
hugeList = range(10_000_000)
print(thread_time_ns() - t0)
map(lambda x: x + 1, hugeList).__next__()
print(thread_time_ns() - t0)

Alas, if we do a bit of conversion and compare the deltas directly we get the following:

First of all, I assume this is common knowledge, but Python’s range function doesn’t actually allocate a massive list of integers. It’s just a generator, which produces values lazily, whenever they are needed. This is vastly more efficient, since the tuple of integers (lower_value, current_value, upper_value, step_size) is really all you need to store all of that data for an arbitrarily vast range. Four integers vs. n integers.

Similarly, Python’s map creates a lazy iterator which applies the function whenever it is needed, and not immediately. It just keeps track of the lambda, and of the iterator which it is consuming. (This brings with it its own footguns, but that’s a topic for another day.)

Racket, on the other hand? Well, Racket’s range creates the entire list element by element, and its map does the same. It consumes a list and spits out a list, and in hindsight it is completely obvious that this stupid-simple, non-optimized behavior is of course) what you’ll get, once you understand that Racket’s lists are, in fact, not lazily evaluated (ie. there’s no magic under the hood, and they’re not like Haskell’s lazy lists). The closest you’ll get to ‘magic’ is tail-recursion, really.

Anyway, how do we solve these problems?

There’s ways around this…sort of. For example, Racket has an in-range function which will create a ‘stream’, which is essentially just a generator.

However, if we try to replace range with in-range in our Racket code, we’ll get an error since map expects to receive a list, and not a stream. To make our code work, we need to, well, use the stream-equivalent for every single stream-operator we might want to use. stream-map, stream-filter, stream-first, and so on.

So far, so good! We can just rewrite our code by replacing all the ‘ordinary’ “list” functions with their stream equivalents, and then everything will be fine, right?

Well, yes. It works and the overhead disappears completely.

But: Not all list-functions actually have a proper stream-equivalent, so there’s a good chance it won’t work at all. So in other words, we can replace first with stream-first, but second cannot be replaced with stream-second since stream-second doesn’t exist. Great!

Essentially, moving between ‘use this as a list’ and ‘use this as a stream’ is significantly more painful than it has any right to be. It makes Racket feel “low-level” in some weird, vague sense I find difficult to pin down: It feels like an implementation detail. Why can’t first work on lists and for streams? Where’s the ‘magic’ that was promised to me? Why is this so clunky? Would this require Racket to inspect the value it receives at runtime, to determine whether it’s a list or a stream, and this is (for whatever reason) just impossible?

Interestingly though, stream-map has no problems whatsoever handling lists. We do not need to use any sort of conversion function to transform a list to a stream first. Considering this, I frankly feel like there’s few situations in which I’d ever want to use map, if I can just immediately reach for stream-map, and gain some performance benefits. Stuff like this, as an enjoyer of statically-typed languages, makes me question my sanity. (In all fairness, typed Racket also exists. I have not used it.)

Tying all of this back to the original LeetCode problem, my first few solutions, including the one at the start of this section allocated new lists of the same length as the input-list, inadvertently resulting in a space-complexity of O(n) rather than O(1)! I did not see that one coming, and I can only imagine that this issue right here might be the crux why at least some Racket code out there is performing significantly worse than you’d expect. (To be fair, Racket should not be your language of choice if you care about performance.)

Anyway. All of this is just a roundabout way of stating that

• It is literally impossible to solve the LeetCode problem within the constraints.
• Of course, this won’t prevent our solution from passing at 100%/100%, since there are ~0 other solutions.
• Watch out if you’re using map, filter, etc., it’s remarkably easy to allocate vast amounts of memory by accident.

On a positive note, the ability to pass around functions however you please, and to apply transformations on containers are absolutely remarkable. Not really by modern standards, no, but historically.

Remember, Lisp is from ~1960, it is 12 years older than C, and anything even remotely similar to this is a tremendous, absurd pain in C for many, many reasons. I can see where Lisp got some of its status from: If you’ve only ever coded in C, many of these (by modern standards relatively common) operations must surely look like black magic to you–and you might end up wondering how C even took off, ‘cause it sure looks like it took many, many steps backwards rather than forwards here.

This here is Racket, of course, rather than one of the ancient Lisp variants. I currently really don’t want to do an academic deep dive into those, but as far as I can tell ‘modern’ tricks such as “pass around a function, map/apply it to each element of a list” were already around. In fact, even Wikipedia has a historical tidbit on how the eval expression was added to the language.

I don’t fully understand how C just manages to lack so many features which Lisp has. Why have a ternary operator when if can just be an expression?

Assuming it wasn’t purely a matter of luck, popularity, and ‘worse is better’, I’d assume that memory usage and performance might’ve been deciding factors here. Lisp is powerful, but all this power comes with a certain overhead. This mattered a lot more back in the day: You might’ve heard how C-programmers used to eschew long variable names, since they made the resulting binary larger.

Anyway. Onwards to the day that finally broke me.

1870. ‘Minimum Speed to Arrive on Time’ (2023-07-26)

The problem itself is not too bad. It’s a cute principle, if you’ve never seen it before, and you’re not trying to use Racket.

Sadly, figuring out why the pieces weren’t coming together was an absolute pain, and had me rewrite the program several times over, first in Racket, and then in Python, until I ended up with two equivalent solutions that nonetheless returned different answers.

Once you’re in the “I’m rewriting it in a different language which I’m more comfortable with, since that seems more likely to help than trying to debug the language I’m actually trying to understand.” debugging hell, then you know that you’re pretty far gone.

For sake of completeness, here’s the Python:

from typing import List
import math

def minSpeedOnTime(dist: List[int], hour: float) -> int:
    if hour + 1 <= len(dist):
        return -1
    a = 1
    b = 10_000_001
    while a < b:
        mid = (a + b) // 2
        if check(mid, dist, hour):
            b = mid
        else:
            a = mid + 1
    return a

def check(v: int, dist: List[int], hour: float) -> bool:
    val = 0
    for x in dist:
        val = math.ceil(val)
        val += x / v
    return val <= hour

And here is the (buggy, non-passing!) Racket code:

(define/contract (min-speed-on-time dist hour)
  (-> (listof exact-integer?) number? exact-integer?)
    (if (<= (+ 1 hour) (length dist))
      -1
    (let step ; our 'for loop' is (tail call) recursion. We call `step` with new values of a and b
     ([a 1]
      [b 10000001])
      (let ([mid (floor (/ (+ a b) 2))])
        (cond
          [(<= b a) a]
          [(check mid dist hour) (step a mid)]
          [else (step (+ mid 1) b)])))))

(define (check v dist hour)
  (<=
    (foldl ; is it weird that I find this relatively readable at this point?
      (lambda (x acc)
        (+ (ceiling acc) (/ x v)))
      0
      dist)
    hour))

I’d tell you to go hunting for the bug, but frankly, I really don’t recommend it unless you see it right away, which is exceedingly unlikely unless you already have experience with Racket. I will reiterate that it took a long, long time to even get here, and a lot of mindless fiddling and going mad over why things are just not working as I expect them to. This describes worst experiences of using Racket quite well.

Errors can be maddening and confusing, behavior unexpected and weird, syntax somewhat tricky to get into your head, and at worst you really start hunting for whether each pair of parentheses was placed correctly. (Missing parentheses were usually not that much of an issue. Racket will tell you where one is missing. An additional pair in the wrong place, though, can be terrible, especially if the error message points at a completely different location.)

I debugged the testcase of dist=[1,1,100000], hour=2.01, shamelessly printing out the values of a, b, and mid in each iteration.

Both versions of the code had the same behavior all the way up to just before the final iteration:

  i=19: a=9999983  < mid=9999992  < b=10000001
  i=20: a=9999993  < mid=9999997  < b=10000001
  i=21: a=9999998  < mid=9999999  < b=10000001
  i=22: a=10000000 < mid=10000000 < b=10000001

  // Behold, the two genders:
  i=23: a=10000000 < mid=10000000 < b=10000000 // Python. Return value: 10000000
  // vs.
  i=23: a=10000001 < mid=10000001 < b=10000001 // Racket. Return value: 10000001

Python terminates here, and dutifully returns 10_000_000. Racket, on the other hand, doesn’t. If you’re confused, so was I. If you’re not confused and already know what’s going on, kudos, you’re faster at figuring this out than me.

If you want to take a stab at figuring this out yourself, now is the time. It might be tricky, but I can tell you that the issue happens inside of our check helper function. With that knowledge and the test case in hand, you might be able to see the underlying problem.

So.

Whether you’ve giving it some thought or not, let’s see what the problem is.

check compares two values at the end, and returns a true. We modify our code to print the values just before the return, and then call it: (check 10000000 (list 1 1 100000) 2.01). The result:

(<= 201/100 2.01)

You’ll notice a few things. First of all, that’s a fraction. A honest to god fraction. A precise mathematical object in full precision, that somehow magically appeared inside of our code as a result of handling a few integers.

Second of all, this apparently evaluates to False, and causes Racket to perform another iteration, and this explains the different results.

At this point the rest should be relatively clear, right? Clearly, 2.01 is represented as a floating point value. Clearly (even without checking) its representation must be smaller than that of 201/100. Clearly, for some godforsaken reason, Racket compares fractions to floating point values directly, rather than converting the fraction to a floating point value first, and this causes the problem.

Don’t judge me, but I was not trusting my sanity at this point, and it took me longer to figure this out. In particularly, I pulled the magical, bizarre incantation necessary to print a Racket floating point value in full precision out of a hat, and cast it:

; Racket
> (~r 2.01 #:precision '(= 49)) ; I really don't know what to tell you
2.0099999999999997854449166317430554797054768447488

vs.

# Python
> print(f"{2.01:2.52}")
2.0099999999999997868371792719699442386627197265625

Why are they different?

Actually, it turns out that if you ask Racket to print the same number at different levels of precision, it will in fact print a different decimal expansion. Why? I don’t know. At this point I’m not sure if I even care anymore. I see no rhyme or reason in it. Keep in mind that 2.01 is already a floating point value, so this can’t be the result of converting the fraction 201/100 to a float at different levels of precision. (Right? I hope so, at least.)

> (~r 2.01 #:precision '(= 10))
"2.0100000000"
> (~r 2.01 #:precision '(= 20))
"2.00999999999999978624"
> (~r 2.01 #:precision '(= 30))
"2.009999999999999786277863948288"
> (~r 2.01 #:precision '(= 40))
"2.0099999999999997863239159566376397438976"
> (~r 2.01 #:precision '(= 50))
"2.00999999999999978787880578418125593057914699907072"
> (~r 2.01 #:precision '(= 60))
"2.009999999999999786187243529025329839880491172228556296028160"
> (~r 2.01 #:precision '(= 70))
"2.0099999999999997876126532121526229858039502810065943725742729228976128"
> (~r 2.01 #:precision '(= 80))
"2.00999999999999978616934376258011154961549496679042195840328745866164573373988864"

In Racket, I am pretty sure that floating point numbers are standard 64-bit IEEE-compliant, so surely it can’t be that bad, right? Maybe it’s somewhere in the formatting macro? I don’t have the energy to investigate this any further.

Somehow, the elegance of Lisps is lost on me here, but it does make me wonder if, maybe, we’d live in a better world if all languages had built-in fractions. Floating point numbers really are weird.

So. How do we fix this? I reached for check and clumsily added a call to convert our number into a floating point value before comparing:

(define (check v dist hour)
  (<=
    (exact->inexact
      (foldl
        (lambda (x acc)
          (+ (ceiling acc) (/ x v)))
        0
        dist))
    hour))

Having done that, I took a deep breath, pressed ‘submit’ and prayed that it was going to work. It did, somehow.

Conclusion

My brain is pretty fried.

It’s honestly hard to write down a proper ‘conclusion’ for all of this.

I can’t say I particularly enjoyed Racket. It’s probably a ‘holding it wrong’ or a ’trying to use a screwdriver as a hammer’ sort of issue, but it still really makes me feel and wonder if, maybe, there’s a “better” Lisp-like language out there. One without all of these rough edges, one which feels nice and convenient instead of making you scramble for weird highly specific functions.

Granted, I’ve only spent some time with Racket, and I probably did it in the worst way possible. Racket is, probably, much more interesting if you approach it with a tinkerer-mentality, and mostly just plan to play around with the macro system.

Which, speaking of, I figured it’d be absurd to have a post on Racket without at least looking at the macro system for just a few lines. Sorry, that’s the best I can do at the moment.

Quoth Matthew Butterick:

(and cond-a cond-b cond-c)
; From afar, `and` looks like a function. But it's not.
; Rather, at compile time, this use of `and` gets expanded
; -that is, rewritten-so it looks like this:
(if cond-a
    (if cond-b
        cond-c
        #f)
    #f)

Doesn’t that sound much more fun? Macros! Syntax transformers! Something you can’t get in any of those ‘production ready’ languages you use in your day to day life!

Let’s take a look at how the Racket standard library implements this macro (this is what proper Racket formatting looks like, apparently).

(define-syntaxes (and)
  (let-values ([(here) (quote-syntax here)])
    (lambda (x)
    	(if (not (stx-list? x))
    	    (raise-syntax-error #f "bad syntax" x)
          (void))
    	(let-values ([(e) (stx-cdr x)])
    	  (if (stx-null? e)
    	      (quote-syntax #t)
    	      (if (if (stx-pair? e)
          		      (stx-null? (stx-cdr e))
          		      #t)
                (datum->syntax
                 here
                 (list (quote-syntax #%expression)
                       (stx-car e))
                 x)
          		  (datum->syntax
          		   here
          		   (list (quote-syntax if)
                			 (stx-car e)
                			 (cons (quote-syntax and)
                			       (stx-cdr e))
                			 (quote-syntax #f))
          		   x)))))))

Oh jeez. A mere two lines in, and I’m already helplessly confused.

1. (let-values ([(here) (quote-syntax here)])? But how does this make any sense? We’re calling a function (macro?) quote-syntax with input here, and assigning the output to a new variable named here? But what’s the here which we’re feeding into it? It’s not a variable, it’s not a ‘keyword’ (does Racket even have a concept of keywords?), it looks like it’s just some abstract identifier, except it doesn’t actually point at anything!
2. Speaking of undefined stuff, where does #%expression come from and what does it mean? Also, later we see (quote-syntax and). Is that the same and which we’re just defining? Probably? (That has to be used for some sort of recursive syntax-expansion here, right?)
3. (lambda (x) (if ...) (let-values ...), so… x is the parameter name. The if block is what we actually do, the whole let-values block is what we pass to it? Why? The if block evidently checks that something is well-formed, but it doesn’t actually do anything with it! It returns an error, but if it’s well-formed, it just returns void? How does this help us? Why is the lambda even necessary? You can see (let-values ([(e) (stx-cdr x)]) just a few lines later, and to me that looks like we’re (for whatever reason) extracting the ‘syntax-tail’ of x and calling it e?

So we define a variable using as the abstract syntax element pointing at its own identifier, and call a lambda that returns “nothing”, but is presumably chock-full of side-effects, then use that to (potentially) write another instance of the very macro which we’re just in the process of defining.

Macros are fun.

I’m still not entirely sure how any of this works. My theory is that the (quote-syntax and) essentially creates a “piece of syntax” representing the thing-which-you-get-if-you-write-and-in-your-code, and you can then pass it around and put it in the right place somewhere.

If you look at it that way, then you can almost see how we’re doing stuff like “Check if this exists, and then write another if or not here, and put the rest of the expression (stx-cdr e) in the right place.”

But in all honesty, if I delve into this, it will have to happen in another post.

EDIT: A reader kindly pointed out that the above code looks so horribly obscure because it’s very specific library code which is loaded early to bootstrap the rest of the library. In other words, it’s written with the absolutely minimal amount of language features.

Here’s what a ’nicer’ version of this macro would look like. Personally, I find macros a lot less scary with this knowledge.

(define-syntax and
  (syntax-rules ()
    ((and) #t)
    ((and test) test)
    ((and test1 test2 ...) (if test1 (and test2 ...) #f))))

To conclude, here’s a final practical joke. Made by LeetCode, though I’m not quite sure if it was remotely intentional, and whether ’the joke’ is on Racket, or on the website. Here it is:

86. Partition List: “Given the head of a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.”

; Definition for singly-linked list:
#|

; val : integer?
; next : (or/c list-node? #f)
(struct list-node
  (val next) #:mutable #:transparent)

; constructor
(define (make-list-node [val 0])
  (list-node val #f))

|#

(define/contract (partition head x)
  (-> (or/c list-node? #f) exact-integer? (or/c list-node? #f))
  ; ...
)

That’s it. That’s the joke. ⁴

I hope you enjoyed it. And I hope you enjoyed this post. For a first attempt at blogging, it turned out significantly longer than expected.