Lecture 7: Elementary Haskell I
--------------------------------
(contributor: Adam Shaw)

Welcome to the introductory Haskell lecture.

I refrain from presenting "Hello World" in Haskell as it is an
advanced topic.

A general comparison of Haskell and ML.
---------------------------------------

Points of similarity between ML (SML in particular) and Haskell

1. both have first-class functions (functions are values)

2. both are statically typed

3. both have polymorphic types

4. both have algebraic datatypes (& pattern matching)

5. both have automatic type inference (based on Hindley-Milner)

6. both have "layered patterns" ("as" in ML, "@" in Haskell)

7. both support a fairly conventional set of basic types
   integers, reals, booleans, strings

8. both have lists as a basic and heavily used type
   (even more privileged in Haskell)

Differences between ML and Haskell

1. Haskell is pure, without side effects or exceptions,
   while ML has mutable data structures (refs and arrays)
   and exceptions (control effects)

2. Haskell has lazy evaluation (a variant of call-by-name
   evaluation with memoization), while ML has strict
   evaluation. (ML can implement forms of lazy evaluation
   though libraries, but there is no special syntactic
   support for it.)

3. Haskell has even more special notational support for
   lists -- list comprehensions.

4. Haskell has boolean guards associated with pattern
   matching

5. Haskell functions are usually curried, while SML functions
   use tuple or record arguments for multi-argument functions

6. Haskell has type classes to support abstraction over
   types with associated interfaces.

7. ML uses modules and functors to support types with
   associated interfaces and abstraction over such.

8. Haskell uses monads to simulate imperative, effectful
   programming (e.g. assignable variables and I/O).
   ML does not need to simulate imperative programming
   since it supports it directly.

Syntactically, there are similarities between Haskell and
ML, but they differ in style.  Haskell has a minimal, 
calculator-style syntax.  ML syntax is heavier, but probably
more readable, particularly for larger bodies of code.

-----------------------------------------------------------------

Practical issues:

1. installing ghc and ghci (Haskell Platform)

-----------------------------------------------------------------

Consider the differences between ML and Haskell in three broad
categories:
- superficial syntactic differences,
- fancy extra syntax on Haskell's part, and
- deep semantic differences with far-reaching implications.

Today's lecture is concerned with the first two. Time permitting,
we'll get into the juicy third category.

Category 1 -- superficial differences in syntax:

thing		ML			Haskell

types		int			Int
		'a tree			Tree a
		'a list			[a]
		'a * 'b			(a,b)

type ascr.	x : int			x :: Int

cons 		x :: xs			x : xs

list append	xs @ ys			xs ++ ys

fun. comp.	f o g			f . g

anon. fn.	fn x => x		\ x -> x

val   		val n = 1		n = 1

fun		fun f x = x		f x = x

fun type	ML
ascription	fun f (b:bool) : int = if b then 1 else 0

		Haskell
		f :: Bool -> Int
		f b = if b then 1 else 0

case	    	case xs	   	        case xs of
		  of []   => 0	          []  -> 0
                   | h::_ => h            h:_ -> h

let		let val x = 1		let x = 1
                    val y = 2       	    y = 2
                in              	in
                  (x+y, x-y)      	  (x+y, x-y)
                end

type syn.	type 'a pr = 'a * 'a	type Pr a = (a,a)

datatype	datatype color          data color = R | G | B
                  = R | G | B 	  	

		ML
		datatype 'a tree
		  = Lf
                  | Nd of 'a * 'a tree * 'a tree	   

		Haskell
		data Tree a
		  = Lf
                  | Nd a (Tree a) (Tree a)

comments	  (* comm *)   	  	-- comm to EOL
		     	  		{- multiline comm -}

ALSO in Haskell, String means [Char], really.

ALSO the fact that functions are usu. curried affects interfaces, i.e.,

foldr in ML is ('a * 'b -> 'b) -> 'b -> 'a list -> 'b

in Haskell is (a -> b -> b) -> b -> [a] -> b

Note also that in Haskell, foldl and foldr have different polymorphic 
types (whereas in SML they have the same type):

Prelude> :t foldl
foldl :: (a -> b -> a) -> a -> [b] -> a
Prelude> :t foldr
foldr :: (a -> b -> b) -> b -> [a] -> b

Why is this?

   foldl f b [x,y,z] ==> f (f (f b x) y) z     (f :: b -> e -> b) 
   foldr f b [x,y,z] ==> f x (f y (f z b))     (f :: e -> b -> b)

while in SML:

   foldl f b [x,y,z] ==> f(x, f(y, f(z,b)))    (f : 'e * 'b -> 'b)
   foldr f b [x,y,z] ==> f(z, f(y, f(x,b)))    (f : 'e * 'b -> 'b)

-----------------------------------------------------------------------
Category 2 -- Haskell syntactic bonuses:

enumeration notation
  [1..10]
  [1,4..20]
  [10,9..0]

In ML, we can generate such integer ranges using a function:

fun range (init: int, incr: int, final: int) = 
    if incr < 0
    then if init < final then []
         else init :: range(init+incr, incr, final)
    else if init > final then []
         else init :: range(init+incr, incr, final);

val r1 = range(1,1,10);
val r2 = range(1,3,20);
val r3 = range(10,~1,0);

A different function would have to be used for similar
sequences of reals.


Haskell also permits open-ended (infinite) enumeration
expressions:

  [1..]  -- all positive integers [1,2,3,4,5,...]

  [1, 3 .. ]  -- all odd integers [1,3,5,7,...]