UNB/ CS/ David Bremner/ teaching/ cs3613/ tutorials/ CS3613 Tutorial 7

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. I already had a solution for Homework 10 written in typed/racket and using the set operations. Rather than importing them (as we did with number? and procedure?), I decided to write them in plait, based on Hash Tables, which are provided in plait.

Types.

In general I have over-annotated the code in this tutorial, to help you think about polymorphic typechecking (to come in a later lecture), 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)))