{- 

HASKELL BASICS
CSE 341, Winter 2009

Instead of the usual Powerpoint slides or web notes, for Haskell, 
the lecture notes can be run!

This stuff is a comment.  (You probably figured that out already.)
Big comments can be delimited by {-   ... stuff ... -}

{- These symbols nest, so this is a comment within a comment ... -}

You can also put a comment on one line, or part of a line: everything on
that line after the -- is a comment.

This file is linked from the 341 website.  To load it into Haskell, save
it under the name HaskellBasics.hs (make sure it doesn't have a .txt extension).
Then load it from within Haskell using 
   :load HaskellBasics.hs

Alternatively, you can double click on the file icon it; or if ghci is on
your path, you can start Haskell from the command line and load the file:
   ghci HaskellBasics.hs

Once in Haskell, just type an expression to evaluate it.  To see the type
of an expression without evaluating it, use this:
   :type expr
or just
   :t expr

Another useful Haskell command is
  :set +t
which causes Haskell to print type information after evaluation.  See the
"Running Haskell" web page or the online manuals for more info.

*********************************

Haskell is an example of a pure functional programming language -- there
are no side effects.

Imperative languages have variables and assignment; they are in effect
abstractions of the von Neumann machine. There is no referential
transparency.

In mathematics, we can substitute equals for equals:
if x=y+z then you can substitute y+z for x 

Informally, in a referentially transparent language you can substitute
equals for equals, just as in mathematics.

Interesting features of Haskell:

    truly functional 
    lazy evaluation -- can deal with infinite structures 
        (semantically the same as call by name)
    type system -- statically typed, no type declarations needed; polymorphic 


Future of functional languages

  Barriers to adoption: 
    efficiency (a declining problem; also functional languages good
              candidates for parallel execution) 
    programmer acceptance (a big problem)
    unnatural for some things, such as interactive I/O 
  Benefits:
    easier to parallelize!
    much cleaner mathematically

Depending on your point of view, I/O in Haskell is either a big problem,
weird, or truly elegant.  Personally I rate it as elegant & weird.

-}

module HaskellBasics
    where

{- SOME BUILT-IN TYPES:
  3 :: Integer
  1.0 :: Double
  'a' :: Char
  True :: Bool
  [1,2,3] :: [Integer]         -- lists
  [1.3,2.8] :: [Double]
  [True,True,True,False] :: [Bool]
  "fred" :: String (which is an alias for [Char]

  [True,3] -- gives a type error ... lists can contain only one type of element

-}

{- To apply a function to arguments just give the function name followed
   by the arguments (no parentheses needed)

sqrt 2
my_member 3 [1,2,3,4,5]
take 4 [2, 3, 5, 7, 11, 13, 17]

Infix operators are functions as well:
3+4

The usual precedence rules apply for operators:
3+4*5
3^2*100

Function application binds more tightly than infix operators:
sqrt 2*10


-}

-- MORE ABOUT LISTS

{-

  [0,5 .. 100 ] -- the list of multiples of 5 between 0 and 100
  [1..] -- the infinite list of positive integers
  [1,3 ..] -- the infinite list of odd positive numbers

: is an infix 'cons' (list constructor) operator.  Example:

  3 : [4,5]

head gets the first element of a list
head [1,2,3]

tail gets the rest of the list
tail [1,2,3]

++ is the infix append operator:

[1,2] ++ [3,4,5]

length finds the length of a list

null tests whether a list is empty
null [1,2,3]
-}

{- STRINGS

strings are just lists of characters (type Char).  Try this:
['y', 'u', 'p']

The show function takes a value and turns it into a string:
show (3+4)
-}

{- PAIRS, TRIPLES, AND TUPLES

A pair is a pair of other values, and is written like this:

(1, 4)

Other examples:
(True, False)
(1, "squid")

Note that the types of the first and second element don't need to be the
same.  (Pairs always have two elements but the first and second element can
be of different types.  Lists can have any number of elements but they must
all have the same type.)

fst is a function to get the first element of a tuple;
snd gets the second.

We can also have triples:
 (1, 0, False)

'tuple' is the most general name -- this has 0 or more elements.  Note that
a tuple with 4 Booleans has a different type from a tuple with 3 Booleans!

But a list of Booleans always has type [Bool]


-}

-- DEFINING A FUNCTION

double :: Integer -> Integer
double x = 2*x

{- Haskell will infer the types of most things, but it's good form to
declare them (gives machine-checkable documentation).  Also the
inferred type might surprise you by being more general than expected.

For now, when we declare types, we will often use more restrictive types
than what Haskell allows.  (We're going to ease into Haskell's rich and
rather complex type system -- more on this later.)  It's always OK to
declare a more restrictive type than the one Haskell will infer, but you
get an error if you try to be more general; or of course if you give the
wrong type.

For 'triple' we haven't declare the type of the triple function.
The inferred type will allow this to work with floats as well as
integers and uses the type class mechanism (to be discussed later).
-}

triple x = 3*x


{- Haskell is case-sensitive ... function names should start with lower
   case, type names and constructors with upper case -}

-- SIMPLE RECURSION EXAMPLES

-- recursive factorial
rec_factorial :: Integer -> Integer
rec_factorial n =
    if n>0
      then n * rec_factorial (n-1)
      else 1

{- here's another version with error checking:

rec_factorial n =
    if n>0
      then n * rec_factorial (n-1)
      else if n==0 
        then 1
        else error "factorial called with n<0"

-}

{- White space is significant in parsing Haskell!
   There's some rule about how tabs are processed, but I avoid them and
   always use spaces. -}

-- factorial using the built-in prod function
-- note that this doesn't check for the case of n<0
factorial :: Integer -> Integer
factorial n = product [1..n]

-- type Integer can have an indefinite number of digits!
-- (confusingly, there is also a type Int that is limited to hardware integers)

-- POLYMORPHIC TYPES (also note use of pattern matching in function def)

my_length        :: [a] -> Integer
my_length []     = 0
my_length (x:xs) = 1 + my_length xs

-- STYLE RECOMMENDATION: watch for opportunities to use pattern matching in
-- function definitions.  This often leads to cleaner definitions than
-- using if expressions.


-- MORE RECURSION EXAMPLES

-- sum the elements in a list (there is also a built-in function 'sum')
rec_sum []     = 0
rec_sum (x:xs) = x + rec_sum xs

-- append two lists (note that this is built-in as the operator ++)
append [] ys     = ys
append (x:xs) ys = x : append xs ys

-- CASE EXPRESSIONS

choose_creature x = 
    case x of 
      0 -> "squid"
      1 -> "octopus"
      2 -> "anemone"
      _ -> "unknown"

-- pattern matching for function definitions is equivalent to using case
-- expressions ... for example:

choose_another_creature 0 = "squid"
choose_another_creature 1 = "octopus"
choose_another_creature 2 = "anemone"
choose_another_creature _ = "unknown"

-- and conversely:

case_append xs ys =
    case xs of
      [] -> ys
      (z:zs) -> z : append zs ys


-- CURRYING!  

plus :: Integer -> Integer -> Integer
plus x y = x+y

-- note that the type of plus is  Integer -> Integer -> Integer, 
-- NOT (Integer , Integer) -> Integer

-- we can apply plus to just one argument (check what the type is of incr)
incr = plus 1

{- HIGHER-ORDER FUNCTIONS

The Haskell library includes a map function.  This applies the function to
each element of a list and returns a list of the results.  Try evaluating 

   map incr [1,2,3]
-}

-- we can also easily define map ourselves:
my_map :: (a -> b) -> [a] -> [b]
my_map f [] = []
my_map f (a:x) = f a : my_map f x

-- try applying my_map to double, factorial, not, etc.

-- the types of the argument list and result list can be different
on_off :: Bool -> Integer
on_off False = 0
on_off True  = 1


-- now try my_map on_off [True,True,False]

-- ANONYMOUS FUNCTIONS

doubletrouble :: Integer -> Integer
doubletrouble = \x -> 2*x

-- try this:
--   my_map (\x -> x+5) [1,2,3]

{- FILTER
Another useful higher-order function is filter:

filter :: (a -> Bool) -> [a] -> [a]
filter Char.isUpper "Oliver Twist" 
filter (\x -> mod x 2 ==0) [1,2,3,4,5,6]

Suppose we want function to filter out the odd elements in a list.

We could write it as:
   evens s = filter (\x -> mod x 2 ==0) s
But a more elegant definition is as follows.  (Why does this work?)
-}

evens = filter (\x -> mod x 2 ==0)



{- STATIC SCOPING 

Illustrated with several versions of calculating the length of the
hypotenuse of a triangle - these all do the same thing) 
-}

hyp x y = 
    let xsq = x*x
        ysq = y*y
        sum = xsq + ysq
    in sqrt sum


hyp2 x y = 
    let sum = xsq + ysq
        xsq = x*x
        ysq = y*y
    in sqrt sum


-- let can be nested
hyp3 x y = 
    let xsq = x*x
        ysq = y*y
    in let sum = xsq + ysq
       in sqrt sum


-- where is another way to produce a local scope 
hyp4 x y =
    sqrt sum
    where sum = x*x + y*y

-- nested declarations shadow outer ones
shadow x =
    let x = 100
    in 2*x

{- Note that 'shadow' always returns 200, since the x in the let expression
   shadows the parameter.  There are additional important things to know about
   scoping and overriding -- we will defer this to Scheme (where exactly the
   same issues arise). -}

{- LIST COMPREHENSIONS -}

-- the list of squares of numbers between 0 and 10
squares100 = [x^2 | x <- [0..10]]

-- the infinite list of squares 
squares = [x^2 | x <- [0..]]


-- quicksort

qsort [] = []
qsort (a:x) = qsort [ b | b <- x, b<=a ] ++ [a] ++ qsort [ b | b <- x, b>a ]


-- all permutations of a list

perms [] = [[]]
perms x  = [ a:y | a <- x, y <- perms (remove a x) ]

remove a [] = []
remove a (x:y) | a==x       = remove a y
               | otherwise  = x : remove a y


{- MORE HIGHER-ORDER FUNCTIONS -}

{- In many cases you can avoid writing a recursive function using
   higher-order functions such as map or foldr -}

my_member :: Eq a => a -> [a] -> Bool
my_member a x = or (map (==a) x)

-- This version of length uses the built-in const function,
-- which is defined as:
--      const k x = k
clever_length x = sum (map (const 1) x)

{- See the tutorial for more information on foldr and foldl.  Simple
   example of use:

foldr (+) 0 [1,8,5]

this is equivalent to 1+8+5+0
-}

my_sum = foldr (+) 0 
my_product = foldr (*) 1
my_or = foldr (||) False
my_and = foldr (&&) True