<html><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "> <div> </div><div> </div><div><div>On Nov 6, 2008, at 10:53 PM, David Yrueta wrote:</div> <blockquote type="cite"></blockquote> </div><div>Think of cons as a function with contract </div><div> </div><div> X [Listof X] -> [Listof X]</div><div> </div><div>The key is to start this "pattern matching exercises" by using variables for the various components of the contract: </div><div> </div><div>1. natural-f takes four arguments and returns the third one. Also the fourth one is guaranteed to be a Nat and the first is a function of two args: </div><div> </div><div> (X Y -> Z) W U Nat -> U</div><div> </div><div>2. The result of f is also a possible result of the function, so let's say Z = U</div><div> </div><div> (X Y -> U) W U Nat -> U </div><div> </div><div>3. The second input to f is the result of natural-f, so Y = U </div><div> </div><div> (X U -> U) W U Nat -> U </div><div> </div><div>4. The second argument is used as the first input to f so U = W </div><div> </div><div> (X U -> U) U U Nat -> U </div><div> </div><div>5. No other constraints so we're fine </div><div> </div><div>And I may have made a mistake so check the calculation -- Matthias</div><div> </div><div> </div><div> </div><div> </div><div> </div><div> </div><div> <blockquote type="cite">If function "natural-f" --<div> </div><div><div>;apply function f to x n times with a base case of TH where n=0</div> <div>;(check-expect (natural-f cons 'x empty 5) (list 'x 'x 'x 'x 'x))</div> <div>;(check-expect (natural-f + 1 5 9) 14)</div><div>(define (natural-f f x TH n)</div> <div> (cond</div><div> [(zero? n) TH]</div> <div> [else (f x</div><div> (natural-f f x TH (sub1 n) ))]))</div> <div> </div><div>-- properly abstracts over the the functions </div> <div> <table><tbody><tr><td><div align="left"><pre style="margin-left:2em;color:rgb(165, 42, 42)">;; <code style="color:rgb(165, 42, 42)">copy : N X <tt>-></tt> (listof X)</code> ;; to create a list that contains ;; <code style="color:rgb(165, 42, 42)">obj</code> <code style="color:rgb(165, 42, 42)">n</code> times (define (copy n obj) (cond [(zero? n) empty] [else (cons obj (copy (sub1 n) obj))])) </pre></div></td><td> </td> <td><div align="left"><pre style="margin-left:2em;color:rgb(165, 42, 42)">;; <code style="color:rgb(165, 42, 42)">n-adder : N number <tt>-></tt> number</code> ;; to add <code style="color:rgb(165, 42, 42)">n</code> to <code style="color:rgb(165, 42, 42)">x</code> using ;; <code style="color:rgb(165, 42, 42)">(+ 1 ...)</code> only (define (n-adder n x) (cond [(zero? n) x] [else (+ 1 (n-adder (sub1 n) x))]))</pre> </div></td></tr></tbody></table></div><div>--then what is the general contract for "natural-f"?</div> <div> </div><div>Considering "natural-f" as an abstraction of function "n-adder" above, the resulting contract would be:</div> <div>(number number -> number) number number number -> number </div><div>(ex. (check-expect (natural-f + 1 5 9) 14)</div><div><div> </div><div>But what would the contract for "natural-f" be if it was viewed as an abstraction of function "copy?"</div> <div>(ex.(check-expect (natural-f cons 'x empty 5) (list 'x 'x 'x 'x 'x))</div> <div> </div><div>In that case, argument "f" would take the value of "cons," so the question (for me) comes down to how to represent the primitive "cons" as a function type within a contract. </div> <div> </div><div>Is "cons" represented as (X Y -> Y)</div> <div>where X is any Scheme ITEM, Y is the Scheme-value list, and the result is basic type Y (Scheme-value list)?</div> <div> </div><div>Or is "cons" represented as (X list -> (listof X)</div> <div> where X is any Scheme ITEM, "list" is Scheme-value list, and the result is defined type (listof X)?</div> <div> </div><div>The difference between the two contracts appears to be in the output types. The first output type is basic, which is consistent with the contract output for "n-adder"; the second output type is defined, which conflicts with "n-adder." Avoiding conflict means choosing the first representation of "cons" in place of f in "natural-f"'s contract. S my guess is that the proper general contract for "natural-f" would be:</div> <div> </div><div>;natural-f: (X Y -> Y) X Y number -> Y </div><div> </div><div>Is this right? If not, where am I going wrong?</div> <div> </div><div>Thanks,</div> <div>Dave </div><div> </div><div> </div><div> </div><div> </div><div> </div><div> </div></div><div> </div><div> </div><div> </div><div> <div align="left"><pre style="margin-left:2em;color:rgb(165, 42, 42)"></pre></div></div></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">_________________________________________________</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; "> For list-related administrative tasks:</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; "> <a href="http://list.cs.brown.edu/mailman/listinfo/plt-scheme">http://list.cs.brown.edu/mailman/listinfo/plt-scheme</a></div> </blockquote></div> </body></html>