--- What do we do about operations that can't succeed? For example, Haskell's
---  head [] must fail, because there is no way for us to unambiguously define
---  the type of its return value. It cannot be the same as the List's element
---  type 'a' in '[a]' and it can't be anything else. So Haskell punts to
---  "this function may crash, will give up a call stack trace if so", a.k.a.
---  HasCallStack:

ghci> head []
<interactive>:1:1: warning: [GHC-63394] [-Wx-partial]
    In the use of ‘head’
    (imported from Prelude, but defined in GHC.Internal.List):
    "This is a partial function, it throws an error on empty lists. Use pattern matching, 'Data.List.uncons' or 'Data.Maybe.listToMaybe' instead. Consider refactoring to use "Data.List.NonEmpty"."

*** Exception: Prelude.head: empty list

HasCallStack backtrace:
  error, called at libraries/ghc-internal/src/GHC/Internal/List.hs:1969:3 in ghc-internal:GHC.Internal.List
  errorEmptyList, called at libraries/ghc-internal/src/GHC/Internal/List.hs:96:11 in ghc-internal:GHC.Internal.List
  badHead, called at libraries/ghc-internal/src/GHC/Internal/List.hs:90:28 in ghc-internal:GHC.Internal.List
  head, called at <interactive>:1:1 in interactive:Ghci1

-- The warning is also a part of its type information:

ghci> :t head
<interactive>:1:1: warning: [GHC-63394] [-Wx-partial]
    In the use of ‘head’
    (imported from Prelude, but defined in GHC.Internal.List):
    "This is a partial function, it throws an error on empty lists. Use pattern matching, 'Data.List.uncons' or 'Data.Maybe.listToMaybe' instead. Consider refactoring to use "Data.List.NonEmpty"."

head :: GHC.Internal.Stack.Types.HasCallStack => [a] -> a

--- Many List operations may result in a failure. For example, getting the index at
---  which an element first occurs in a list (elemIndex) may fail if the element
---  does not in fact occur in the list. Getting the element at an index (!!) may fail if
---  the list doesn't have that many elements, etc.

--- We looked at the list of standard library list functions, Data.List:
---  https://hackage-content.haskell.org/package/base-4.22.0.0/docs/Data-List.html

--- Notice the Maybe return types. A 'Maybe Int' is either Nothing (signifying operation
---   failure) or an actual value. To be pattern-matchable, the value is constructed
---   with the 'Just' constructor:
---
---     Maybe a = Nothing | Just a

--- "Just" is perhaps not the best name for "this operation succeeded and produced an
---  actual value, which you can match in any function like so". Indeed, OCaml and Rust
---  chose to call this type differently. However, the name "Maybe a" or "Maybe monad"
---  had stuck.

--- One nice place to see the code for standard Haskell types is
---     https://www.haskell.org/onlinereport/standard-prelude.html
---   It is from an older version of Haskell but succinct and clear. 

ghci> import Data.List

ghci> :t elem
elem         elemIndex    elemIndices

ghci> :t elemInd
elemIndex    elemIndices

ghci> :t elemIndex 
elemIndex :: Eq a => a -> [a] -> Maybe Int

ghci> let l = ['a', 'b', 'c', 'd']

ghci> :t l
l :: [Char]

-- elemIndex may fail, so its return type is a "Maybe Int": a "Nothing" or a "Just <value>":

ghci> elemIndex 'a' l
Just 0

ghci> elemIndex 'z' l
Nothing

-- We want to handle collections of Maybe indexes and do arithmetic on them,
--   with functions such as (+1) and square 

ghci> let sq x = x*x

-- We can easily make a list of Just values, of type [Maybe Int]:

ghci> map Just (take 10 [1..])
[Just 1,Just 2,Just 3,Just 4,Just 5,Just 6,Just 7,Just 8,Just 9,Just 10]

ghci> :t map Just (take 10 [1..])
map Just (take 10 [1..]) :: (Num a, Enum a) => [Maybe a]

ghci> let jl = map Just (take 10 [1..])

ghci> jl
[Just 1,Just 2,Just 3,Just 4,Just 5,Just 6,Just 7,Just 8,Just 9,Just 10]

-- Now look at the definition of fmap for Maybe. It takes a function that works
--   on some type 'a' (say, Int of Char) and "lifts" it to a function on 'Maybe a',
--   which does the most natural thing on Nothing and on Just x values. 

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

-- fmap applied to sq takes a (Just x) to (Just x*x) and Nothing to Nothing:

ghci> let sq x = x*x
ghci> :t sq
sq :: Num a => a -> a

ghci> fmap sq (Just 5)
Just 25

-- Note that's (fmap sq) (Just 25), function applications associate to the left,
--  just like lambda calculus. It _is_ lambda calculus! Lambda calculus is to Haskell
--  what the CPU ISA is to C. 

ghci> fmap sq Nothing   -- note, that's (fmap sq) Nothing
Nothing

-- Note that this works with 'map' to apply to lists: 

ghci> map (fmap sq) jl
[Just 1,Just 4,Just 9,Just 16,Just 25,Just 36,Just 49,Just 64,Just 81,Just 100]

--  In mathematics, this mapping from objects and functions from one domain
--   to another is called a Functor. In Haskell, defining an 'fmap' makes
--   a type a Functor. Note that List is a Functor too, and its fmap is just map.
--   Technically, map takes a function on elements of the list and turns it into
--   a function on lists:

ghci> :t map sq
map sq :: Num b => [b] -> [b]

--- The most important and natural property of functions is composition, i.e.,
---  the ability to build pipelines that a value travels through. 

--- Maybe defines a handy (>>=) function that allows us to feed (Just x) values
---   to functions that take an 'x'. The same function handily takes Nothing to Nothing:
--
-- instance  Monad Maybe  where
--     (Just x) >>= k   =  k x
--     Nothing  >>= k   =  Nothing
--     return           =  Just
--     fail s           =  Nothing


--- Let's send values coming out of elemIndex to another function: 

ghci> elemIndex 'b' ['a', 'b', 'c', 'd'] 
Just 1

ghci> elemIndex 'a' ['a', 'b', 'c', 'd'] 
Just 0

--- So let's add 1 to the index. This doesn't quite work:

ghci> elemIndex 'a' ['a', 'b', 'c', 'd'] >>= (+1)
<interactive>:20:41: error: [GHC-83865]
    • Couldn't match type ‘Int’ with ‘Maybe b’
      Expected: Int -> Maybe b
        Actual: Int -> Int
    • In the second argument of ‘(>>=)’, namely ‘(+ 1)’
      In the expression: elemIndex 'a' ['a', 'b', 'c', 'd'] >>= (+ 1)
      In an equation for ‘it’:
          it = elemIndex 'a' ['a', 'b', 'c', ....] >>= (+ 1)
    • Relevant bindings include
        it :: Maybe b (bound at <interactive>:20:1)

-- The reason the above didn't work is that (>>=) needs to return a Maybe. So
--  we need to throw in the Just constructor:

ghci> elemIndex 'a' ['a', 'b', 'c', 'd'] >>= \x -> Just (x+1)
Just 1

ghci> elemIndex 'z' ['a', 'b', 'c', 'd'] >>= \x -> Just (x+1)
Nothing

--- It's not pretty to have to type 'Just' or another constructor
---   all over the place. Luckily, there is a 'return' function in Maybe
---   that makes it look prettier:

ghci> elemIndex 'z' ['a', 'b', 'c', 'd'] >>= \x -> return (x+1)
Nothing

--- A bit more syntax, to get rid of the lambda: Haskell defines '.'
---   for composition of simple functions: f . g  is  f (g x)

ghci> :i (.)
(.) :: (b -> c) -> (a -> b) -> a -> c
  	-- Defined in ‘GHC.Internal.Base’
infixr 9 .

ghci> (sq . (+1)) 2 
9
ghci> ( (+1) . sq) 2 
5

-- Note that we need the parens above. Without the parens (+1) will apply to 2
--  and we'll get a type error. 

ghci> sq . (+1) 2 
<interactive>:3:1: error: [GHC-39999]
    • No instance for ‘Show (a0 -> Integer)’
        arising from a use of ‘print’
      (maybe you haven't applied a function to enough arguments?)
    • In a stmt of an interactive GHCi command: print it

-- So this works:

ghci> elemIndex 'z' ['a', 'b', 'c', 'd'] >>=  return . (+1)
Nothing

ghci> elemIndex 'c' ['a', 'b', 'c', 'd'] >>=  return . (+1)
Just 3

--- Note the signature of (>>=): starts with an 'm a' (e.g., Maybe Int),
---   and takes a function from a (e.g., Int) to the Maybe (could be Maybe Int,
---   or could be a different type, e.g., Maybe Char if we look at getting the
---   character at an index that may be Nothing, see below)

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

--- Index operator (!!) is sadly not safe:

ghci> ['a', 'b', 'c', 'd'] !! 0
'a'

ghci> ['a', 'b', 'c', 'd'] !! 3
'd'

ghci> ['a', 'b', 'c', 'd'] !! 4
*** Exception: Prelude.!!: index too large

HasCallStack backtrace:
  error, called at libraries/ghc-internal/src/GHC/Internal/List.hs:1627:14 in ghc-internal:GHC.Internal.List
  tooLarge, called at libraries/ghc-internal/src/GHC/Internal/List.hs:1637:50 in ghc-internal:GHC.Internal.List
  !!, called at <interactive>:29:22 in interactive:Ghci20


--- Instead, we'll use the safe (!?), which returns a Maybe Char but never crashes: 

ghci> ['a', 'b', 'c', 'd'] !? 4
Nothing

ghci> ['a', 'b', 'c', 'd'] !? 0
Just 'a'

--- Now let's get the next list element after the matching one:

ghci> elemIndex 'c' ['a', 'b', 'c', 'd'] >>=  return . (+1) 
Just 3

ghci> elemIndex 'c' ['a', 'b', 'c', 'd'] >>=  return . (+1) >>= \i -> ['a', 'b', 'c', 'd'] !? i  
Just 'd'

--- Even simpler, due to partial application:

ghci> elemIndex 'c' ['a', 'b', 'c', 'd'] >>=  return . (+1) >>= (['a', 'b', 'c', 'd'] !? )
Just 'd'

ghci> elemIndex 'a' ['a', 'b', 'c', 'd'] >>=  return . (+1) >>= (['a', 'b', 'c', 'd'] !? )
Just 'b'

ghci> elemIndex 'd' ['a', 'b', 'c', 'd'] >>=  return . (+1) >>= (['a', 'b', 'c', 'd'] !? )
Nothing

----- to be continued -------