CODEWITHSUNDEEP
data-structuresfunctional-programmingschemelispchicken-scheme
functorial
functorial

Reputation: 338

Data Structures in Scheme

I am learning Scheme, coming from a background of Haskell, and I've run into a pretty surprising issue - scheme doesn't seem to have custom data types??? (ie. objects, structs, etc.). I know some implementations have their own custom macros implementing structs, but R6RS itself doesn't seem to provide any such feature.

Given this, I have two questions:

  1. Is this correct? Am I missing a feature that allows creation of custom data types?
  2. If not, how do scheme programmers structure a program?

For example, any function trying to return multiple items of data needs some way of encapsulating the data. Is the best practice to use a hash map?

(define (read-user-input)
    (display "1. Add todo\n2. Delete todo\n3. Modify todo\n")
    (let ((cmd-num (read)))
    (if (equal? cmd-num "1") '(("command-number" . cmd-num) ("todo-text" . (read-todo)))
    (if (equal? cmd-num "2") '(("command-number" . cmd-num) ("todo-id"   . (read-todo-id)))
                             '(("command-number" . cmd-num) ("todo-id"   . (read-todo-id)))))))

Upvotes: 4

Views: 4299

Answers (2)

John Clements
John Clements

Reputation: 17203

In order to answer your question, I think it might help to give you a slightly bigger-picture comment.

Scheme has often been described as not so much a single language as a family of languages. This is particularly true of R5RS, which is still what many people mean when they say "Scheme."

Nearly every one of the languages in the Scheme family has structures. I'm personally most familiar with Racket, where you can define structures with struct or define-struct.

"But", you might say, "I want to write my program so that it runs in all versions of Scheme." Several very smart people have succeeded in doing this: Dorai Sitaram and Oleg Kiselyov both come to mind. However, my observation about their work is that generally, maintaining compatibility with many versions of scheme without sacrificing performance usually requires a high level of macro expertise and a good deal of Serious Thinking.

It's true that several of the SRFIs describe structure facilities. My own personal advice to you is to pick a Scheme implementation and allow yourself to feel good about using whatever structure facilities it provides. In some ways, this is not unlike Haskell; there are features that are specific to ghc, and generally, I claim that most Haskell programmers are happy to use these features without worrying that they don't work in all versions of Haskell.

Upvotes: 7

Sylwester
Sylwester

Reputation: 48745

  1. Absolutely not. Scheme has several SRFIs for custom types, aka. record types, and with R7RS Red edition it will be SRFI-136, but since you mention R6RS it has records defined in the standard too.

Example using R6RS:

#!r6rs
(import (rnrs))

(define-record-type (point make-point point?)
  (fields (immutable x point-x)
          (immutable y point-y)))

(define test (make-point 3 7))
(point-x test) ; ==> 3
(point-y test) ; ==> 7
  1. Early Scheme (and lisp) didn't have record types and you usually made constructors and accessors:

Example:

(define (make-point x y)
  ...)

(define (point-x p)
  ...)

(define (point-y p)
  ...)

This is the same contract the record types actually create. How it is implemented is really not important. Here are some ideas:

(define make-point cons)
(define point-x car)
(define point-y cdr)

This works most of the time, but is not really very safe. Perhaps this is better:

(define tag (list 'point))
(define idx-tag 0)
(define idx-x 1)
(define idx-y 2)

(define (point? p)
  (and (vector? p)
       (positive? (vector-length p))
       (eq? tag (vector-ref p idx-tag))))

(define (make-point x y)
  (vector tag x y))

;; just an abstraction. Might not be exported
(define (point-acc p idx)
  (if (point? p)
      (vector-ref p idx)
      (raise "not a point")))

(define (point-x p)
  (point-acc p idx-x))

(define (point-y p)
  (point-acc p idx-y))

Now if you look the the reference implementation for record types you'll find they use vectors so the vector version and R6RSs isn't that different.

  1. Lookup? You can use a vector, list or a case:

Example: 

;; list is good for a few elements
(define ops `((+ . ,+) (- . ,-)))
(let ((found (assq '+ ops)))
  (if found 
      ((cdr found) 1 2)
      (raise "not found")))
; ==> 3 

;; case (switch)
((case '+
  ((+) +)
  ((-) -)
  (else (raise "not found"))) 1 2) ; ==> 3

Of course you have hash tables in SRFI-125 so for a large number of elements its probably vice. Know that it probably uses vector to store the elements :-)

Upvotes: 3

Related Questions