Efficiently updating nested data structures in Racket

Questions & Answers
1

I am trying to write some code that updates immutable nested data structures.

There does not seem to be good support for this in base Racket, and the internet seems to point to using the lens library for this.

The lens library looks like it has not been updated in quite a while and seems to be missing obvious functions.

Is that my only solution for working with deeply nested immutable data structures or is there a different mechanism or library that I could have a look at?

Regards.

1 Like
2

It's not hard to whip up a function or macro that turns (nested-update table key1 key2 key3 new-value) into a series of hash-update calls. Or sets or what have you.

1 Like
3

If it’s truly deeply nested, the lens library sounds appropriate to me.

Can you elaborate what you meant by “missing obvious functions”?

Note that “it has not been updated in quite a while” doesn’t necessarily mean it’s abandoned. It could simply be that the library is matured, so there’s nothing to be done.

For structs, also take a look at struct-copy, which is a bit clunky, but might suffice for your purposes and doesn’t require installing an external library.

1 Like
4

One thing I do often is to update a subset of values in a list based on some predicate. For example I need to be able to express: Update each person's age field where the name starts with "R" and the age < 18.

So I want to write something like this:

(lens-transform (lens-thrush
                  (list-where (lambda (p) (and (starts-with? (person-name p) "R")
                                               (< (person-age p) 18))))
                  person-age-lens)
                (list (person "Rouan" 17))
                (lambda (age) (+ age 10)))

struct-copy is too clunky if you start having 3 or more levels of nesting.

I am used to using the Specter library in Clojure and it is really easy to work with nested data and do the things I am describing above.

5

I am unfamiliar with Specter. Do you have some illustrative examples?

6

You can check out Specter here: GitHub - redplanetlabs/specter: Clojure(Script)'s missing piece.

To write the same example in Clojure using Specter, the code would look like this:

(transform [ALL 
           (fn [p] (and (starts-with? (:name p) "R")
                        (< (:age p) 18)))
           :age]
           [(->Person "Rouan" 17)]
           (fn [age] (+ age 10)))

Which essentially means, visit all the nodes in the vector which match the predicate, and for each node update the :age field by running the supplied update function.

1 Like
7

How are the nodes represented? As hash tables (maps) or structures with named fields?

8

In my example, I have a vector of structs with named fields (or records in Clojure terms). But that is just because of the example I chose. I can have arbitrary complex nested data structures of different types.

9

I was actually curious about the Clojure representation.

In Racket, for structs the field names aren't present at runtime.
Since hash tables store the keys at runtime, it's easier to make a "Spector for Racket" if only vectors and hash tables are used.

An alternative is to look at packages uses at @dstorrs package struct++.

https://docs.racket-lang.org/struct-plus-plus/index.html

3 Likes
10

Thanks, I will take a look at the struct++ package.

In the mean time I was thinking of writing a macro that takes a path description and converts it into the normal struct-copy and other base features so I don't have to write the clunky code by hand :slight_smile:

11

You can get a lot of mileage out of match.

#lang racket

(struct person (name age) #:transparent)
(person "bob" 17)

(match (list (hash 'bob (person "Bob" 18) 'alice (person "Alice" 21)))
  [(list (hash-table ('bob (struct* person ([name name] [age age])))))
   (displayln (~a name " is " age " years old"))])

; Very minimal demo of struct++ , just because                                                  
(require struct-plus-plus)

(struct++ person2 ([name string?]
                   [age  natural-number/c])
          #:transparent)
(person2++ #:name "Alice" #:age 18)

NB: The hash-table match pattern is deprecated; I need to finish updating my Racket to 8.12

12

Always fun to do these; functions and some sugar :ok_hand:.

1 Like
13

Ok, so I spoke to the creator of lens library and @Jack said that what I am trying to do is traversal and not a lens so the functionality is not technically missing.

So I ended up writing my own library for this just as a proof-of-concept and here is an example of what it looks like to use the lib:

#lang racket/base

(require
  sunshine-fw/slib/data
  racket/function)

(struct book
  (title)
  #:transparent)

(update
  ; Specify the path through the nested data structures we want to update.
  (list (ref/list 2) (ref/vec 1) (ref/hash 'book) (ref/struct-m book title))
  ; Define how we want to update the places we identify via the path above.
  (const "Joe is smelling daisies")
  ; This is the nested data structure to update. 
  (list 10 20 (vector 100 (hash 'name "Rouan" 'age 41 'book (book "Smelling daisies.")))))

When I run the example above, I get the output:

(list 10 20 (vector 100 (hash 'age 41 'book (book "Joe is smelling daisies") 'name "Rouan")))

Because this is a proof-of-concept, there is much room for improvement, but I am happy with the interface so far and can use this already in my own code to help with selecting or updating values in nested data structures without needing to manually write the clunky code using Racket's built-in facilities for updating immutable data structures.

2 Likes