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

// :i looks up useful information about the type and syntax of a function
//    (+) is a handy name for the function + . Without the parens rules
//    of infix syntax would apply: "infixl 6 +", i.e., associates to the left,
//    "1+2+3" is "(1+2)+3". Infix + has precedence 6. 

ghci> :i (+)
type Num :: * -> Constraint
class Num a where
  (+) :: a -> a -> a
  ...
  	-- Defined in ‘GHC.Internal.Num’
infixl 6 +

ghci> 1+2
3

ghci> (+) 1 2
3

// Note the currying: (+) 1 2  is  ((+) 1) 2, a partial function \x -> x+1  applied to 2. 

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

ghci> (\x->x+1) 2
3

// Note the type of (+). It's a parametric type expression, with a type variable a .
//
//  Think of this as a lambda calculus expression, which can be rewritten with
//  another variable. Say,  a -> a -> a  is the same as  b -> b -> b, etc.
//  The important thing is that  a  is in the typeclass Num, due to being used in (+).  

ghci> :t "foo"
"foo" :: String

// Predictably, a type error: here a is String, but there is no (+) defined for Num String 

ghci> (+) "foo" 4
<interactive>:5:1: error: [GHC-39999]
    • No instance for ‘Num String’ arising from a use of ‘+’
    • In the expression: (+) "foo" 4
      In an equation for ‘it’: it = (+) "foo" 4

// This polymorphism allows (+) to work on many types that define (+), floats and
//   integers in particular:

ghci> (+) 1.0 2.0
3.0

ghci> (+) 1 3
4

ghci> (+) 3 2.0
5.0

// The same inference happens with constants:

ghci> :t 5
5 :: Num a => a

// The same happens with lists and any other types. They all go through type inference:

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

// Note that [] has no restrictions on the type variable:

ghci> :t []
[] :: [a]

// We can ask what functions (operators) a class type supports:

ghci> :i Num
type Num :: * -> Constraint
class Num a where
  (+) :: a -> a -> a
  (-) :: a -> a -> a
  (*) :: a -> a -> a
  negate :: a -> a
  abs :: a -> a
  signum :: a -> a
  fromInteger :: Integer -> a
  {-# MINIMAL (+), (*), abs, signum, fromInteger, (negate | (-)) #-}
  	-- Defined in ‘GHC.Internal.Num’
instance Num Double -- Defined in ‘GHC.Internal.Float’
instance Num Float -- Defined in ‘GHC.Internal.Float’
instance Num Int -- Defined in ‘GHC.Internal.Num’
instance Num Integer -- Defined in ‘GHC.Internal.Num’
instance Num Word -- Defined in ‘GHC.Internal.Num’

// For example, the type Int is in the class type Num:

ghci> :i Int
type Int :: *
data Int = GHC.Types.I# GHC.Prim.Int#
  	-- Defined in ‘GHC.Types’
instance Bounded Int -- Defined in ‘GHC.Internal.Enum’
instance Read Int -- Defined in ‘GHC.Internal.Read’
instance Enum Int -- Defined in ‘GHC.Internal.Enum’
instance Integral Int -- Defined in ‘GHC.Internal.Real’
instance Num Int -- Defined in ‘GHC.Internal.Num’      // <<------
instance Real Int -- Defined in ‘GHC.Internal.Real’
instance Show Int -- Defined in ‘GHC.Internal.Show’
instance Eq Int -- Defined in ‘GHC.Classes’            // <--- Int is also in Eq
instance Ord Int -- Defined in ‘GHC.Classes’

ghci> :i Eq
type Eq :: * -> Constraint
class Eq a where
  (==) :: a -> a -> Bool     // <-- equality ==
  (/=) :: a -> a -> Bool
  {-# MINIMAL (==) | (/=) #-}
  	-- Defined in ‘GHC.Classes’
instance Eq Integer -- Defined in ‘GHC.Num.Integer’
instance (Eq a, Eq b) => Eq (Either a b)
  -- Defined in ‘GHC.Internal.Data.Either’
instance [safe] Eq a => Eq (Maybe a)
  -- Defined in ‘GHC.Internal.Maybe’
instance Eq Bool -- Defined in ‘GHC.Classes’
instance Eq Char -- Defined in ‘GHC.Classes’
instance Eq Double -- Defined in ‘GHC.Classes’
instance Eq Float -- Defined in ‘GHC.Classes’
instance Eq Int -- Defined in ‘GHC.Classes’
instance Eq a => Eq [a] -- Defined in ‘GHC.Classes’
instance Eq Ordering -- Defined in ‘GHC.Classes’
instance Eq a => Eq (Solo a) -- Defined in ‘GHC.Classes’
// skipped 

ghci> :i (==)
type Eq :: * -> Constraint
class Eq a where
  (==) :: a -> a -> Bool
  ...
  	-- Defined in ‘GHC.Classes’
infix 4 ==           // <--- note that infix == binds weaker that + and doesn't associate

ghci> 3 == 4
False

ghci> 3+1 == 4       // same as (3+1)==4
True

ghci> 3 == 4 == 5
<interactive>:97:1: error: [GHC-88747]
    Precedence parsing error
        cannot mix ‘==’ [infix 4] and ‘==’ [infix 4] in the same infix expression

// == curries as a function of two arguments:

ghci> :t (==) 2                          // a function of one argument now:
(==) 2 :: (Eq a, Num a) => a -> Bool  

ghci> let is2 x = (==) 2 x               // just like this one

ghci> is2 2
True

ghci> is2 3
False

ghci> :t is2
is2 :: (Eq a, Num a) => a -> Bool

ghci> :t 3.0
3.0 :: Fractional a => a

ghci> :i Fractional 
type Fractional :: * -> Constraint
class Num a => Fractional a where
  (/) :: a -> a -> a
  recip :: a -> a
  fromRational :: Rational -> a
  {-# MINIMAL fromRational, (recip | (/)) #-}
  	-- Defined in ‘GHC.Internal.Real’
instance Fractional Double -- Defined in ‘GHC.Internal.Float’
instance Fractional Float -- Defined in ‘GHC.Internal.Float’

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

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

// The above is _exactly_ the same as ...

ghci> 1 : ( 2 : ( 3 : [] )))             // oops, typo:
<interactive>:23:22: error: [GHC-58481]
    parse error on input ‘)’

// ...that:

ghci> 1 : ( 2 : ( 3 : [] ))         
[1,2,3]

ghci> :i (:)
type List :: * -> *
data List a = ... | a : [a]
  	-- Defined in ‘GHC.Types’
infixr 5 :

// Note that  :  associates to the right as an infix operator, so we can write: 

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

ghci> :i (+)
type Num :: * -> Constraint
class Num a where
  (+) :: a -> a -> a
  ...
  	-- Defined in ‘GHC.Internal.Num’
infixl 6 +

// OK, we can check how + binds stronger that : 

// Oops, a type error. What am I going wrong?

ghci> 2+3 : 4 : 5
<interactive>:28:1: error: [GHC-39999]
    • No instance for ‘Num [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


ghci> 2+3 : 4 
<interactive>:29:1: error: [GHC-39999]
    • No instance for ‘Num [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


ghci> (2+3) : 4 
<interactive>:30:1: error: [GHC-39999]
    • No instance for ‘Num [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

ghci> 5 : 4
<interactive>:99:1: error: [GHC-39999]
    • No instance for ‘Num [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

// Why oh why? It's the same error.

// it's simple: (:) expects a list as its second argument, not 4 ! We forgot [],
//   the only way to make a list

ghci> 2+3 : 4 : 5 : []
[5,4,5]

ghci> (:) 1 []
[1]

ghci> (:) 2 ((:) 1 [])
[2,1]

ghci> :i (:)
type List :: * -> *
data List a = ... | a : [a]
  	-- Defined in ‘GHC.Types’
infixr 5 :

// See if you understand what goes wrong here:

ghci> (:) 2 (:) 1 []
<interactive>:35:1: error: [GHC-83865]
    • Couldn't match expected type: t0 -> [a0] -> t
                  with actual type: [a2]
    • The function ‘(:)’ is applied to four visible arguments,
        but its type ‘a -> [a] -> [a]’ has only two
      In the expression: (:) 2 (:) 1 []
      In an equation for ‘it’: it = (:) 2 (:) 1 []
    • Relevant bindings include it :: t (bound at <interactive>:35:1)

<interactive>:35:7: error: [GHC-83865]
    • Couldn't match expected type: [a2]
                  with actual type: a1 -> [a1] -> [a1]
    • Probable cause: ‘(:)’ is applied to too few arguments
      In the second argument of ‘(:)’, namely ‘(:)’
      In the expression: (:) 2 (:) 1 []
      In an equation for ‘it’: it = (:) 2 (:) 1 []

// "(:) 2 (:)"  associates to the left, so it's  ((:) 2) (:) .
//   The partially applied function "(:) 2" expects a list but gets a function, (:)

ghci> (:) 2 (:)
<interactive>:38:7: error: [GHC-83865]
    • Couldn't match expected type: [a]
                  with actual type: a0 -> [a0] -> [a0]
    • Probable cause: ‘(:)’ is applied to too few arguments
      In the second argument of ‘(:)’, namely ‘(:)’
      In the expression: (:) 2 (:)
      In an equation for ‘it’: it = (:) 2 (:)
    • Relevant bindings include it :: [a] (bound at <interactive>:38:1)

// This works:

ghci> (:) 2 ((:) 1 [])
[2,1]

ghci> :t (:) 2 
(:) 2 :: Num a => [a] -> [a]

ghci> :t (:)
(:) :: a -> [a] -> [a]

ghci> (:) 1 []
[1]

ghci> (:) "foo" []     // note the polymorphism
["foo"]

ghci> (:) "foo" ["bar"]
["foo","bar"]

ghci> (:) "foo" ( "bar" : [] )
["foo","bar"]

// Note how inference works on a -> [a] -> [a] --- when the first argument is a
//   list, the second and the return type must be lists of lists (of Nums) 

ghci> :t (:) [1,2] 
(:) [1,2] :: Num a => [[a]] -> [[a]]

ghci> :t (:) [1,2] []
(:) [1,2] [] :: Num a => [[a]]

ghci> (:) [1,2] []
[[1,2]]

// Fails to typecheck

ghci> (:) [1,2] [4,5]
<interactive>:47:1: error: [GHC-39999]
    • No instance for ‘Num [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

// This works:

ghci> (:) [1,2] [[4,5]]
[[1,2],[4,5]]

ghci> (:) [1,2] [[4,5,6]]
[[1,2],[4,5,6]]

// Let's see type inference work on the polymorphic function for list length:

// Let's define the base case:

ghci> let myLen [] = 0

// It already works:

ghci> myLen []
0

// The inductive step is not ready:

ghci> myLen [1]
*** Exception: <interactive>:50:5-16: Non-exhaustive patterns in function myLen


HasCallStack backtrace:
  collectBacktraces, called at libraries/ghc-internal/src/GHC/Internal/Exception.hs:169:13 in ghc-internal:GHC.Internal.Exception
  toExceptionWithBacktrace, called at libraries/ghc-internal/src/GHC/Internal/Exception.hs:89:42 in ghc-internal:GHC.Internal.Exception
  throw, called at libraries/ghc-internal/src/GHC/Internal/Control/Exception/Base.hs:434:30 in ghc-internal:GHC.Internal.Control.Exception.Base

// Syntax error here: 

ghci> let myLen x:xs = 1 + myLen xs
<interactive>:53:5: error: [GHC-07626]
    Parse error in pattern: myLen

//  Function application binds the strongest (priority 10), so the parser sees the above as
//     let (myLen x):xs = 1 + myLen xs
//         ^^^^^^^^^

ghci> let myLen (x:xs) = 1 + myLen xs

ghci> myLen []
*** Exception: <interactive>:55:5-31: Non-exhaustive patterns in function myLen


HasCallStack backtrace:
  collectBacktraces, called at libraries/ghc-internal/src/GHC/Internal/Exception.hs:169:13 in ghc-internal:GHC.Internal.Exception
  toExceptionWithBacktrace, called at libraries/ghc-internal/src/GHC/Internal/Exception.hs:89:42 in ghc-internal:GHC.Internal.Exception
  throw, called at libraries/ghc-internal/src/GHC/Internal/Control/Exception/Base.hs:434:30 in ghc-internal:GHC.Internal.Control.Exception.Base


ghci> myLen [1]
*** Exception: <interactive>:55:5-31: Non-exhaustive patterns in function myLen


HasCallStack backtrace:
  collectBacktraces, called at libraries/ghc-internal/src/GHC/Internal/Exception.hs:169:13 in ghc-internal:GHC.Internal.Exception
  toExceptionWithBacktrace, called at libraries/ghc-internal/src/GHC/Internal/Exception.hs:89:42 in ghc-internal:GHC.Internal.Exception
  throw, called at libraries/ghc-internal/src/GHC/Internal/Control/Exception/Base.hs:434:30 in ghc-internal:GHC.Internal.Control.Exception.Base

// Oh no, we blew away the base case! We need a multi-line definition:

ghci> :set +m

ghci> let myLen [] = 0
ghci|     myLen (x:xs) = 1 + myLen xs
ghci| 

ghci> let myLen [] = 0
ghci|     myLen (x:xs) = 1 + myLen xs
ghci| 

ghci> myLen [1]
1

ghci> myLen [1,234,5]
3

ghci> myLen []
0

// Note the inferred type, it has two independent type parameters, a and t

ghci> :t myLen
myLen :: Num t => [a] -> t

// It all works now!

// Folds are core to Haskell's library definitions. Haskell's Prelude
//   defined foldl and foldr as Common Lisp's REDUCE with :INITIAL-VALUE for both
//   as the default form of the fold, and :FROM-END for the right fold. 
// Note that the folds without the explicitly supplied initial value are
//   called foldl1 and foldr1 and produce an error when passed an empty list [].

// Look for their definitions in https://www.haskell.org/onlinereport/standard-prelude.html
//   These are really illuminating to learn good Haskell style.

// Specifically, study the definitions of Section 8.1, PreludeList.
//  For the first reading, skip scanl, stop at scanr

ghci> :t foldr
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b

ghci> :t foldl
foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b

// Foldable is the typeclass that includes List, fixed-length tuples, and other
//  collection types that can generally be converted to List, iterated over,
//  filtered for elements matching a test, and other things we use collection types for.

ghci> :i Foldable
type Foldable :: (* -> *) -> Constraint
class Foldable t where
  GHC.Internal.Data.Foldable.fold :: Monoid m => t m -> m
  foldMap :: Monoid m => (a -> m) -> t a -> m
  GHC.Internal.Data.Foldable.foldMap' :: Monoid m =>
                                         (a -> m) -> t a -> m
  foldr :: (a -> b -> b) -> b -> t a -> b
  GHC.Internal.Data.Foldable.foldr' :: (a -> b -> b) -> b -> t a -> b
  foldl :: (b -> a -> b) -> b -> t a -> b
  foldl' :: (b -> a -> b) -> b -> t a -> b
  foldr1 :: (a -> a -> a) -> t a -> a
  foldl1 :: (a -> a -> a) -> t a -> a
  GHC.Internal.Data.Foldable.toList :: t a -> [a]
  null :: t a -> Bool
  length :: t a -> Int
  elem :: Eq a => a -> t a -> Bool
  maximum :: Ord a => t a -> a
  minimum :: Ord a => t a -> a
  sum :: Num a => t a -> a
  product :: Num a => t a -> a
  {-# MINIMAL foldMap | foldr #-}
  	-- Defined in ‘GHC.Internal.Data.Foldable’
instance Foldable (Either a)
  -- Defined in ‘GHC.Internal.Data.Foldable’
instance Foldable [] -- Defined in ‘GHC.Internal.Data.Foldable’
instance Foldable Maybe -- Defined in ‘GHC.Internal.Data.Foldable’
instance Foldable Solo -- Defined in ‘GHC.Internal.Data.Foldable’
instance Foldable ((,) a)
  -- Defined in ‘GHC.Internal.Data.Foldable’

// Let's define Filter a.k.a. GREP

ghci> let myFilter p xs = foldr step [] xs where step x ys = if p x then x : ys else ys
ghci| 

ghci> :t even
even :: Integral a => a -> Bool

ghci> even 2
True

ghci> even 3
False

ghci> myFilter even [1,2,3,4,5]
[2,4]

ghci> myFilter even [1,2,3,4,5,6]
[2,4,6]

ghci> :t myFilter
myFilter :: Foldable t => (a -> Bool) -> t a -> [a]

// This explains the type of foldr: 

ghci> :t foldr
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b
                       ^^^^^^^^^^^^^    ^    ^^^    ^--return type
                        function to     |    collection of a, such as [a] 
			iterate over    initial-value
			the list

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

// We can do map the same way

ghci> :i sq         // <-- before we define the square function, let's see if there's one 
<interactive>:1:1: error: [GHC-76037]
    Not in scope: ‘sq’


ghci> let sq x = x*x
ghci| 

ghci> sq 5
25

ghci> myMap f xs = foldr step [] xs where step x ys = f x : ys
ghci| 

ghci> :t myMap sq 
myMap sq :: (Foldable t, Num a2) => t a2 -> [a2]

ghci> myMap sq  [1,2,3,4,5]
[1,4,9,16,25]

/// Suggested exercise: 
///   Do length, sum, maximum, and minimum -- foldl is the natural for these.