BEGIN 16_11_08_SequentialVsSimultaneousDeclarations.lhs

SEQUENTIAL, SIMULTANEOUS AND NESTED LOCAL DECLARATIONS

We give several examples to illustrate some of the issues
indicated by the title above. In Example 1, 2, and 3, below,
we exhibit unexpected behaviors, which are explained at the
very of the handout -- under EXPLANATIONS.

These examples also cover some of the issues presented in
the handout 16_10_20_PolymorphicRecursionNotSupported.hs
which showed that POLYMORPHIC RECURSION is not supported
in Haskell.

##############################################################
BEGIN EXAMPLE 1: Sequential versus Simultaneous Recursive Calls.

(1) A private definition of the "map" function, and
how it can be used on an integer list:

> x1  = let myMap f lst = [ f x | x <- lst ];
>           intList lst = myMap succ lst
>       in  intList [2,3,4]

(2) The following should be totally equivalent to (1):

> x2  = let (myMap, intList) = 
>             (\ f lst -> [ f x | x <- lst ],
>              \ lst -> myMap succ lst)
>       in  intList [2,3,4]

(3) Similar to (1), but with a boolean list instead:

> y1  = let myMap f lst = [ f x | x <- lst ];
>           boolList lst = myMap not lst
>       in  boolList [True,False]

(4) The following should be totally equivalent to (3):

> y2  = let (myMap, boolList) = 
>             (\ f lst -> [ f x | x <- lst ],
>              \ lst -> myMap not lst)
>       in  boolList [True,False]

(5) Combining (1) and (3) poses no problem:

> (x3,y3) = let intList  lst = myMap succ lst;
>               boolList lst = myMap not  lst;
>               myMap f  lst = [ f x | x <- lst ]
>           in  (intList [2,3,4], boolList [True,False])

(6) HOWEVER, combining (2) and (4) as follows will NOT work:

  (x4,y4) = let (myMap, boolList, intList) = 
                   (\ f lst -> [ f x | x <- lst ],
                    \ lst -> myMap not lst,
                    \ lst -> myMap succ lst)
           in  (intList [2,3,4], boolList [True,False])

and will return the following error message (using HUGS):

   ERROR - Unresolved top-level overloading
   *** Binding             : x4
   *** Outstanding context : Num Bool

WHAT IS GOING ON HERE????

END EXAMPLE 1
##############################################################
BEGIN EXAMPLE 2 Sequential versus Simultaneous 
                Recursive Calls -- Once More.

(7) The following is similar to (5) and raises no problem:

> (x5,y5) = let twice f y = f (f y);
>               foo v = twice succ v;
>               goo w = twice sqrt w
>           in  (foo 3, goo 16.0)

(8) The following should be equivalent to (7), and is similar 
to (6). But whereas (6) returns an ERROR, this one does not:

> (x6,y6) = let (twice,foo,goo) =
>                  (\ f y -> f (f y),
>                   \ v -> twice succ v,
>                   \ w -> twice sqrt w)
>           in  (foo 3, goo 16.0)

BUT, WHEREAS (7) RETURNS "x5 :: Integer", (8) RETURNS 
"x6 :: Double" !!??!!

WHAT IS GOING ON HERE????

(9) Now we try to redefine "succ" so that its type is
"Int -> Int", which is more specific than the type of
"succ" in the library, "Enum a => a -> a". 

> mySucc :: Int -> Int
> mySucc x = succ x

We also redefine "sqrt" so that its type is "Double -> Double",
which is more specific that the type of "sqrt" in the library,
namely  "Floating a => a -> a".

> mySqrt :: Double -> Double
> mySqrt x = sqrt x

Then we replace "succ" by "mySucc", and "sqrt" by "mySqrt", in
the definition of "(x6,y6)" and -- lo and behold !! -- we get
an error:

 (x7,y7) = let (twice,foo,goo) =
                  (\ f y -> f (f y),
                   \ v -> twice mySucc v,
                   \ w -> twice mySqrt w)
           in  (foo 3, goo 16.0)

