=================[ Why/what the Functor? ]=================

There is a confusing difference between https://en.wikipedia.org/wiki/Functor
and https://en.wikipedia.org/wiki/Functor_(functional_programming) . Both definitions
seem to make sense and they are clearly related, but the mathematical Functor
definition implies _two_ maps, one for objects and one for functions/arrows/morphisms,
whereas Haskell's Functor defines only one, fmap, which maps functions.

Here is the relation, to the best of my understanding. Haskell types are constructed 
by data constructors such as (:) for 'List a', or Just for 'Maybe a'. These data
constructors are what maps elements of type a to those of 'List a' or 'Maybe a'. That
is, the data constructors map the objects, and that type's corresponding fmap maps the
functions/arrows/morphisms.

The point of this is getting functions that operate on constructed parametrized types like
List and Maybe from the functions that operate on the parameter types, with nothing more
than just an application of fmap.

% ghci
GHCi, version 9.10.1: https://www.haskell.org/ghc/  :? for help

ghci> let sq x = x*x        -- a function on integers

ghci> map sq [1,2,3,4]      -- natural, but what does it mean?
[1,4,9,16]

ghci> :t map sq             -- (map sq) is a function from List of Num to List of Num 
map sq :: Num b => [b] -> [b]

// In general, for whatever type defines fmap, (fmap sq) is already there:

ghci> :t fmap sq
fmap sq :: (Functor f, Num b) => f b -> f b

// That looks quite general. In fact, this will work for both List and Maybe:

ghci> fmap sq (Just 2)
Just 4

ghci> fmap sq (Just 6)
Just 36

ghci> fmap sq [1, 2, 3]
[1,4,9]

// We can use List's fmap to make a list of 'Maybe Int'. After all, Just is a data constructor, i.e., a function like any other

ghci> :t Just
Just :: a -> Maybe a

ghci> fmap Just [1,2,3,4]
[Just 1,Just 2,Just 3,Just 4]

ghci> :t [Just 1,Just 2,Just 3,Just 4]
[Just 1,Just 2,Just 3,Just 4] :: Num a => [Maybe a]

ghci> :t fmap Just
fmap Just :: Functor f => f a -> f (Maybe a)

// The above works because Maybe is a Functor, i.e., defines fmap: 

ghci> :i Maybe
type Maybe :: * -> *
data Maybe a = Nothing | Just a
  	-- Defined in ‘GHC.Internal.Maybe’
instance Traversable Maybe
  -- Defined in ‘GHC.Internal.Data.Traversable’
instance MonadFail Maybe
  -- Defined in ‘GHC.Internal.Control.Monad.Fail’
instance Applicative Maybe -- Defined in ‘GHC.Internal.Base’
instance Foldable Maybe -- Defined in ‘GHC.Internal.Data.Foldable’
instance Functor Maybe -- Defined in ‘GHC.Internal.Base’    -- <<--- defines fmap
instance Monad Maybe -- Defined in ‘GHC.Internal.Base’
instance Semigroup a => Monoid (Maybe a)
  -- Defined in ‘GHC.Internal.Base’
instance Read a => Read (Maybe a) -- Defined in ‘GHC.Internal.Read’
instance Semigroup a => Semigroup (Maybe a)
  -- Defined in ‘GHC.Internal.Base’
instance Ord a => Ord (Maybe a) -- Defined in ‘GHC.Internal.Maybe’
instance Show a => Show (Maybe a) -- Defined in ‘GHC.Internal.Show’
instance Eq a => Eq (Maybe a) -- Defined in ‘GHC.Internal.Maybe’

// So what does it take to define sq on a List of Maybe Int? 

// Perhaps we could through Just in there somewhere? Doesn't work:

ghci> fmap (Just . sq) [Just 1, Just 2, Just 3]
<interactive>:13:1: error: [GHC-39999]
    • No instance for ‘Num (Maybe Integer)’ arising from a use of ‘it’
    • In the first argument of ‘print’, namely ‘it’
      In a stmt of an interactive GHCi command: print it

// BUT, this works: 

ghci> fmap (fmap sq) [Just 1, Just 2, Just 3]
[Just 1,Just 4,Just 9]

// Behold! The above is a miracle of type inference. The inner fmap is that of Maybe,
//  the outer fmap is that of List!

// Also observe:

ghci> :t fmap (fmap sq)
fmap (fmap sq)
  :: (Functor f1, Functor f2, Num b) => f1 (f2 b) -> f1 (f2 b)

// The type of b is inferred to be a Num, thanks to sq containing a '*', a trait of Num.
//   The other two functors are left hanging, except for the fact that they are functors,
//    that is, define their own instance of fmap. Once applied to Maybe and List, the
//    right fmaps will be inferred, purely statically.

// The same magic drives "return". A mere mention of Maybe's Just data constructor
//  leads the type inference to produce a Maybe type:

ghci> Just 5 >>= \x -> return (x*x) 
Just 25

// We can say the same shorter:

ghci> Just 5 >>= return . sq
Just 25

// BTW, observe this:

ghci> return 5 >>= \x -> return (x*x)
25

Note that this way of creating new functions on newly constructed objects is not entirely
free. It is no doubt liberating, because it eliminates a lot of boilerplate special-case
code, but it is also limiting, because it forces the functions defined on the constructed
objects to play nice with fmap. This limits your decisions on what might be an otherwise
convenient corner case, like 'head' and 'tail' on []. See https://cosc59.gitlab.io/hs/why-no-head-of-empty-list.txt

So Haskell's "theorems for free" actually means "no special case left behind".

The following blog presents many excellent examples of parametrized types that---by
construction!---provide a "free" way of extending _all_ functions on their parameter type
to the constructed type, by defining fmap for that type (a.k.a., making them Functor types):

    https://blog.jle.im/entry/functors-to-monads-a-story-of-shapes.html

The author refers to this impressive property as the "shape" preserved by functor.
Getting _any_ functions that are defined on the 'base' type to operate on any 'derived' type is
indeed amazing, but there is no mystery where that capability comes from. It is all
due to their data constructors and the corresponding fmap handling of these constructors
in its pattern matching.

=====================[ The IO monad ]=======================

IO is a very different kind of a monad, but the type inference works just the same with it:

% cat rock.hs
-- From http://learnyouahaskell.com/input-and-output, slightly modified

main = do 
    chat  
    putStrLn "Bye!"

chat = do
    putStrLn "Hello, what's your name?"
    name <- getLine
    putStrLn ("Hey " ++ name ++ ", you rock!")

% ghc rock

% ./rock
Hello, what's your name?
Sergey
Hey Sergey, you rock!
Bye!

% cat rock-desugared.hs
-- Slightly modified from http://learnyouahaskell.com/input-and-output

-- check the types of these functions!

main = chat >>
    putStrLn "Bye!" 

chat = putStrLn "Hello, what's your name?" >> 
    getLine >>= \ name -> putStrLn ("Hey " ++ name ++ ", you rock!")

% ghci
GHCi, version 9.10.1: https://www.haskell.org/ghc/  :? for help

ghci> :t getLine
getLine :: IO String

ghci> :i putStrLn
putStrLn :: String -> IO () 	-- Defined in ‘GHC.Internal.System.IO’

ghci> let chat = putStrLn "Hello, what's your name?" >> getLine >>= \ name -> putStrLn ("Hey " ++ name ++ ", you rock!")

ghci> chat
Hello, what's your name?
Foo
Hey Foo, you rock!

ghci> :t chat
chat :: IO ()