[IFP] Exercises 1.2

1.2.1 Count the number of different ways that square(square(3+7)) can be reduced to normal form Started this one without using my brain. I wrote out two solutions after coming to a (correct?) solution. I've misplaced my solutions, but they were something like the following....

square(square(3+7))
=> square(square(10)) (+)
=> square(10*10)      (square)
=> square(100)        (*)
=> 100*100            (square)
=> 10000              (*)

square(square(3+7))
=> square(3+7)*square(3+7) (square)
=> square(10)*square(10)   (+)
=> (10*10)*(10*10)         (square)
=> (100)*(100)             (*)
=> 10000                   (*)

It would seem the same five operations need to be performed each time to get to the solution, and that these five operations can be done in any order. There are 5! (120) ways to reduce square(square(3+7)) to normal form.

1.2.2 In how many ways can three (3+4) be reduced to normal form if three x = 3
This one isn't quite the same as 1.2.1 as the definition three x = 3 means that, if one chooses to do the operation three before addition, the number of steps, from that point, is not the same. Er... words are difficult. A better explanation of what I'm trying to say:

three (3+4)
=> three (7)     (+)
=> 3             (three)

three (3+4)
=> 3          (three)

Incidentally, my answer is 2.

1.2.3 This is one of the longer questions, and has multiple parts.

(i) zero is an expression (ii) if e is an expression, so are (succ e) and (pred e). Two rules:

(succ(pred e)) => e (succ.1)

(pred(succ e)) => e (pred.1)

Simplify (succ(pred(succ(pred(pred zero)))))

(succ(pred(succ(pred(pred zero)))))
=> (succ(pred(pred zero)))       (succ(pred e))
=> (pred zero)                   (succ(pred e))

(succ(pred(succ(pred(pred zero)))))
=> (succ(pred(pred zero)))       (pred(succ e))
=> (pred zero)                   (succ(pred e))

(succ(pred(succ(pred(pred zero)))))
=> (succ(pred(succ(pred e))))    e = (pred zero)
=> (succ(pred(e))                (succ(pred e))
=> e                             (succ(pred e))
=> (pred zero)

(succ(pred(succ(pred(pred zero)))))
=> (succ(pred(succ(pred e))))    e = (pred zero)
=> (succ(pred e))                (pred(succ e))
=> e                             (succ(pred e))
=> (pred zero)

How many ways can the reduction rules be applied? Do they all lead to the final result?

Assuming these are the same:

(succ(pred(succ(pred(pred zero)))))
=> (succ(pred(pred zero)))      (succ(pred(e))
=> (pred zero)                  (succ(pred e))

(succ(pred(succ(pred(pred zero)))))
=> (succ(pred(pred zero)))      (succ(pred(e))
=> (pred zero)                  (succ(pred e))

three ways. They all lead to the final result.

Prove that the process must terminate for all given expressions.

A preface: I can't say I've ever successfully or acceptably proven anything. Ever.
The variable e can be, at it's simplest, one of these three expressions: zero, (succ e), and (pred e).
In the case of (succ (succ zero)), e is equivalent to (succ zero) and the expression reduces to (succ e). Similarly (where e is equivalent, to zero, (succ e), or (pred e)):

(succ(pred e)) => e
(pred(succ e)) => e
(succ(succ e)) => (succ e)
(pred(pred e)) => (pred e)

The two rules of reduction will always reduce an expression to one of the three simple expressions, and so the process will terminate for all expressions.

Suppose a third rule is added: (iii) if e1 and e2 are expressions, then so is (add e1e2).
The corresponding reduction rules:

(add zero e2) => e2
(add (succ e1)e2) => (succ (add e1e2))
(add (pred e1)e2) => (pred (add e1e2))

Simplify (add(succ(pred zero)) zero). How many ways can the reduction rules be applied? Do they all lead to the final result?

e1 = (pred zero), e2 = zero
(add(succ(pred zero)) zero)
=> (add (succ e1)e2)
=> (succ (add e1e2))
=> (succ (pred zero))
=> zero

(add(succ(pred zero)) zero)
=> (add zero zero)
=> zero

There are two ways the reduction rules can be applied; both lead to the final result.

Prove that the process must terminate for all given expressions.

All the reduction rules will reduce an expression to a simple form -- the process will never get stuck in a loop where it simplifies expression e to f and then back to e. This is probably not an acceptable proof. I will fix this, in the future.

1.2.4 Reduce 1110, 10, and 1110100 using these rules:

 1??x => x1101

0??x => x00

x is an arbitrary sequence of 0s and 1s while ? denotes a single 0 or 1.

1110
=> 01101
=> 0100
=> 000

10
(already in canonical form)

1110100
=> 01001101
=> 0110100
=> 010000
=> 00000
=> 0000
=> 000

Find an expression for which the reduction process does not terminate.

10011
=> 111101
=> 1011101
=> 11011101
=> 111011101
=> 0111011101
=> 101110100
=> 1101001101
=> 10011011101
=> 110111011101
=> 1110111011101
=> 01110111011101
=> 1011101110100
=> 11011101001101
=> 111010011011101
=> 0100110111011101
=> 011011101110100
=> 01110111010000
=> 1011101000000
=> 11010000001101
=> 100000011011101
=> 0000110111011101
=> 011011101110100
=> 01110111010000
=> 1011101000000
=> 11010000001101
=> 100000011011101
=> 0000110111011101
=> 011011101110100

You'll notice it took me a while to see the pattern restarting..... I noticed that the reduction rule for expressions beginning with 1 made the expression longer, so I figured that if x in 1??x involved ones, the next expression would be longer (yes) and so would the next, so on and so on forever. Obviously, that's not what happened. But regardless, the process won't terminate for 10011.

I have no mathematical confidence whatsoever. I'll address this another day.

[IFP] Exercises 1.1

Introduction to Functional Programming by Richard Bird and Philip Wadler.

1.1.1 Using the function square, design a function quad which raises its argument to the fourth power

square :: Num a => a -> a
square x = x * x

quad :: Integer -> Integer
quad = square . square

1.1.2 Define a function max which returns the greater of its two arguments

max' :: Ord a => a -> a -> a
max' a b
  | a > b     = a
  | otherwise = b

1.1.3 Define a function for computing the area of a circle with given radius r (use 22/7 as an approximation to pi)

areaCircle :: Fractional a => a -> a
areaCircle r = pi * r ^ 2
  where pi = 22/7