Homework 7 Solution

By using only constructors in pattern matching we could write four-line functions for the binary logical connectives which simply mimicked their truth tables. By allowing variables in patterns the declarations could all be shorter. Write these shorter versions of conj, disj, impl and equiv.

Would it be straightforward to rewrite the reduce function using local rather than let? What would be the difficulty?

It would be messier since local creates bindings but doesn't return a value.

The semifactorial of a positive integer n is 1 × 3 × 5 × ... × n if n is odd and 2 × 4 × 6 × ... × n if n is even. Use the reduce function to define a semifac function which calculates semifactorials.

This function works by transforming the numbers from 1 to n/2 into either 2*x if the original input was even or 2*x+1 if the original input was odd. All of the transformed numbers are multiplied together, yielding a semifactorial.

Which, if either, of the following are well defined?
  1. compose (compose, uncurry compose)
  2. compose (uncurry compose, compose)

In the context of a statically typed functional language "well defined" means roughly "will survive parsing and type checking." The second expression is definitely not well defined. If you look at the types of 'uncurry compose' and 'compose' you'll see that they can't be plugged together. The first expression is more complex: it's technically well defined but causes the type checker to emit an error. This happens for reasons way beyond the scope of our class. If you're curious, you can read about ML's value restriction.

Use the predefined Standard ML version of function composition to define a function, iter', which behaves identically to the function iter given earlier.

Instead of directly applying x to the one argument function "iter (n-1) f", you first compose this function with f and then apply x.

How would you define exp1 andalso exp2 and exp1 orelse exp2 in terms of exp1, exp2, conditional expressions and the constants true and false? Try out your definitions against the expressions with the derived forms when exp1 is true and exp2 is 10 div 0 = 0. Then change exp1 to false and compare again.

I think this question is confusingly worded. You can't define short-circuiting logical operators from within SML. Eager evaluation won't let you! What you can do is define logical operators which fully evaluate both their arguments before computing a result. These are just conjunction and disjunction functions from the first question.