Arbitrary-Sized Data

when do we use arbitrary sized data?

when we don’t already know how much data there will be. for ex: number of people in a lecture.

how to make it so that your template is intact?

make sure your final function doesn’t have any more cond questions than the template, or the function doesn’t have any extra stuff going on

how do we represent abitrary-sized data?

with lists, and or compound data

what is the empty value for a list?

an empty value looks like <empty>

how to make lists

(cons "Flames" empty) ;one element list
;; add "flames" to the front of an empty list

(cons "Leafs" (cons "Flames empty)) ;two element list
;; add leafs in front of flames in front of an empty list

;; you can also do expressions in the cons expression
(cons (string-append "C" "anucks") empty)

lists can also take numbers and images and if you really wanted, lists of more than one type of data. (but we dont do that in this course)

the primitives we can operate on lists using

(cons <value> empty) ;to produce the list

(first <list-name>) ;produces the first value in the list

(rest <list-name>) ;produces the remaining values in a list, including empty
;; and also, second, third, but we're not supposed to use them. instead, do ;; a rest, and the first of that rest would give you the second of that 
;; overall

(empty? <list-name>) ;determines if the list has any values excluding empty

what is a self-reference?

whenever a part of the program references itself in the type comment specifically

ex:

(@htdd ListOfString)
;; ListOfString is one of:
;;  - empty
;;  - (cons String ListOfString)
;; interp. a list of strings

the self-reference occurs when we declare a new data type as one of, and then one of the options is itself, but presented in a compound data form

the ;;list of string is one of:

and the (cons String ListOfString)

what is the natural recursion

whenever the template for a function calls itself again

how to write a list data definition?

1. do your (@htdd <TypeName>)

2. usually your TypeName will be “ListOf____”

3. then type comment: ListOf_____ is one of:

   1. one example of the base case, usually ;; - empty

   2. one example with two pieces in it

   3. (cons “string1” (cons “string2” empty))

   4. and you need the self-referential one too

   5. (cons String ListOfString)

4. and then the interp. comment

5. then do your examples:

   1. (define LOS1 empty)

   2. (define LOS2 (cons “string1” (cons “string2” empty)))

6. then do the template:

7. (@template-origin ListOf____)

8. then write the actual template:

(@dd-template-rules one-of             ;2 cases
                    atomic-distinct    ;empty
                    compound           ;(cons Number ListOfString)
                    self-ref)          ;(rest los) is ListOfString

(@template
	(define fn-for-los los)
	(cond [(empty? los) (...)]
	      [else
		(...) (first los)
		      (fn-for-los (rest los)]))) 

;one cond question for each one in the temp rules
	

9. one cond question for each one of you had in the type comment

10. the predicate for empty is (empty? los) and empty is an atomic distinct, so it gets (…) for the answer

designing functions for lists

1. (@htdf fnname)

2. (@signature ListOf___ → datatype)

3. ;; purpose

4. stub

5. then do the check-expects, one for each sort of case you can think of, like the empty case, and then any other to address the one ofs in the type comment

6. then steal the template, and edit it to include the name of the function but also in the recursion too!!!!!!!!!!!!!!!!!!!!!!!!!!!!

7. 
   

recursion def from the course site

When a function calls itself we say that the function is recursive. When a type comment refers to itself we say that the type involves self-reference. Both are forms of recursion.

what constitutes a well-formed self-referential data definition?

it means that in your tpe comment, the must be a one of for the base case, which is the “;; - empty”, and then the one that includes the self-referential case as a piece of compound data, i.e. “";; - (cons ____ ListOf____)””