// Read this first: https://cosc59.gitlab.io/hs/functors-in-math-vs-haskell.txt

// In class we drew this diagram, known as the _commutative diagram_:
//
//        fmap f
//   F x -------> F y    :type F a
//    ^            ^
//    |            |
//  F |            | F
//    |     f      |
//    x ---------> y     :type a 
//
// That is, if you construct the type 'F a' out of a type 'a' with a constructor F 
//   -- think of constructors like (:) and [] for the list [a] ,
//       or the constructors Just and Nothing for 'Maybe a' --
//  then we say that F is a Functor (possibly among other things, such as
//    being a Monad) if there is a function  fmap  defined for F such that
//    you get the same result if you do  f x  first and then construct  F (f x)
//     or if you first construct  F x  and then apply (fmap f) to (F x) 
//
//  That is, F is a Functor if it defines an  fmap  function such that
//      F (f x) == fmap f (F x)
//                 ^^^^^^----------- associates left, so this is (fmap f) 

// Let's look at Maybe and [] as Functors:

sergey@snowball hs % ghci
GHCi, version 9.12.2: https://www.haskell.org/ghc/  :? for help

// A reminder: Just and Nothing are the two constructors of Maybe.  
//  So there are one two ways to make a 'Maybe Int' type:
//     - call Just with an Int
//     - call Nothing. 

// 'Maybe' comes with automatic ways of constructing code for 'Maybe a'
//   for whatever type 'a' you choose. For example, for any function
//    f: a -> a  you will get a function f': Maybe a -> Maybe a  simply
//    by applying  fmap f  to a 'Maybe a' object:  

ghci> :i Maybe
type Maybe :: * -> *
data Maybe a = Nothing | Just a
  	-- Defined in ‘GHC.Internal.Maybe’
instance Semigroup a => Monoid (Maybe a)
  -- Defined in ‘GHC.Internal.Base’
instance Semigroup a => Semigroup (Maybe a)
  -- Defined in ‘GHC.Internal.Base’
instance Foldable Maybe -- Defined in ‘GHC.Internal.Data.Foldable’
instance Traversable Maybe
  -- Defined in ‘GHC.Internal.Data.Traversable’
instance Read a => Read (Maybe a) -- Defined in ‘GHC.Internal.Read’
instance Show a => Show (Maybe a) -- Defined in ‘GHC.Internal.Show’
instance Applicative Maybe -- Defined in ‘GHC.Internal.Base’

instance Functor Maybe -- Defined in ‘GHC.Internal.Base’  // <==== because of this!

instance MonadFail Maybe
  -- Defined in ‘GHC.Internal.Control.Monad.Fail’
instance Monad Maybe -- Defined in ‘GHC.Internal.Base’
instance [safe] Eq a => Eq (Maybe a)
  -- Defined in ‘GHC.Internal.Maybe’
instance [safe] Ord a => Ord (Maybe a)
  -- Defined in ‘GHC.Internal.Maybe’

------- Here is how fmap for 'Maybe a' is defined in Prelude 98 ---------

instance  Functor Maybe  where
    fmap f Nothing    =  Nothing
    fmap f (Just x)   =  Just (f x)

--- https://www.haskell.org/onlinereport/standard-prelude.html
------- end Prelude ---------

ghci> let sq x = x*x

ghci> sq 100
10000

ghci> fmap sq (Just 100)
Just 10000

ghci> fmap sq (Just 1)
Just 1

ghci> fmap sq (Just 2)
Just 4

ghci> fmap sq (Just 3)
Just 9

// Syntactically the same as:

ghci> (fmap sq) (Just 3)
Just 9

// ..and the same as (recall that $ has precedence 0):

ghci> fmap sq $ Just 3
Just 9

ghci> fmap sq (Just 100) == Just (sq 100)
True

// Let's not forget about Nothing in Maybe Int

ghci> fmap sq Nothing == Nothing
True

// So (fmap sq) works for both constructors of 'Maybe Int' (and any 'Maybe a' where a is a Num)

// But that's not all! The 'List a' type [a] is also a Functor:
//  the moment you define [a] for a type 'a' you also get a factory
//  that for any function  f: a -> a  makes f': [a] -> [a] , e.g.,
//  an automatic way of making functions on lists from functions on elements.

// But of course we already saw it: it's the MAP function. Yet now we see it
//  in a new light. List is a Functor, see below:

ghci> :i []
type List :: * -> *
data List a = [] | a : [a]
  	-- Defined in ‘GHC.Types’
instance Traversable []
  -- Defined in ‘GHC.Internal.Data.Traversable’
instance MonadFail []
  -- Defined in ‘GHC.Internal.Control.Monad.Fail’
