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

//   
// Let's start with reading an older Prelude to pick up Haskell style
//  of writing and thinking. This prelude version is a 1998 classic:
//     https://www.haskell.org/onlinereport/standard-prelude.html

// Note that parts marked "..." are implemented internally, i.e., not in
//   Haskell. Still, there is plenty of idiomatic Haskell code to read and
//   understand!

// Start looking with PreludeList, section 8.1.
//  We looked at map, (++), filter, concat, and concatMap. 
//   Keep looking through drop and splitAt. Make sure you read and understand the types! 

// Length is implemented naively recursively, but it could be implemented via a left fold:

ghci> let mylen xs = foldl (\z x -> z+1) 0 xs

// More idiomatic: let mylen xs = foldl (\z _ -> z+1) 0 xs

ghci> mylen []
0

ghci> mylen [1,2,4]
3

ghci> mylen [1,2,4,7]
4

ghci> mylen [1..10]
10

ghci> :i foldl
type Foldable :: (* -> *) -> Constraint
class Foldable t where
  ...
  foldl :: (b -> a -> b) -> b -> t a -> b
  ...
  	-- Defined in ‘GHC.Internal.Data.Foldable’

ghci> :i foldl1
type Foldable :: (* -> *) -> Constraint
class Foldable t where
  ...
  foldl1 :: (a -> a -> a) -> t a -> a
  ...
  	-- Defined in ‘GHC.Internal.Data.Foldable’

----------- begin quote from Prelude --------------
-- Map and append

map :: (a -> b) -> [a] -> [b]
map f []     = []
map f (x:xs) = f x : map f xs


(++) :: [a] -> [a] -> [a]
[]     ++ ys = ys
(x:xs) ++ ys = x : (xs ++ ys)


filter :: (a -> Bool) -> [a] -> [a]
filter p []                 = []
filter p (x:xs) | p x       = x : filter p xs
                | otherwise = filter p xs


concat :: [[a]] -> [a]
concat xss = foldr (++) [] xss


concatMap :: (a -> [b]) -> [a] -> [b]
concatMap f = concat . map f
----------- end quote from Prelude --------------

// Whats does concat do? Look at the type! The type is often all you need to guess. 

ghci> concat [[1,2], [3,4], [5,6,7]] 
[1,2,3,4,5,6,7]

// . and $ are an interesting pair. (.) has precedence 9, ($) precedence 0.
//   (.) is used to chain function applications:
//      f . g =  \ x -> f (g x)

// So f makes b out of a, and f makes c out of b. Their composition makes c out of a
//  (going through b):

ghci> :t (.)
(.) :: (b -> c) -> (a -> b) -> a -> c

// An aside: what is the type of the following:

ghci> :t \f g x -> f g x 
\f g x -> f g x :: (t1 -> t2 -> t3) -> t1 -> t2 -> t3

// Here is roughly how the type inference works:
//    Let's say x has type t2.
//    (f g) applies to x, so (f g)'s type should be  t2 -> t3  for some t3 
//    Let's say g has some time t1 
//    f applies to g, so f's type must be  t1 -> a  for some a, and (f g)'s type is then  a 
//      unifying with (f g)'s type,  a  must be  t2 -> t3
//    So  f  has the type  t1 -> t2 -> t3  . Nothing further can be unified.

// Note that f's type can be interpreted as "takes a t1, makes a function that takes t2 to t3".
//  This is the familiar currying/partial application. For examples, when (+) gets
//    partially applied to its first argument, it makes functions that take a number
//    to a number (specifically, add that argument). 

ghci> :t (+)
(+) :: Num a => a -> a -> a

ghci> :t (+) 1 
(+) 1 :: Num a => a -> a

ghci> let sq x = x*x

ghci> :i neg
<interactive>:1:1: error: [GHC-76037]
    Not in scope: ‘neg’

ghci> let neg x = -x

ghci> sq 2
4

ghci> sq (neg 2)
4

// . has precedence 9, $ has precedence 0. So  sq . neg $ 2  is  ((.) sq neg) 2   

ghci> sq . neg $ 2
4

ghci> neg . sq $ 2
-4

//  An aside: How does "sq neg 2", i.e., (sq neg) 2 fails to typecheck?

