==========================[ Readings ]==========================

Read Chapters 3--6 of "Read World Haskell". You may skim Ch. 5
at a first reading, but try examples from all others at your
GHCI command line (or in Emacs buffer) to follow along!

Read Chapter 6.3 on type inference in the Mitchell textbook.
It covers ML, not Haskell, but the type systems of these 
languages are very close (they both use the type system
called the Hindley-Milner type syste,). The difference is almost entirely syntactic.
For example, in ML type variables come with an apostrophe,
whereas in Haskell they don't need one. A function from 
things of type a to things of type b is written to have type 
('a -> 'b ) in ML, (a -> b) in Haskell.

Just as in Haskell, types in ML are _trees_ (called "well-founded trees").
In pattern-matching, these trees are compared against the trees
for patterns (think ASTs of the pattern expressions, with types at nodes).
The matching is somewhat similar to your HW2 pattern-matching task.

=====================[ In-class transcript ]=====================

$ ghci
GHCi, version 7.8.3: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.

// Recall that : and [] are the Haskell list constructors.
//  They are as fundamental to Haskell lists as CONS and NIL
//  are to LISP's---they are the only an 

Prelude> 1 : 2 : []
[1,2]

// By itself, [] has a type of "list of any single kind of thing t"
//   When used with values of specific types, t will
//    be constrained by whatever types these values have. 

Prelude> :t []
[] :: [t]
Prelude> :set +m

Prelude> :t 1:[]
1:[] :: Num a => [a]

// Looking up if functions are defined, and where.

Prelude> :i sum
sum :: Num a => [a] -> a 	-- Defined in ‘Data.List’
Prelude> :i +
class Num a where
  (+) :: a -> a -> a
  ...
  	-- Defined in ‘GHC.Num’
infixl 6 +

// map has an interesting type: note that the function
//  (a -> b) makes as into bs, and so map takes a
//  list of as into a list of bs. But a and b need
//  not be the same; unification doesn't demand this.

Prelude> :i map
map :: (a -> b) -> [a] -> [b] 	-- Defined in ‘GHC.Base’


// for some reason, multiline input didn't work;
//   note that the second prompt we got wasn't
//   Preline| as should be with multiline.
// Recall that GHCI needs a let for functions defined
//   at the top level (but not in a file that's :load-ed).

Prelude> let mysum [] = 0 
Prelude>     mysum (x:xs) = x + mysum xs
<interactive>:9:18: parse error on input ‘=’

// Fine, let's use the one-liner syntax with ;

Prelude> let mysum [] = 0 ; mysum (x:xs) = x + mysum xs
Prelude| 

// Testing

Prelude> mysum []
0
Prelude> mysum [1,2,3]
6

Prelude> :t mysum
mysum :: Num a => [a] -> a


// Let us now create our own List type.
//  Haskell has a standard one in Data.List, 
//  but ours will be isomorphic to it.

Prelude> :i List

Top level: Not in scope: data constructor ‘List’
Prelude> :i Nil

Top level: Not in scope: data constructor ‘Nil’

// Good, these are not in scope; so define them as we like:

Prelude> data List a = Nil | Cons a (List a)

// This works: our expression typechecks

Prelude> :t Cons 1 (Cons 2 Nil)
Cons 1 (Cons 2 Nil) :: Num a => List a

// ..and type inference works for it just like for built-ins:

Prelude> :t Cons 'a' (Cons 'b' Nil)
Cons 'a' (Cons 'b' Nil) :: List Char

// NOTE that I didn't just create a type---I created a whole family
//      of types, List a, for any type a (a.k.a. "parametrized by a").
// You can do this in C++ and recent Java with templates, but not
//      so gracefully.

// Even though this type-checks, Haskell doesn't know how to print it.
//   GHCI's REPL uses the function 'show', and it argument must belong 
//   to the typeclass Show (just like + means Num).
//  

Prelude> Cons 'a' (Cons 'b' Nil)

<interactive>:28:1:
    No instance for (Show (List Char)) arising from a use of ‘print’
    In a stmt of an interactive GHCi command: print it
Prelude> 
[4]+  Stopped                 ghci

// The definition of show for my List is a bit more complex syntactically
//   than convenient to type at the GHCI prompt, so I switched to Emacs
//   and did M-x shell to start my Bash shell in a buffer, then started
//   GHCI there. 

hs user$ emacs mylist.hs 

// Pasting from Emacs shell 

Prelude> :l "mylist.hs"
[1 of 1] Compiling Main             ( mylist.hs, interpreted )

// We'll ignore this warning for now. It comes from my variant
//  of the tail function.

mylist.hs:16:1: Warning:
    Pattern match(es) are overlapped
    In an equation for ‘tl’: tl (Cons _ Nil) = ...
Ok, modules loaded: Main.

// Now that I defined show for my new type (List a), its objects
//  now print fine with my custom printing function.

*Main> Cons 1 (Cons 2 Nil)
<1 <2 <>>>

// rereading a file is easy from GHCI command line

*Main> :r
[1 of 1] Compiling Main             ( mylist.hs, interpreted )

// I had both the "deriving" in the class declaration, and a 
//  defined instance of Show (List a). They conflicted, hence
//  the error: 

mylist.hs:2:22:
    Overlapping instances for Show (List a)
      arising from the second field of ‘Cons’ (type ‘List a’)
    Matching instances:
      instance Show (List a) -- Defined at mylist.hs:2:22
      instance Show a => Show (List a) -- Defined at mylist.hs:7:10
    When deriving the instance for (Show (List a))