instance Foldable [] -- Defined in ‘GHC.Internal.Data.Foldable’
instance Monoid [a] -- Defined in ‘GHC.Internal.Base’
instance Read a => Read [a] -- Defined in ‘GHC.Internal.Read’
instance Semigroup [a] -- Defined in ‘GHC.Internal.Base’
instance Ord a => Ord [a] -- Defined in ‘GHC.Classes’
instance Show a => Show [a] -- Defined in ‘GHC.Internal.Show’
instance Eq a => Eq [a] -- Defined in ‘GHC.Classes’
instance Applicative [] -- Defined in ‘GHC.Internal.Base’

instance Functor [] -- Defined in ‘GHC.Internal.Base’ // <==== because of this!

instance Monad [] -- Defined in ‘GHC.Internal.Base’

------- from the Preamble: ------
instance Functor [] where
    fmap = map
------- end Premable ------------

// First, let's do [Int]: 

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

ghci> (fmap sq) [4]
[16]

ghci> fmap sq [1..10]
[1,4,9,16,25,36,49,64,81,100]

// Now let's do a List of Maybe Ints, [Maybe Int]:

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

// ..which, remember, is the same as

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

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


// Note that it's the application to a particular type that picks the
//  right  fmap . Without it, the type signature of (fmap sq) remains
//  generic and undermined:

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

//---------- Here are some outtakes. What did I do wrong? ------------

ghci> fmap sq [Just 1, Just 2, Just 3]
<interactive>:5: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

//  .... fmap sq picks the list version, but the list is of 'Maybe Int',
//        not Int, whereas sq only consumes Int.

ghci> (fmap sq) [Just 1, Just 2, Just 3]
<interactive>:6: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

//  .... exactly the same thing, exactly the same error.

//  And now 

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

<interactive>:8:1: error: [GHC-39999]
    • Ambiguous type variable ‘f0’ arising from a use of ‘print’
      prevents the constraint ‘(Show (f0 Integer))’ from being solved.
      Probable fix: use a type annotation to specify what ‘f0’ should be.
      Potentially matching instances:
        instance (Show a, Show b) => Show (Either a b)
          -- Defined in ‘GHC.Internal.Data.Either’
        instance Show a => Show (Maybe a) -- Defined in ‘GHC.Internal.Show’
        ...plus 16 others
        ...plus 33 instances involving out-of-scope types
        (use -fprint-potential-instances to see them all)
    • In a stmt of an interactive GHCi command: print it

// ....and now we prepared something that typechecks but we don't know
//      how to compute it or print it:

ghci> :t fmap (fmap sq) [1, 2, 3]
fmap (fmap sq) [1, 2, 3] :: (Functor f, Num b, Num (f b)) => [f b]
--------------- end outtakes --------------------

// But there's still more! The list [a] is a Monad too:

ghci> :i []
type List :: * -> *
data List a = [] | a : [a]
  	-- Defined in ‘GHC.Types’
instance Traversable []
  -- Defined in ‘GHC.Internal.Data.Traversable’
instance MonadFail []
  -- Defined in ‘GHC.Internal.Control.Monad.Fail’
instance Foldable [] -- Defined in ‘GHC.Internal.Data.Foldable’
instance Monoid [a] -- Defined in ‘GHC.Internal.Base’
instance Read a => Read [a] -- Defined in ‘GHC.Internal.Read’
instance Semigroup [a] -- Defined in ‘GHC.Internal.Base’
instance Ord a => Ord [a] -- Defined in ‘GHC.Classes’
instance Show a => Show [a] -- Defined in ‘GHC.Internal.Show’
instance Eq a => Eq [a] -- Defined in ‘GHC.Classes’
instance Applicative [] -- Defined in ‘GHC.Internal.Base’
instance Functor [] -- Defined in ‘GHC.Internal.Base’
instance Monad [] -- Defined in ‘GHC.Internal.Base’ // <<==== here!

-------------------- begin Prelude --------------------
instance  Monad []  where
    m >>= k          = concat (map k m)
    return x         = [x]
    fail s           = []
-------------------- end Prelude --------------------

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

// OK, this didn't work. Remember that the function to the right of >>=
//   must make F b , not just b . 

ghci> :t (>>=)
(>>=) :: Monad m => m a -> (a -> m b) -> m b

// So this works:

ghci> [1,2,3] >>= \x -> [x*x]
[1,4,9]

ghci> [1..10] >>= \x -> [x*x]
[1,4,9,16,25,36,49,64,81,100]

// The same can be achieved with more general syntax, thanks to type inference!
//   Type inference will supply the right type for 'return' in this:

ghci> [1..10] >>= return . sq
[1,4,9,16,25,36,49,64,81,100]

ghci> Just 10 >>= return . sq
Just 100

// Notice that the pipeline of actions to the right of >>= is exactly the
//  same now, and does exactly the right thing for the type on the left.