Dada
|> Structures
|> Algorithms

A set data structure in Racket

Creating a set in a lisp

This is a little experiment with racket. I wanted to see how I could implement a set data structure. A set is a collection that can only have one copy of each member. This is the quick code that I came up with

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

(define (includes? x xs)
  (cond
    ((eq? #f (member x xs)) #f)
    (else #t)))

(define (set-insert item set)
  (if (not (includes? item set))
    (cons item set)
    set))

(define (set-delete item set)
  (remove item set))

(define (set-includes? item set)
  (includes? item set))

It struck me was how easy it was to do it. The core of a set data structure is so brief and readable.

This is a functional implementation because it is trickier to create a mutating structure in racket. I am sure that there is a way to do it; I don't know how to do it right now. So it took me a bit longer than I had thought.

At the same time, I was able to experience troubleshooting in racket. It is so easy. It is so easy to interactively test the different calls that one is making.

Sometimes we don't have the functions that we expect, as in the case of include? which python and ruby offer. What I have found is that even when we run into those issues, it is not terribly hard to write your own.

Lisp is this amazing language that can provide such quick software development. What I find amazing is how business are not taking advantage of it.

This is another of those great U.S. innovations that are sitting there for someone to come along and exploit it. I suspect it will end up being some country other than the U.S. History does have a tendency to surprise us. We will see.