Failed, modules loaded: none.

// Commented 'deriving out', reloading

Prelude> :r
[1 of 1] Compiling Main             ( mylist.hs, interpreted )

mylist.hs:22:1: Warning:
    Pattern match(es) are overlapped
    In an equation for ‘tl’: tl (Cons _ Nil) = ...
Ok, modules loaded: Main.

// GHCI REPL doesn't complain now & uses my show:

*Main> Cons 1 (Cons 2 Nil)
<1 <2 <>>>

// But I still need to write parens when building lists,
//    because without parens Haskell's parser sees
//    a call to Cons with *four* parameters 1, Cons, 2, and Nil, 
//    not what we intended!

*Main> Cons 1 Cons 2 Nil

<interactive>:7:1:
    Couldn't match expected type ‘a2 -> List a3 -> t’
                with actual type ‘List a0’
    Relevant bindings include it :: t (bound at <interactive>:7:1)
    The function ‘Cons’ is applied to four arguments,
    but its type ‘a0 -> List a0 -> List a0’ has only two
    In the expression: Cons 1 Cons 2 Nil
    In an equation for ‘it’: it = Cons 1 Cons 2 Nil

<interactive>:7:8:
    Couldn't match expected type ‘List a0’
                with actual type ‘a1 -> List a1 -> List a1’
    Probable cause: ‘Cons’ is applied to too few arguments
    In the second argument of ‘Cons’, namely ‘Cons’
    In the expression: Cons 1 Cons 2 Nil

// So we want an infix function to build lists without parens, just like : 
//   Let's check what : is: 

*Main> :i :
data [] a = ... | a : [a] 	-- Defined in ‘GHC.Types’
infixr 5 :

data [] a = ... | a : [a] 	-- Defined in ‘GHC.Types’
infixr 5 :

// Note that + associates to the _left_ (infixl) whereas : associates 
//  to the _right_:

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

// So I add a "infixr 5 :" declaration to the file, and
//  now the GHCI parser sees it right:

*Main> :r
[1 of 1] Compiling Main             ( mylist.hs, interpreted )

mylist.hs:3:10: parse error on input ‘cons’
Failed, modules loaded: none.

Prelude> :r
[1 of 1] Compiling Main             ( mylist.hs, interpreted )

mylist.hs:26:1: Warning:
    Pattern match(es) are overlapped
    In an equation for ‘tl’: tl (Cons _ Nil) = ...
Ok, modules loaded: Main.

// Now it works: cons is a function, `cons` is infix right-associative

*Main> cons 1 Nil
<1 <>>
*Main> 1 `cons` Nil
<1 <>>
*Main> 1 
1
*Main> 1 `cons` 2 `cons` Nil
<1 <2 <>>>

// Adding my length function for List:

Prelude> :r
[1 of 1] Compiling Main             ( mylist.hs, interpreted )

mylist.hs:30:1: Warning:
    Pattern match(es) are overlapped
    In an equation for ‘tl’: tl (Cons _ Nil) = ...
Ok, modules loaded: Main.

*Main> len (1 `cons` 2 `cons` Nil)
2

// Alternative syntax with $ 

*Main> len  $ 1 `cons` 2 `cons` Nil
2

*Main> 

//// Lazy evaluation:

GHCi, version 7.8.3: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Prelude> :i cond

Top level: Not in scope: ‘cond’

// Writing my own functional form of IF . In LISP & Scheme,
//   which use eager evaluation of function arguments,
//   such a function cannot exist---it must be a special form. 

// In Haskell, due to lazy evaluation, this can be a normal function,
//   because in Haskell functions only evaluate their arguments
//   if needed, and _don't_ evaluate them otherwise.

// Argh, typo:

Prelude> let cond tst thn els = if tst then tt else els

<interactive>:4:36:
    Not in scope: ‘tt’
    Perhaps you meant ‘tst’ (line 4)

// Now it works. Note that if .. then .. else .. in Haskell
//   forces the expressions after then and after else to have
//   the same type! "if True then 1 else 'a'" won't type-check!

Prelude> let cond tst thn els = if tst then thn else els

Prelude> cond (1>0) 1 (-1)
1

Prelude> cond (1>0) 'a' 'b'
'a'

// error, when evaluated, causes an immediate exception. 
//   So it's evidently _not_ evaluated!

Prelude> cond (1>0) 'a' (error "boom")
'a'

// ..and now it is:

Prelude> cond (1>2) 'a' (error "boom")
*** Exception: boom

// Laziness allows Haskell to define infinite list objects like [1..]
//   (all integers starting from 1)

Prelude> [1..10]
[1,2,3,4,5,6,7,8,9,10]

Prelude> take 2 [1..10]
[1,2]

Prelude> take 2 [1..]
[1,2]

// Finally, a short demo of filter. Note its type: 

Prelude> :i filter
filter :: (a -> Bool) -> [a] -> [a] 	-- Defined in ‘GHC.List’

Prelude> filter (\x -> x > 2) [1,2,3,4]
[3,4]

// With partial application, we don't even need the explicit lambda:

Prelude> :t (>) 2
(>) 2 :: (Ord a, Num a) => a -> Bool

Prelude> filter ((>) 2) [1,2,3,4]
[1]

Prelude> filter ((<=) 2) [1,2,3,4]
[2,3,4]

Prelude> filter ((<) 2) [1,2,3,4]
[3,4]