CSE 360 Homework 1

1. Below are the abstract data types for conj and or presented in lecture notes lect2.

   abstype ('a,'b) conj = c of 'a * 'b  with
      fun pair x y = c(x,y)
      fun left (c(x,y)) = x
      fun right(c(x,y)) = y             end;
   abstype ('a,'b) or = left of 'a | right of 'b with
      fun putl x = left x
      fun putr x = right x
      fun cases (left x)  f g = f x
        | cases (right x) f g = g x              end;
   

   Write ML programs of the following types using only these data types and applications and abstractions ( fn).

   ('a -> 'a -> 'b) -> 'a -> 'b
   (('a,'b) or -> 'c) -> ('a -> 'c,'b -> 'c) conj
   (('a,'a -> 'b) or -> 'b) -> 'b
   ((('a -> 'b) -> 'c) -> 'd) -> 'a -> ('b -> 'c) -> 'd
   

2. Below is are some date type declarations.

   datatype r = a
    and     q = f of s * p * r
    and     v = g of s * v
    and     p = h of r
    and     s = j of r;
   

   With respect to these constants (and just application and abstraction), build terms of the type q and of type v -> v.