Need help with Scheme assignment

[hans030390]

My professor has spent half of a lecture going over this material, so I'm really not exactly sure how to do any of this. She didn't explain anything clearly over it AND expects us to turn this assignment in earlier than normal due to Thanksgiving break. That, and she's not lecturing over it again before we turn it in (like she normally does).

Normally, I'd go to office hours to get help, but that's a big issue with break coming up...the time I normally go happens to be the Wednesday we don't have school.

So, I could really use some help with these...trying to understand everything, how I should go about solving them, etc. I really have no clue what's going on...except I kind of understand I/O stuff. Here are the problems...any specific help or tips you can get will be greatly appreciated. Sorry if the formatting is bad or if there are specific problems requiring something related to a previous assignment:

1. Consider the following tail-recursive definition of a procedure append-many that takes a list of lists and returns the result of appending them altogether into a single list. We use the built-in append as a helper to join two lists together.

> (define append-many
(lambda (lol)
(cond
[(null? lol) '()]
[(null? (cdr lol)) (car lol)]
[else
(append-many (cons (append (car lol) (cadr lol)) (cddr lol)))])))

> (append-many '((a b c) (d e) () (f g h i)))
(a b c d e f g h i)

In comments, answer the following question: Is this an efficient implementation? If so, provide a compelling argument to support your position. If not, give an alternate implementation that is more efficient and prove your claim with specific timing tests. (You may use the built-in append only to join two lists.)

2. We can transform any and expression into an equivalent if expression using the following recursive rewrite rules:

(and) --> #t

(and e) --> e

(and e1 e2 ...) --> (if e1 (and e2 ...) #f)

Define a procedure and->if that takes a properly formed and expression and returns the logically equivalent if expression generated by applying the above rules. Do not worry about and expressions embedded inside the terms of the given expression.

> (and->if '(and))
#t
> (and->if '(and 5))
5
> (and->if '(and (zero? n) (even? n)))
(if (zero? n) (even? n) #f)
> (and->if '(and (zero? n) (even? n) n))
(if (zero? n) (if (even? n) n #f) #f)
> (and->if '(and e1 e2 e3 e4 e5))
(if e1 (if e2 (if e3 (if e4 e5 #f) #f) #f) #f)
> (and->if '(and (and a b) (and c d)))
(if (and a b) (and c d) #f)

3. Define a procedure write-file that takes a string s and a filename ofn, and uses write-char to write the contents of s to a file named ofn. Replace the file if it already exists. (The type procedure used in the examples below was defined in 1119 lecture. Output sent to the interactions window appears in a tan color.)

> (write-file "I speak for the trees!\n" "seuss.txt")
> (type "seuss.txt")
I speak for the trees!
> (write-file
(string-append
"If you never did, you should\n"
"These things are fun, and fun is good.\n")
"seuss.txt")
> (type "seuss.txt")
If you never did, you should
These things are fun, and fun is good.

4. Define a procedure list->html that takes a list ls and a filename, and writes an html ordered list version of ls to the specified file, with the exact whitespace as shown in the examples below. Use display to write each list element. Replace the file if it already exists.

Example followed by Rendered html
> (list->html '(red green yellow pink white) "colors.html")
> (type "colors.html")
<ol>
<li> red
<li> green
<li> yellow
<li> pink
<li> white
</ol>

red
green
yellow
pink
white

> (list->html '(#\A #\E #\I #\O #\U) "vowels.html")
> (type "vowels.html")
<ol>
<li> A
<li> E
<li> I
<li> O
<li> U
</ol>

A
E
I
O
U

> (list->html '("Star Trek" "Doctor Who" "The Twilight Zone") "scifi.html")
> (type "scifi.html")
<ol>
<li> Star Trek
<li> Doctor Who
<li> The Twilight Zone
</ol>

Star Trek
Doctor Who
The Twilight Zone

> (list->html '() "empty.html")
> (type "empty.html")
<ol>
</ol>

5. Define a procedure file-size that takes a filename and returns a count of the number of characters in the file

> (type "seuss.txt")
If you never did, you should
These things are fun, and fun is good.
> (file-size "seuss.txt")
68

6. Define a procedure compare-files that takes the names of two files and compares them character by character. Return #t if the files are identical, and #f otherwise. Stop reading the files as soon as you come across a mismatch. Use read-char to read the files char by char, and use char=? to compare two characters.

> (write-file "Thing one" "t1.txt")
> (write-file "Thing two" "t2.txt")
> (compare-files "t1.txt" "t2.txt")
#f
> (write-file (read-file "t1.txt") "t2.txt")
> (compare-files "t1.txt" "t2.txt")
#t
> (write-file (string-append (read-file "t1.txt") "other stuff") "t2.txt")
> (compare-files "t1.txt" "t2.txt")
#f

7. Recall the procedure you defined in a7 to count the number of shortest paths from a given square on a board to the upper left corner. Each step in the path moves either up or to the left. Define a procedure all-shortest-paths that takes two positive integers representing the row and column number, respectively, of a particular square on the board and returns a list of shortest paths. Each path is a list that consists of the coordinates along the path, and each coordinate is a two-element list. The order of the coordinates in a given path is important, but the order of the paths in the big list is immaterial. All paths should be distinct. Hint: use map.

> (all-shortest-paths 1 1)
(((1 1)))
> (all-shortest-paths 1 2)
(((1 2) (1 1)))
> (all-shortest-paths 2 1)
(((2 1) (1 1)))
> (all-shortest-paths 2 2)
(((2 2) (2 1) (1 1)) ((2 2) (1 2) (1 1)))
> (all-shortest-paths 2 3)
(((2 3) (2 2) (2 1) (1 1))
((2 3) (2 2) (1 2) (1 1))
((2 3) (1 3) (1 2) (1 1)))
> (all-shortest-paths 3 2)
(((3 2) (3 1) (2 1) (1 1))
((3 2) (2 2) (2 1) (1 1))
((3 2) (2 2) (1 2) (1 1)))
> (all-shortest-paths 3 3)
(((3 3) (3 2) (3 1) (2 1) (1 1)) ((3 3) (3 2) (2 2) (2 1) (1 1))
((3 3) (3 2) (2 2) (1 2) (1 1)) ((3 3) (2 3) (2 2) (2 1) (1 1))
((3 3) (2 3) (2 2) (1 2) (1 1)) ((3 3) (2 3) (1 3) (1 2) (1 1)))
> (all-shortest-paths 3 4)
(((3 4) (3 3) (3 2) (3 1) (2 1) (1 1)) ((3 4) (3 3) (3 2) (2 2) (2 1) (1 1))
((3 4) (3 3) (3 2) (2 2) (1 2) (1 1)) ((3 4) (3 3) (2 3) (2 2) (2 1) (1 1))
((3 4) (3 3) (2 3) (2 2) (1 2) (1 1)) ((3 4) (3 3) (2 3) (1 3) (1 2) (1 1))
((3 4) (2 4) (2 3) (2 2) (2 1) (1 1)) ((3 4) (2 4) (2 3) (2 2) (1 2) (1 1))
((3 4) (2 4) (2 3) (1 3) (1 2) (1 1))
((3 4) (2 4) (1 4) (1 3) (1 2) (1 1)))
> (length (all-shortest-paths 3 8))
36
> (length (all-shortest-paths 7 6))
462

 

[Fallen Kell]

Have I mentioned that I hate LISP before?

Well, the first one is simply asking you if the program given is efficient, and if not, explain why not. Basically, it is asking if it is efficient to do a recursive append to build one list from a list of lists, or is it more efficient to do it some other way, but that you are only allowed to use the built in append on 2 lists at once. Well, that is simple to answer, of course it is not efficient. You are forced to wait for each append to happen in serial, when you could be doing multiple at once in parallel (you can append the first two lists together without needing to know the answer to the appending of the next two lists, etc, which means there is a better way to do it. You need to just code up something to do it in parallel and prove do some "O notation" analysis of the algorithm).

2) is just asking to write a function which produces the output described in the question, and gives examples of how your function should work if you did it properly.

3) you need to write a function which opens a file and writes a string into the file. You are not to open append, since you should overwrite the file if it already exists... Pretty straight forward...

4) Just wants you to again, write a function which opens a file/creates the file (just like 3), and create a HTML formated LIST from the list given as an argument to your function. Very close to what you did in 3, except you need to write another function which simply parses over the list and writes the proper HTML language to the file, not just the string in the list...

5) Too bad you are probably not expected to use system call's especially if you are running on linux/unix... this one is just open a file to read, as opposed to open for write and increment a counter for each byte (read-char) in the file, should be pretty easy loop over the file's data.

6) Again, pretty simple, get the string name of each file into a list, loop over the names one character at a time and compare them. If they are the same, continue looping, if they are different, exit with #f, if you get to the end of each name and both end, exit with #t, if one continues (i.e. is longer than the other), exit with #f.....

7) Well, you are on your own on that one. We would need to know what a7 was to get an idea what is is really asking. I am assuming it is something like a chessboard where each square has a coordinate. If that is the case, they are simply asking you to do a search for the smallest path between your starting location which is passed into the function and the finish location (not sure what that is, but from the looks of the output, (1 1) appears to be the finish).

 

[hans030390]

Thanks for those tips. The only reason I don't know what I'm doing is because the professor never explained what any of the things are needed to write the code. I'll see what I can do, though.

 

[hans030390]

For write-file, I've gotten it to the point where it will create a new file with the string in it, but it ignores the "#\newline" character and just sticks the following character to the previous. I've tried to create a separate base case where it will recognize if that is the newline character and create a newline, (newline op), but it still does the same thing.

 

[IHateMyJob2004]

Scheme is a nice language. But since you are in school:
http://www.google.com/search?h...e+tutorial&btnG=Search

You need to learn this stuff on your own or I'll end up having to work with you some day.