I implemented a simple tree structure — a node has a set of child-nodes type of thing — and an insert function that traverses breadth first to find the parent node under which to add a child node:

It seems to do what I wanted it to do. However, could I have achieved the same thing in a non-mutable way?

@stefan.kruger https://www.amazon.com/Purely-Functional-Data-Structures-Okasaki/dp/0521663504 may be of interest

Short answer is, “yes”, you can insert into a tree in a functional way w/o mutation.

Related question — is it considered dirty to reach for mutability in Racket? I just worry my Racket looks like Python :slightly_smiling_face:

I’m sure opinions will vary widely, but I do try to go for a functional approach first as a matter of habit. When I use mutation, which is rarely, I try and localize it as much as possible. It’s nice that Racket allows mutation when needed though :slightly_smiling_face:

As an example of “localize”, I will occasionally use set! inside a single function where I’m only mutating a variable local to that function.

@stefan.kruger FWIW here is the code for a functional red black tree done in Racket: http://planet.racket-lang.org/package-source/soegaard/galore.plt/4/2/private/red-black-tree.ss

The B struct is a tree with a black top node and the R struct is a tree with a red top node.

The old match used $ to match structs, so ($ B l x r) matches a tree where the node element x is black and the l and r is the left and right sub trees respectively.

The book by Okasaki is top-notch. The basis of the book was his thesis: https://www.cs.cmu.edu/~rwh/theses/okasaki.pdf

Sounds like $40 of worthwhile spend.

I admit I got obsessed with implementing data structures after reading it.

Bought.