Corrections, FAQs, and Hints for Assignment 2

CSc 372, Fall 2006

Last Update: September 27, 2006, 11:19pm

FAQs

Q1:      I've got unzip working but I didn't use composition. Is that a problem?

A:        You probably used another function, either an anonymous one or one defined using fun. I see now that my wording is poor but it's my intention that you don't create helper functions, anonymous or not.

Q2:      When experimenting for unzip I tried val f = first o swap but I got that long error about "type vars not generalized". What does that mean, anyway?

A:        The sad fact is that I'm unable to put forth a good explanation for that. Ullman devotes four pages to it (5.3.1) and I would say he is unsuccessful.

However, if you give ML some more context, it can handle that composition. For example, (first o swap)(3,4) works. This is one of those cases where a part doesn't work on the test bench but works fine in a machine.

Q3:      What should mfilter return if the list of integers is nil?

A:        nil.

Q4:      For cpfx, I see that cpfx1 is recursive. Is that ok or should we rewrite it to be non-recursive, too?

A:        cpfx1 is ok as-is. Your task is to arrange for a suitable sequence of calls to cpfx1 without resorting to recursion.

Q5:      What should nnn [] produce? How about nnn [3]?

A:        [] and ["3-3-3"], respectively.

Q6:      For exsufs.sml, could you clarify what you mean by "The order of the output must match the order shown above."?

A:        I struggled with the wording on that. How about this: "The root is first. The other forms follow in the order the suffixes are specified."

Q7:      I can't see what's wrong with the following. I simply want to test whether c is an 'x'!

- c=#"x";

stdIn: Error: unbound variable or constructor: =#

stdIn: Error: operator is not a function [tycon mismatch]

  operator: char

  in expression:

    c <errorvar>

A:        You've found a pitfall that I'm surprised doesn't claim more victims. You can fix it by inserting a space between the = and the #. Read on to understand the cause of the problem.

Recall that ML has symbolic identifiers (slide 17) and that both = and # are valid characters in a symbolic identifier. ML parses the expression as ((c =#) "x")—an invocation of a function c with the argument =#, a "variable". The resulting function will be called with "x". You'll see a similar error with x=~1, for example.

Q8:      For pancakes, do our trailing spaces have to match your trailing spaces? If so, where do you have trailing spaces, if anywhere?

A:        Don't worry about trailing spaces on your pancakes. We'll trim trailing spaces before we diff.

FAQs for repeat.sml

Q1:      Should we include the code on the slide (the definitions for InfList, head and tail)?

A:        Yes, please do. The command sml < repeat.sml should produce no errors.

Q2:      What if the list is empty?

A:        Good question! Assume the list has at least one element.

Q3:      I get a non-exhaustive match warning on head and tail. Is that OK?

A:        You can ignore that warning but if you want to fix it, just add a case for Nil:

fun head Nil = raise Empty

 | head(Cons(x,_)) = x;

Typos

1.       Typo in problem 5, repeat.sml: The second sentence has a spurious occurrence of "code". It should read "Start by copying the InfList code from the preceding slides."

2.       Near the top of page 9, where group.4 is displayed, there is a spurious shell prompt. It should read like this:

% cat group.4

a

b

3.       First sentence on page 6 has a spurious "the": and prints [the] all the forms

DANGER! DANGER!

HINTS BELOW!!

Below are some hints for various problems. You'll probably learn more if you can solve a problem without using any hints but you need to think about the time you have available. It's certainly better to solve a problem by using a hint than to not solve it at all, however.

The hints are in a tiny font to lessen the chance of picking up one you don't want. Copy the text and paste it into something else, minus the formatting information. Or zoom in with your browser to see them all!

doubler

The common problem with doubler is making more of a problem out of it than it really is. Once you understand folding you'll see that doubler is even simpler than a recursive length function.

Be sure you're caught up with the mailing list messages. I've written quite a few messages about folding.

cpfx

Consider the call cpfx(["just", "testing", "this"]). Write out the sequence of recursive calls to cpfx1 that the supplied cpfx will generate. See if that pattern of calls looks familiar to you.

mfilter 

Some students may find that this problem requires the biggest mental leap of any on this assignment. Don't get stuck on it and chew up all your time. Maybe do it last.

                                                             Below is one sequence of steps that may lead you to a solution.

(1) Write a curried predicate inRange that takes a range and an integer. Think about using that with filter:

List.filter (inRange (5,10)) listOfInts

(2) Write a function that takes one range and a list of ints.

(3) Write a function that takes two ranges and a list.

pancakes

A secondary title for this problem might be map, map and map again.

To deal with stacks of varying heights, think about evening out the stacks with some zero-width pancakes. For example, the "order" [[1],[3,3,3]] could be thought of as [[0,0,1],[3,3,3]].

A common problem is extracting the pancake widths at a particular height. A curried form of List.nth with the arguments swapped can help with that:

- L;

val it = [[1,2,3],[10,20,30],[100,200,300]] : int list list

- fun myNth n L = List.nth(L,n);

val myNth = fn : int -> 'a list -> 'a

- map (myNth 0) L;

val it = [1,10,100] : int list

- map (myNth 1) L;

val it = [2,20,200] : int list

- map (myNth 2) L;

val it = [3,30,300] : int list

Then consider a partial application of a function that gets the widths at a particular level:

- fun cakesAtN cakes n = map (myNth n) cakes;

val cakesAtN = fn : 'a list list -> int -> 'a list

- val f = cakesAtN L;

val f = fn : int -> int list

- f 0;

val it = [1,10,100] : int list

- f 1;

val it = [2,20,200] : int list

Of course, you don't need to explicitly define myNth—you could create it with curry and swapArgs.

groups

Use folding to insert the separators. As a warm-up, with your doubler solution in mind, use foldr to create an int list -> int list function that inserts a zero between any two list elements that are identical. The list [1,3,3,7,8,8] would turn into [1,3,0,3,7,8,0,8].

                                                             My solution uses ListPair.zip.