-- BEGIN 16_10_20_PolymorphicRecursionNotSupported.hs

-- POLYMORPHIC RECURSION IS NOT SUPPORTED IN HASKELL

-- We give two sequences of functions {mystery1,...,mystery10}
-- and {foo1,...,foo4}. In each of these two sequences, every
-- function is a variation on the preceding one, culminating
-- in a function (mystery10 and foo4) that canNOT type-check 
-- in Haskell because it involves a recursive definition that 
-- must be typed polymorphically.

mystery1 = let
              myMap f [] = [] 
              myMap f (x : xs) = f x : myMap f xs
           in let 
                 (plus1, plus2) = (myMap (+1), myMap (+2))
              in (plus1 [1,2,3], plus2 [1,2,3])
                 
mystery2 = let
              myMap f [] = [] 
              myMap f (x : xs) = f x : myMap f xs  
           in let 
                 (notList, notnotList) = (myMap not, myMap (not . not))
              in (notList [True,False], notnotList [True,False])

mystery3 = let
              myMap f [] = [] 
              myMap f (x : xs) = f x : myMap f xs  
           in let 
                 (notList, plus1) = (myMap not, myMap (+1))
              in (notList [True,False], plus1 [1,2,3])

mystery4 = let
              myMap f [] = [] 
              myMap f (x : xs) = f x : myMap f xs  
              notList = myMap not
              plus1 = myMap (+1)
           in (notList [True,False], plus1 [1,2,3])

mystery5 = let
              myMap f [] = [] 
              myMap f (x : xs) = f x : myMap f xs  
              (notList, plus1) = (myMap not, myMap (+1))
           in (notList [True,False], plus1 [1,2,3])

mystery6 = let
            myMap f xs = [ f x | x <- xs ] 
            (notList, plusOne) = (myMap not, myMap (+1))
           in (notList [True,False], plusOne [1,2,3])
              
mystery7 = let
            myMap = \ f -> \ xs -> [ f x | x <- xs ] 
            (notList, plusOne) = (myMap not, myMap (+1))
           in (notList [True,False], plusOne [1,2,3])
              
mystery8 = let
            (myMap, notList) = 
              (\ f -> \ xs -> [ f x | x <- xs ], myMap not)
           in notList [True,False]
              
mystery9 = let
            (myMap, plusOne) = 
              (\ f -> \ xs -> [ f x | x <- xs ], myMap (+1) )
           in plusOne [1,2,3]
              
{- the following will NOT type-check because Haskell does NOT
   support "polymorphic recursion" -- this is "recursion" because
   "myMap" appears on both sides of the let-binding and it is
   "polymorphic" because the two occurrences of "myMap" on the
   right-hand side of the binding are necessarily of different
   types. The first occurrence of "myMap" on the right-hand side
   must have type "(Bool -> Bool) -> [Bool] -> [Bool]", 
   and the second occurrence must have type 
   "(Int -> Int) -> [Int] -> [Int]" (assuming that (+1) has type 
   "Int -> Int":

mystery10 = let
             (myMap, notList, plusOne) = 
               (\ f -> \ xs -> [ f x | x <- xs ], myMap not, myMap (+1))
            in (notList [True,False], plusOne [1,2,3])
-}
   
-- in "foo", the type of "f" is "a -> a", and it can be instantiated
-- to "b -> b" as well as "(b -> b) -> (b -> b)", which makes possible
-- the typing of the self-application "f f":

foo1  = let
         f = \ x -> x
        in let   
            g = f f
           in g True 

-- "foo2" is totally equivalent to "foo1": 

foo2 = let
         f = \ x -> x
         g = f f
       in g True
        
-- "foo3" confirms that the let-binding of "g" is polymorphic:

foo3 = let
       f = \ x -> x
       g = f f
      in (g True, g "abc")

{- "foo4" will NOT type-check, again because Haskell does not
   support "polymorphic recursion": 

foo4 = let
       (f,g) = (\ x -> x, f f)
      in (g True, g "abc")
-}

-- END 16_10_20_PolymorphicRecursionNotSupported.hs