Background

Racket and Typed/Racket provide a set datatype with a fairly convenient syntax.

#lang typed/racket
(define S (list->set '(1 2 3)))
(define S* (set 1 2 3))
(equal? S S*)
(set-member? S 1)
(define T (set-add S 4))
(set-union S T)

Unfortunately these forms are not provided in plait. Since sets are a useful data structure, in particular for thinking about garbage collection, we're going to impliment something similar to the typed/racket set API using plait hash tables.

Types.

In general I have over-annotated the code in this tutorial, to help you think about polymorphic typechecking (which we discussed in ), and to make it clearer what the functions should do. The original code works fine without any annotations.

Questions

Making sets

Complete the definition of list->set. The type annotation and second test should give you the idea of how to impliment it using e.g. map. If you examine the type of list->set, you will see that our type-alias is not opaque; the underlying implimentation as a hash table is visible.

#lang plait

(define-type-alias (Setof 'a) (Hashof 'a Boolean))
(define (list->set [ items : (Listof 'a) ]) : (Setof 'a)
  ....)

(module+ test
  (test (list->set empty)  (hash empty))
  (define S123 (list->set '(1 2 3)))
  (test  S123 (hash (list (pair 1 #t) (pair 2 #t) (pair 3 #t)))))

Providing some prettier syntax

One of my main motivations in reimplimenting these primitives was not having to change all of the places my code writes (set ....) to some clunkier syntax (like the list->set we just wrote. Write an appropriate syntax rule, using ... to collect arguments to provide a set macro. This is a very common development pattern in languages with macros: debug the code first as a function, then make a minimal macro wrapper for that function that makes it nicer to use.

(define-syntax-rule (set ....)
  ....)

(module+ test
  (test (set) (list->set empty))
  (test (set 1 2 3) S123))

Define set-member?

One of the defining characteristics of set data structures (compared to e.g. lists or arrays) is fast membership testing. Define a set-member? function. You will most likely want to use hash-ref, but note the return type in plait uses Optionof.

(define (set-member? [set : (Setof 'a)]  [thing : 'a]) : Boolean
  ....)

(module+ test
  (test (set-member? S123 1) #t)
  (test (set-member? S123 10) #f))

Define set-add

Our sets are immutable (hence hash rather than make-hash above), but we still want to be able to extend them by a single element. We want set-add to be like cons. The input is not modified but a new set with one more element is returned.

(define (set-add [set : (Setof 'a)] [thing : 'a]) : (Setof 'a)
  ....)

(module+ test
  (test (set-add (set 1 2 3) 0) (set 0 1 2 3)))

Set union

Finally, define a way to take the union of two sets. This can either use set-add, or (probably easier), underlying hash-table operations. Note in particular the function hash-keys.

(define (set-union [the-set : (Setof 'a)] [other-set : (Setof 'a)])
    ....)

(module+ test
  (test (set-union (set 0 1 2 3) (set -1 2 7)) (set -1 0 1 2 3 7)))