Try Firefox!

SI413 Scheme Lab 3: Representing data with lists!


Scheme standard's list information
Points
To compute with points in C++ or Java we would usually define a nice point class. In Scheme, however, any object more complicated than one of the builtin types is represented as a list (or as a fuunction, but we'll get to that later). So, we represent points as a list, so the point (4.1,0.5) is represented as the list (4.1 0.5).
  1. Write a function magnituder that takes a point and returns its distance from the origin. Example:
    > (magnituder '(4.5 3.1))
    5.4644304369257
    > (magnituder '(-0.5 -0.5))
    0.7071067811865476
  2. Write a function distance that takes two points and returns the distance between them. Example:
    > (distance '(0 1) '(1 0))
    1.4142135623730951
    > (distance '(3.4 -0.25) '(3.15 3.75))
    4.00780488547035
  3. Optional: come back later and ... Rewrite the above functions so that they work for points in 2-dimensional space, 3-dimensional space, and even higher dimensional spaces!
    > (distance '(-1 1 0) '(1 0 1))
    2.449489742783178
    > (distance '(-1 0 2.5 3) '(0 0.5 -1 0))
    4.743416490252569
    

Interlude
Sometimes we want a function to return more than one piece of information. In C++ we often used reference parameters to do this. However, reference parameters are the antithesis of functional programming (can you tell me why?), so we don't do anything like that in Scheme. Instead, we simply return a list containing the several objects we want to return.

Consider the definition of rem-smallest given below:

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;; (rem-smallest L) returns a list (s Lp) where s is the smallest 
;;; element in L, and Lp is a list containing all the other elements in L.
;;; NOTE: L must be a nonempty list of numbers!
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(define (rem-smallest L) 
  (if (equal? (cdr L) '())
      (list (car L) '())
      (let ((R (rem-smallest (cdr L))))
	(if (> (car L) (car R))
	    (list (car R) (cons (car L) (car (cdr R))))
	    (list (car L) (cdr L))))))
Given a nonempty list of numbers L, this function returns a list (s Lp) where s is the smallest element in L, and Lp is a list containing all the other elements in L. For example:
> (rem-smallest '(4 7 2 3 6))
(2 (4 7 3 6))
> 
Using rem-smallest, write a function my-sort that sorts a list of numbers into ascending order. For example:
> (my-sort '(3 8 7 2 9 1 6 5 4))
(1 2 3 4 5 6 7 8 9)
>
Triangles
There are two obvious ways to represent triangles, a coordinate-free representation, in which the triangle is represented by the lengths of its three sides, and the coordinate representation, in which the triangle is represented by its three vertices.
  1. Write a function tric-to-tricf that converts a triangle from its coordinate to its coordinate-free representation. Example:
    > (tric-to-tricf '((0 0) (1 1) (1 0)))
    (1.4142135623730951 1 1)
    > (tric-to-tricf '((3.5 4.5) (3.5 4) (3 4)))
    (0.5 0.5 0.7071067811865476)
  2. Write a function similar-cf? that takes two triangles in their coordinate-free representation and returns true if the triangles are similar and false otherwise. Recall: two triangles are similar if their sides can be matched up so that for some constant the constant times each side of the first yields the length of the corresponding side of the second.
    Hint: other function(s) you have written for this lab may be useful!
    Example:
    > (similar-cf? '(1 1 0.8) '(0.4 0.5 0.5))
    #t
    > (similar-cf? '(1 1 1) '(2 2.2 2))
    #f
    	    
  3. Write a function similar-c? that takes two triangles in their coordinate representation and returns true if the triangles are similar and false otherwise. Example:
    > (similar-c? '((0 0) (1 1) (1 0)) '((2 2) (1.5 2) (1.5 1.5)))
    #t
    > (similar-c? '((3 4) (-1 5) (-1 -1)) '((0 10) (1 5) (-1 -10)))
    #f
    


Christopher W Brown
Last modified: Mon Aug 31 13:56:35 EDT 2009