Haskell Data Types in Scheme

Arthur Smyles

March 12, 2013


Programming languages should be designed not by piling feature on top of feature, but by removing the weaknesses and restrictions that make additional features appear necessary.

Why Haskell data

What we want to avoid


data Maybe a = Just a | Nothing

Just a | Nothing

Data types

Data types have four parts:

Definition (srfi-99)

Back to the Future

 (define $data-type 
   (make-rtd 'data-type 
    '#((immutable type); procedure
       (immutable constructor) ; procedure
       (immutable predicate) ; procedure
       (immutable destructor)) ; procedure
    #f 'sealed 'opaque))

Constructing data type

De-structuring data-types

Everything is built on this:

 (define (call-with-data-type data-type proc)
    (call-with-values (lambda () (data-type-destructor data-type)) proc))


(define-syntax new
  (syntax-rules ()
    ((_ type values ...)
    (call-with-data-type type (lambda ($ @ ? *) (@ values ...))))))

(define (instance-of? type obj)
      (call-with-data-type type (lambda ($ @ ? *) (? obj))))

Example (destructure data)

(define (data-ref obj type fields)
   ((list? fields)
    (call-with-data-type type 
     (lambda ($ @ ? *)
      (if (? obj) 
       (call-with-values (lambda () (apply * obj fields)) (lambda result result))
       (assertion-violation 'data-ref "Invalid type!" type obj)))))))

Re-imagining λ

de-structuring values

(type-lambda x
   (Just (a) a)
   (Nothing () 'nothing)
   (else 'not supported))

destructure values (expansion)

remember data-ref?

(lambda (x)
  (call-with-data-type Just 
     (lambda ($ @ ? *)
      (if (? x)
       (call-with-values (lambda () (apply * x 'a)) (lambda (a) a))
       (call-with-data-type Nothing 
    (lambda ($ @ ? *)
     (if (? x)
       (lambda (apply * x '())) 
       (lambda () 'nothing)))
      'not supported)))))))

type-lambda features

examples are type-lambda clauses

type-lambda features (cont)

But sometimes I really want to have a mutable type

Sum Types

(define maybe? (type-lambda (Just (a) \#t) (Nothing () \#t) (else #f)))
(when (maybe? x) 
   (type-case x (Just (a) a) (Nothing () 'nothing) (else \#f)))

Sum Types (as macro)

(define-type Maybe (Just a) (Nothing))

expands to:

(define-data-type Just a)
(define-data-type Nothing)
(define-syntax Maybe
 (syntax-rules (Just Nothing)
  ((Maybe x (Just clauses (... ...)) (Nothing clauses (... ...)))
   (type-case x
    (Just clauses ...)
    (Nothing clauses ...)
    (else \#f)))))

Recursive Types

(define-data-type Nil)
(define-data-type Node x l r)
(define tree? (type-lambda (Nil () \#t) (Node (x l r) (and (tree? l) (tree? r)))))

Type Classes

Type Classes

What's a data type again?

 (define $data-type 
   (make-rtd 'data-type 
    '#((immutable type); procedure
       (immutable constructor) ; procedure
       (immutable predicate) ; procedure
       (immutable destructor)) ; procedure
    #f 'sealed 'opaque))

What is a Type Class?


(define (make-type-class name type-parms fields)
(let ((library '())
      ($funcs (make-rtd name (list->vector (map (lambda (f) `(immutable ,f)) fields)))))
  (let ((funcs@ (rtd-constructor $funcs))
    (funcs* (rtd-destructor $funcs))) 
   (define ($ proc) (proc 'type-class type-parms fields library))
   (define (@ . rest) 
    (let ((parms-fields (fold-left 
            (lambda (a e) 
              ((< (length (car a)) (length type-parms)) 
               (cons (cons e (car a)) (cdr a))) 
              (else (cons (car a) (cons e (cdr a)))))) (list '()))))
        (cons (cons (reverse (car parms-fields)) (apply funcs@ (reverse (cdr parms-fields)))) library)

make-type-class cont

   (define (? . instances)
    (assp (lambda (parms) (for-each (lambda rest (apply instance-of? rest)) (map list parms instances))) library))
   (define (* objs . fs) (apply funcs* (cdr (apply ? objs)) fs))
   (make-data $ @ ? *))))


Play @ home

The Prestige

Thank you