==============[ A taste of monadic programming ]=============

The Maybe Int (see recap below) is perhaps the simplest example of a
monadic type.

---------------[ What is "monadic"? ]---------------

This term came from the theory side. For our practical purposes,
a monad is a parametrized type ("wrapping" some other type "a") 
that allows the  >>=  operator (and a couple of other useful 
operators such as >> and 'return'; 'return' is absolutely not
related to its C or Java namesakes, and only allows us to make
a "wrapped" object in the monadic type from the basic type "a").  

After all, a type is about what common operations we can perform on
its values.

---------------[ A recap of Maybe's >>= and "wrapping" ]---------------

In the previous lectures we saw the operator >>= that---together with
the addition of a special point, called Nothing, to the type of
integer indexes---worked to set up a pipeline of arithmetic
operations, in which Nothing could also participate. That way, if a
function like  elemIndex  returned a Nothing, the pipeline was able to
handle it, by passing that Nothing along rather than trying to add
actual numbers to it and failing with a type error.

We created a new type for adding this special point to integers.  For
purposes of pattern-matching and also for keeping our type system
sound, this addition requires wrapping our numbers in a new data
constructor, so that functions that get our new type as an argument
could pattern-match between the cases of getting Nothing and getting
an actual number. Thus we add two data constructors, one for nothing
and another for the "wrapped" numbers.

This operation is so frequent in Haskell, that the Prelude provides
the generic type "Maybe a" that adds Nothing to whatever data values
the type "a" can take. The wrapper data constructor is called Just.
You can say that we extended the numeric type by creating a Maybe
type from it.

We could have used any other names for this new type and its data
constructors, like 

  data Index = Ind Int | NoIndex
  
(in which case we construct indexes as "Ind 0", "Ind 1", "NoIndex", etc.,
 and get :t Ind 0  => Index  ,  :t NoIndex  => Index)

or 

  data Index = Index Int | Nothing 

(note that the data constructor on the right-hand side of the Index 
 type can also be called Index, so "Index 0" works, unlike in the case
 above; the namespaces of types and their data constructors are separate.)

However, elemIndex of Data.List already uses the standard "Maybe a" type,
and we will use it to remain idiomatic. Note that if we use Nothing with
our new type Index as in the second alternative, the definition succeeds,
but we'll get collision warnings with Prelude's own Nothing, like this:

*Main> :t Index 5
Index 5 :: Index

*Main> :t Nothing

<interactive>:1:1:
    Ambiguous occurrence ‘Nothing’
    It could refer to either ‘Main.Nothing’, defined at ind.hs:2:26
                          or ‘Prelude.Nothing’,
                             imported from ‘Prelude’ at ind.hs:1:1
                             (and originally defined in ‘Data.Maybe’)

So best take advantage of the standard "Maybe", getting "Maybe Int":

*Main> import Data.List

*Main Data.List> elemIndex 'y' "xyz"
Just 1

*Main Data.List> :t elemIndex 'y' "xyz"
elemIndex 'y' "xyz" :: Maybe Int

Prelude Data.Maybe Data.List> elemIndex "a" ["y" , "x", "z" ] >>= Just . ((+) 1) >>= Just . ((*) 2)
Nothing

Prelude Data.Maybe Data.List> elemIndex "z" ["y" , "x", "z" ] >>= Just . ((+) 1) >>= Just . ((*) 2)
Just 6

---------------[ Maybe as a Monad ]---------------

Now the >>= operator is only available for Maybe Int (i.e., its application
typechecks and compiles) because it is defined here:
http://hackage.haskell.org/package/base-4.4.0.0/docs/src/Data-Maybe.html

data  Maybe a  =  Nothing | Just a
  deriving (Eq, Ord, Generic)

instance  Monad Maybe  where
    (Just x) >>= k      = k x
    Nothing  >>= _      = Nothing

    (Just _) >>  k      = k
    Nothing  >>  _      = Nothing

    return              = Just
    fail _              = Nothing


Observe the meaning of these definitions. The data constructor 'Just' is
used to pattern-match the values (in our case of Maybe Int, those tagged
by/built with Int). The argument k of >>= is a function that works on the
type that Maybe maps and extends. You can think of k as the continuation
function passed to >>= . Indeed, all that >>= does is applies k to x, as
any CPS function would! But when Nothing is the first argument of >>= , no
application of k to x happens, and Nothing just gets passed on.  This
definition allows it to pass down the pipeline without exceptions, even
though all functions in the pipeline are written to operate on Ints!

Note that >>= associates to the _left_, with the least priority, so
that the code between >>=s need not be bracketed, and the first >>=
looking from the left is applied first. Recall that : associates to
the right, and so we can write 1 : 2 : 3 : [] meaning to have the
rightmost : done first; but function application associates to the
left, so f g h x is ((f g) h) x and "sq sq 2" (where sq x = x*x) fails
without brackets, being "(sq sq) 2", not the intended "sq (sq 2)".

Also note that if you need to inject the basic type value into
the pipeline at any point, you could use 'return'.

You can even start with 'return'! Or even have 'return 5' all alone,
and it still typechecks!

Prelude> :t return 5 
return 5 :: (Num a, Monad m) => m a

Into what type is 5 being wrapped, you ask, when no type is explicitly 
given above? Well, type inference will conclude that you want to 
wrap 5 into some monadic type, and leave it at that. If this
expression is used in a larger one, more type inference info
will become available, and that monad 'm' will be inferred:

Prelude> return 5 >>= \x -> if x > 0 then Just x else Just 0 
Just 5
Prelude> return 0 >>= \x -> if x > 0 then Just x else Just 0 
Just 0
Prelude> return (-1) >>= \x -> if x > 0 then Just x else Just 0 
Just 0
Prelude> Nothing >>= \x -> if x > 0 then Just x else Just 0 
Nothing

Note that by using the Just constructor, we pulled in the Maybe's
definition of what to do for Nothing at no extra coding cost! 

This the 'negative code' that Doug McIlroy spoke about when he
said that the real hero of programming is the one who writes negative code,
https://en.wikipedia.org/wiki/Douglas_McIlroy:

"""
McIlroy is attributed the quote "The real hero of programming is the one who writes
negative code,"[32] where the meaning of negative code is taken to be similar to the
famous Apple developer, Bill Atkinson, team anecdote[33] (i.e., when a change in a program
source makes the number of lines of code decrease ('negative' code), while its overall
quality, readability or speed improves).
"""



--------------[ Maybe as a Functor ]--------------

Notice another definition in Data.Maybe:

instance  Functor Maybe  where
    fmap _ Nothing       = Nothing
    fmap f (Just a)      = Just (f a)

It allows us to create functions that act on 'Maybe a'
from functions on 'a', with fmap.

Prelude> let sq x = x*x

Prelude> fmap sq $ Just 10   --or fmap sq (Just 10)
Just 100

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

Prelude>  fmap ((+) 1) (Just 2)  
Just 3

See also examples in either-to-io-log.txt

Note that for lists [], fmap is the same as map---it is a
generalization of map. Recall that map gives you a function from a
list of A to a list of B if you give it a function from A to B. From
simply generalizes it for other kinds of types constructed from other
types, not just list. These constructions may involve just one object
of the base type (like Maybe), or potentially infinitely many (like
[]).

In fact, in https://hackage.haskell.org/package/base-4.4.1.0/docs/src/GHC-Base.html
you'll find:

instance Functor [] where
    fmap = map

This is why fmap is defined for [], and does the same thing as map:

Prelude> map sq [1,2,3,4,5]
[1,4,9,16,25]
Prelude> fmap sq [1,2,3,4,5]
[1,4,9,16,25]

fmap helps us write "negative code"---or just as much code as needed.

---------------[ IO as a Monad ]---------------

Maybe is a very simple monad. Haskell's IO is also a monad---a lot more
complex, of course, because it interacts with the OS. This monad serves a
very important goal (among others): to separate pure operations from those
that involve the OS state, and may end up in failure for whatever OS
reasons (e.g., your terminal went away, a file ended, or could not be read
from, or didn't exist, etc.)

Haskell IO takes getting used to. Work through examples in "Learn You a
Haskell" and "Read World Haskell" in the readings above---and make sure to
keep track of the types!

Note that the "do" notation actually hides >>= (for IO, which, of course,
has a different instance definition from Maybe) and <- in the "do" notation
hides lambdas. For example,

main = do 
    chat
    putStrLn "Bye!"

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

is actually:

main = chat >> 
       putStrLn "Bye!" 

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

Note that the lambda fits the >>= type signature, because using putStrLn
on a pure string brings that string into the monad IO (). Note that
getLine is IO String; but the signature of >>= is general enough to fit
both (a is String here, b is (), m is IO)

Prelude> :t getLine
getLine :: IO String
Prelude> :t (>>=)
(>>=) :: Monad m => m a -> (a -> m b) -> m b