The error in HUGS says the following:

   ERROR  - Type error in application
   *** Expression     : twice mySucc v
   *** Term           : mySucc
   *** Type           : Int -> Int
   *** Does not match : Double -> Double

WHAT IS GOING ON HERE????

END EXAMPLE 2
#############################################################
BEGIN EXAMPLE 3: Sequential versus Simultaneous 
                 Recursive Calls -- Once More, Again.

This example is about TRANSPOSING A MATRIX. A matrix is 
represented by a list of lists. For example, the following matrix:

        1 2 3
        4 5 6

is represented by [[1,2,3], [4,5,6]] where the first list "[1,2,3]"
is the first row of the matrix, and the second list "[4,5,6]" is 
the second row of the matrix. To transpose the matrix means to "rotate" 
it along its main diagonal, from the NW corner to the SE corner. So, 
for the preceding matrix, its transpose is:

        1 4
        2 5
        3 6

and its representation as a list of lists is [[1,4], [2,5], [3,6]].

(10) Here is a natural and straightforward way of transposing a matrix:

> x8 = let -- input should be a list of equal-length non-empty lists,
>          -- otherwise an error will occur
>          transpose :: [[a]] -> [[a]]; 
>          transpose ([]:_) = [];
>          transpose xss    = (map head xss) : transpose (map tail xss)
>      in  transpose [[1,2,3], [4,5,6]]

(11) The function "map" is used twice in the definition of "transpose" 
in (10). So we can try to abstract it, as follows:

  x9 = let transpose _ ([]:_) = [];
           transpose f xss    =  (f head xss) : transpose f (f tail xss)
       in  transpose map [[1,2,3], [4,5,6]]

But the preceding gives the following error (on HUGS):

  ERROR  - Type error in application
  *** Expression     : f head xss
  *** Term           : head
  *** Type           : [[a]] -> [a]
  *** Does not match : [a] -> [a]
  *** Because        : unification would give infinite type

(12) We try to remedy the problem in (11), by abstracting twice "map"
in (10), as follows -- and this works fine:

> x10 = let transpose _ _ ([]:_) =  [];
>           transpose f1 f2 xss  = (f1 head xss) : transpose f1 f2 (f2 tail xss)
>       in  transpose map map [[1,2,3], [4,5,6]]

WHAT IS GOING ON HERE????

END EXAMPLE 3
##############################################################

EXPLANATIONS

EXAMPLE 1. The declaration in (5) is interpreted in the
same way as the following:

> (v1,w1) = let  myMap f  lst = [ f x | x <- lst ]
>           in   let  intList  lst = myMap succ lst;
>                     boolList lst = myMap not  lst
>                in  (intList [2,3,4], boolList [True,False])

The declaration in (6) cannot be serialized, and is forced
to be simultaneous by the programmer.

EXAMPLE 2. Obviously (7) and (8) are not equivalent, since
(7) returns "x5 :: Integer" and (8) returns "x6 :: Double".

The declaration in (7) is interpreted as:

> (v2,w2) = let twice f y = f (f y)
>           in  let foo v = twice succ v;
>                   goo w = twice sqrt w
>               in  (foo 3, goo 16.0)

Whereas in (8), the user forces the let-declaration to be 
simultaneous. But (8) does not return an error, rather it
makes the type of x6 "Double" instead of "Integer", i.e.
it makes the types of x6 and y6 to be the same "Double".

That the interpreter canNOT handle the case when the user
forces the type of the "x" and the type of the "y" to be 
different is confirmed by (9).

EXAMPLE 3. In the 3rd line in (11) of the definition of 
"transpose", the two recursive calls to "f" in the subexpressions:

     (f head xss)

and  (f tail xss)

do not have the same type. Observing that "f" stands for "map", the
type of the first recursive call to "f" above must be of the form:

     f :: ([a] -> a) -> [[a]] -> [a]

whereas the type of the second recursive call to "f" must be:

     f :: ([a] -> [a]) -> [[a]] -> [[a]]

The interpreter cannot handle different recursive calls to
the same function "f" with different types.

END 16_11_08_SequentialVsSimultaneousDeclarations.lhs