ghci> sq neg 2
<interactive>:17:1: error: [GHC-39999]
    • No instance for ‘Num (Integer -> Integer)’
        arising from a use of ‘it’
        (maybe you haven't applied a function to enough arguments?)
    • In the first argument of ‘print’, namely ‘it’
      In a stmt of an interactive GHCi command: print it

//  OK, (sq neg) applies to "2", resulting in the constraint "Num a" .
/      So (sq neg) must have the type  a -> b  for some b
//   sq has type a' -> a'  and applies to neg. neg has type a'' -> a''
//     So a' is (a'' -> a'') , (sq neg)'s is  (a'' -> a'') -> (a'' -> a'')
//     and both  a  and  b  unify with  (a'' -> a'').
//   So the constraint Num (a'' -> a'')  must apply. Unifying with 2, we
//     see that, in order to typecheck, "Num (Integer -> Integer)" must exist.
//     But it doesn't, hence type check failure.
//
//     You probably wonder, where did that Integer come from? According to
//       https://www.haskellforall.com/2014/10/how-to-desugar-haskell-code.html,
//      
//      """Integer literals are polymorphic by default and desugar to a call to
//         fromIntegral on a concrete Integer:
//
//           1 :: Num a => a
//
//         -- desugars to:
//         fromInteger (1 :: Integer)"""
//

ghci> :t 2
2 :: Num a => a

ghci> :t sq
sq :: Num a => a -> a

// Another unintended syntactic screw-up, another type check issue:

ghci> neg . sq 2
<interactive>:22: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

// But wait, the expression was created, it only failed to print, as it's
//  missing the function for doing so:

ghci> :t neg . sq 2
neg . sq 2 :: (Num c, Num (a -> c)) => a -> c

// So this is neg applying to (sq 2), i.e.  neg . 4

// What is neg . 4 ? It's \x -> neg (4 x)  Its type is then  a -> b  where
//   b is the type of  neg (4 x) . Neg's is Num a' => a' -> a', so b unifies with a'
//   a' unifies with whatever the type of (4 x) is. Now, what could be the type of (4 x)?

// Well, 4 applies to x, so the type of "4" must be, mechanically, some  t1 -> t2 .
//  At the same time, 4 is a "Num a". So we get the constraint Num (t1 -> t2).
//  This seems to type-check but falls apart at the next step, e.g., if we apply
//   it to some number, like 3:

ghci> ( neg . sq 2 ) 3
<interactive>:24:1: error: [GHC-39999]
    • Could not deduce ‘Num a0’
      from the context: (Num c, Num a, Num (a -> c))
        bound by the inferred type for ‘it’:
                   forall {c} {a}. (Num c, Num a, Num (a -> c)) => c
        at <interactive>:24:1-16
      The type variable ‘a0’ is ambiguous
      Potentially matching instances:
        instance Num Integer -- Defined in ‘GHC.Internal.Num’
        instance Num Double -- Defined in ‘GHC.Internal.Float’
        ...plus three others
        ...plus two instances involving out-of-scope types
        (use -fprint-potential-instances to see them all)
    • In the ambiguity check for the inferred type for ‘it’
      To defer the ambiguity check to use sites, enable AllowAmbiguousTypes
      When checking the inferred type
        it :: forall {c} {a}. (Num c, Num a, Num (a -> c)) => c

// Let's make concatMap do something:

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

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

// Why bother with a function like (\x -> [x*x]) ? We'll see it soon!

-------------------------- Our first Monad! -------------------------- 

// We will need a function that is not in the Prelude. This function
//  takes a value and a list, and returns an index at which the value occurs
//  in this list. It is called elemIndex .

// BUT: What should this function do if the value is _not_ in the list?
//   We can quit the program with an error, but what if we don't want to quit,
//    but rather return and handle this condition? Is so, what should we return?
//
//   In LISP we can return 'nil' but in Haskell the type of the return value
//    must be explicitly specified, not ad hoc.
//    We could return a nonsense value such as "-1", but what if we then want 
//     to do arithmetic with the answer, e.g., increment it? Handling the special
//     integer like "-1" may be a source of bugs.
// 
//   Java and C++ offer exceptions, but we want to stay within our clean type system
//     without side effects, not jump somewhere and restore some good state. We really
//     don't want any state at all!
//     
// To do this cleanly, the "Maybe a" type was invented. It has a special value Nothing
//   for the failed cases and the normal value wrapped in a special constructor that
//   can be pattern-matched on: 
//

//  data  Maybe a  =  Nothing | Just a      

ghci> import Data.List

//  elemIndex returns a Maybe Int. All functions that consume this type will pattern-match
//    on Nothing or Just 

// Note: I am not very happy about the name "Just", but we need to pattern-match on
//   something. This is historical notation, just like 'lambda', etc.

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

ghci> elemIndex 2 [1,2,3]
Just 1

ghci> elemIndex 1 [1,2,3]
Just 0

ghci> elemIndex 3 [1,2,3]
Just 2

ghci> elemIndex 4 [1,2,3]
Nothing

// The great thing about this "Maybe a" type is that it comes with a few very
//   simple functions that allow us to write no new code to handle the special
//   case of Nothing. But first we are going to do it the hard way. 

ghci> :set +m

// Here's an increment function that passes Nothing through and increments actual indices:

ghci> let inc1 Nothing = Nothing
ghci|     inc1 (Just x) = Just (x+1)
ghci| 

ghci> inc1 Nothing
Nothing

ghci> inc1 (Just 1)
Just 2

ghci> inc1 (elemIndex 4 [1,2,3])
Nothing

ghci> inc1 (elemIndex 2 [1,2,3])
Just 2

// We can write this in a more pipelined way with (.)

ghci> inc1 . elemIndex 2 $ [1,2,3]
Just 2

ghci> inc1 . inc1 . elemIndex 2 $ [1,2,3]
Just 3

ghci> inc1 . inc1 . inc1 . elemIndex 2 $ [1,2,3]
Just 4

ghci> inc1 . inc1 . inc1 . elemIndex 5 $ [1,2,3]
Nothing

// But this is counter-intuitive, the pipeline grows the wrong way. So there is
//  a very useful chaining operator >>=   (with a convenient infixl 1 weak precedence)
//  that feeds the normal value through and includes an automatic case for Nothing: 

// instance  Monad Maybe  where
//     (Just x) >>= k   =  k x
//     Nothing  >>= k   =  Nothing
//     return           =  Just
//     fail s           =  Nothing

ghci> elemIndex 5 [1,2,3] >>= \x -> Just (x+1) 
Nothing

ghci> elemIndex 2 [1,2,3] >>= \x -> Just (x+1) 
Just 2

// "return" arguably looks better, although it has no relation to stack-based RET, C's return, etc.

ghci> elemIndex 2 [1,2,3] >>= \x -> return (x+1) 
Just 2

// Notice that the pipelined lambdas treat the case of the normal value, Nothing gets
//   passed along automatically:

ghci> elemIndex 2 [1,2,3] >>= \x -> return (x+1) >>= \x -> return (x*x)
Just 4

ghci> elemIndex 2 [1,2,3] >>= \x -> return (x+1) >>= \x -> return (x*x)
Just 4

ghci> elemIndex 100 [1,2,3] >>= \x -> return (x+1) >>= \x -> return (x*x)
Nothing

// We can keep adding more functions that work on the returned index (and pass Nothing),
//    using the >>=  syntax and the Maybe Int type.

// But there's more! Writing "return" or "Just" every time is annoying. Instead,
//   we can define a function that takes what we want to do with an Int and
//   makes the function that does it with Maybe Int, while passing Nothing through:

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

// We'll talk next time	why it's called	a 'Functor'. For now think of it as
//   a factory of functions that makes functions on the newly defined type Maybe Int
//   from the functions we have on Ints.

// So: fmap takes the (+) 1 function on Ints and makes a function on Maybe Ints!

ghci> fmap ((+) 1)  .  elemIndex 100 $ [1,2,3]
Nothing

ghci> fmap ((+) 1)  .  elemIndex 2 $ [1,2,3]
Just 2

// Note	that type inference just works!	

// For another example of a Monad consider taking the element at an index:

ghci> :t (!!)
(!!) :: GHC.Internal.Stack.Types.HasCallStack => [a] -> Int -> a

ghci> [1,2,3]!!1
2

ghci> [1,2,3]!!2
3

// See definition of (!!) in the Prelude. It explicitly produces errors
//   for negative or too large indices:

// (!!)                :: [a] -> Int -> a
// xs     !! n | n < 0 =  error "Prelude.!!: negative index"
// []     !! _         =  error "Prelude.!!: index too large"
// (x:_)  !! 0         =  x
// (_:xs) !! n         =  xs !! (n-1)

ghci> [1,2,3]!!3
*** Exception: Prelude.!!: index too large

HasCallStack backtrace:
  error, called at libraries/ghc-internal/src/GHC/Internal/List.hs:1695:14 in ghc-internal:GHC.Internal.List
  tooLarge, called at libraries/ghc-internal/src/GHC/Internal/List.hs:1705:50 in ghc-internal:GHC.Internal.List
  !!, called at <interactive>:64:8 in interactive:Ghci41

// But there is a version (!?) that doesn't produce errors but returns Nothing:

ghci> :t (!?)
(!?) :: [a] -> Int -> Maybe a

ghci> [1,2,3]!?1
Just 2

ghci> [1,2,3]!?5
Nothing

// Note its type: [a] -> Int -> Maybe a  . Here  a  refers to the type of the list's elements.