gangster

GOGO GANG

Every Gangster should know about ?

Functional Programming

via haskell

		▹ In Java:
total = 0;
for (i = 1; i <= 10; ++i)
total = total + i;

	▹ In Haskell:
    sum [1..10] 

		▹ In Haskell fibonacci:
	fib = 1:1:zipWith (+) fib (tail fib)

	take 10 fib 

What is functional prog ?

▹ "Programming with Mathematical Functions."
		Always same output for same input.

▹ Computation = Application of functions to arguments

          
										Pure World :            Imperative world :
                                        
						f :: Int -> Int         |     int f (int) 
						                        |    
						(f(3) , f(3))           |     (f(3) , f(3))   
						                        |  
						let x = f(3) in (x,x)   |     Can't do it. #time on clk
										

Haskell

" Haskell is a pure, statically typed, lazy functional
		programming language."


				▹ Purity. It doesn’t allow any side-effects.

				▹ Laziness (non-strict).

				▹ Strong static typing.

				▹ Elegance. Stuff just work like you’d expect it to

Wrong Marketing

    
    Special characteristics && advantages func prog :
     
     ♥ Functional programs contain no assignment statements.
     
     ♥ Functional programs contain no side-effects at all.
     
     -- Makes the order of execution irrelevant 
     -- Expression can be evaluated at any time.
     
     ♥ Relieves the programmer of the burden of 
       prescribing the flow of control.
										

Buzzword No.1

									REFERENTIAL TRANSPARENCY :

									"An expression is said to be referentially transparent 
									 if it can be replaced with its value without
									 changing the behavior of a program ."			
									 
									 Equals can be replaced by Equals.
									 
         ♥ 	Functions are values	 ♥
									

John Hughes '1984

    "As software becomes more and more complex, 
      it is more and more important to structure it well." 
           
    "Conventional languages place conceptual limits 
     on the way problems can be modularised.
     Functional languages push those limits back."
										

Modular design - great productivity improvements :

1. Small modules

2. Module Reuse

3. Modules Tested independently

"The ways in which one can divide up the original prob depend
 directly on the ways in which one can glue sols together."

"To increase ones ability to modularise a prob conceptually,
 one must provide new kinds of glue in the prog lang."

▹ Two new kind of glue :

  ♥ Higher order functions.

  ♥ Lazy Evaluation.

Lambda Calculus

“Lambda calculus is a formal system in math logic & c.s for
 expressing computation by way of var binding & substitution."
 Composed only of functions.

♥ Smallest universal programming lang of the world

          E  ::=   x       -- MENTION

              |  λx.E      -- ABS

              |  E E       -- APP

Function Basics

Function types::

 Mathematics      Haskell
 f : A × B → C    f :: A -> B -> C

 f a + b  means (f a) + b
          not f (a + b)

            > head [1, 2, 3, 4, 5]     -- dual  tail
              1

            > take 3 [1, 2, 3, 4, 5]   -- dual drop
              [1,2,3]

            > length [1, 2, 3, 4, 5]
              5

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

Types and Classes

      "A type is a collection of related values."
						
      ♥ 	Bool , Char , String , Int , Integer , Float 
						List , Tuple , Function.
      
      → 	Type inference.

       	Curried Functions
       Every function in Haskell officially takes one parameter.       
       add :: (Int, Int) → Int
       add (x , y) = x + y
       
       add' :: Int → (Int → Int)
       add' x y = x + y
       	
       add' = λx → (λy → x + y)
				

     Polymorphic type:
          length :: [a] → Int	 

      -- a is a type var 
      
     Overloaded type:
            (+) :: Num a ⇒ a → a → a 

      -- Num a is Class constraint
       
      "Class" is a collection of types that support
       certain overloaded operations called methods. 
     ♥  Eq, Ord, Show, Read, Num, Integral, fractional
     

       Guarded Equation

       abs n  | n ≥ 0  = n
              | otherwise = −n      
       
       Miranda :
       abs n =  n , n >= 0
             = -n , otherwise             

      Pattern Matching :
      
   → [1,2,3,4] :: [Int]  is just Syntactic sugar for 
      1 : (2 : (3 : 4 : [] ) ) )    -- cons operator
      
      sum :: Num a => [a] -> a
      sum []     = 0
      sum (x:xs) = x + sum xs
      

 
      List Comprehension
      
      [ x | x <- [1 .. 10] , even x ]      
          -- Generator      --Guard
     
      factors :: Int -> [Int]
      factors n = [m | m <- [1 .. n], n `mod` m == 0]
     
      zip :: [a] -> [b] -> [ (a , b) ]
      

      Recursion
      
      fibonacci :: Int → Int
      fibonacci 0 = 0
      fibonacci 1 = 1
      fibonacci (n + 2) = fibonacci n + fibonacci (n + 1)
     
      

      Higher Order Functions
        " The functions take functions as parameters and 
           return functions as return values."
           applyTwice :: (a -> a) -> a -> a  
           applyTwice f x = f (f x)
           > applyTwice (+3) 10   
             16                
        The mother of all higher-order functions :           
           map :: (a -> b) -> [a] -> [b]			          
           map f [ ] = []
           map f (x : xs) = f x : map f xs	
            
           map f xs = [ f x | x <- xs ]   --using list compreh
           > map (+3) [1,5,3,1,6]  
             [4,8,6,4,9] 

  Filter :

     filter p xs = [ x | x <- xs, p x ]   -- using list compreh

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

     > filter even [1, 2, 3, 5]
       [2]                                   

				Simple functions with a common interface 
sum :: (Num a) => [a] -> a
sum [] = 0
sum (x:xs) = x + sum xs

prod :: (Num a) => [a] -> a
prod [] = 1
prod (x:xs) = x * prod xs

length :: [a] -> Int
length [] = 0
length (x:xs) = 1 + length xs 

f []     = v
f (x:xs) = x ⊕ f xs

foldr encapsulate this pattern of recursion.

     								foldr :: (a -> b -> b) -> b -> [a] -> b
         foldr f v [] = v
         foldr f v (x:xs) = f x ( foldr f v xs )
         
         foldr f v replaces 
            (:) by f and
            [] by v				
           
         foldr (+) 0 [3,2,5]          
         -> 3 : (2 : (5 : []))
         -> 3 + (2 + (5 + 0))		

        										sum’ = foldr (+) 0

										prod’ = foldr (*) 1

										length’ = foldr (\_ accum -> 1 + accum) 0
										

 The composition Operator :
										
        (.) :: (b → c) → (a → b) → (a → c)
        f . g = \x → f (g x )		
        
        > map (negate . abs) [5,-3,-6,7,-3,2,-19,24]  
         [-5,-3,-6,-7,-3,-2,-19,-24]  
        
        map :: (a -> b) -> [a] -> [b]
        map fn = foldr ((:) . fn) []        
        	

       " Haskell is a lazy language, meaning that the
         language will evaluate expr only one needed."

					(g . f) when applied to input  
      ⊛  g (f input)
       
      The two prog f & g are run together
      in strict synchronisation.
      
      If g terminates without reading all of 
      f’s output then f is aborted.
      F can even be a non-terminating program .

     > take 5 [1..]
     > sum . map (\_ -> 1)   -- No intermediate data structure.
     
      ♥ This allows termination conditions to be separated from 
      loop bodies - a powerful modularisation
      

   f x = 4711

    ⊥ is a non terminating function

       f  (True && ⊥)   ⊵    4711
    ≔
       f ⊥
    ≔
       4711      -- order of evaluation do't matters. 

  Beauty of lazy eval :

♥   It supports equational reasoning .
♥   U abstract from evaluation order.

  That's why fp very popular for concurrency & parallelism.

  Compiler / VM can deside in which order it eval things.
  Imperative world its dictated by lang spec.

Newton-Raphson Square Roots:

          This algorithm computes the square root of a number N by
          starting from an initial approximation a0 and computing
          better and better ones using the rule :
          a(n+1) = (a(n) + N/a(n)) / 2
          If the approximations converge to some limit a, then
          a = (a + N/a) / 2
    so    2a = a + N/a
          a = N/a
          a*a = N
          a = squareroot(N)
        Square root programs take a tolerance (eps) & stop when
        two successive approximations differ by less than eps.

     The algorithm is usually programmed as:
C    N IS CALLED ZN HERE SO THAT IT HAS THE RIGHT TYPE
     X = A0
     Y = A0 + 2.*EPS
C    THE VALUE OF Y DOES NOT MATTER SO LONG AS ABS(X-Y).GT.EPS
100  IF (ABS(X-Y).LE.EPS) GOTO 200
     Y = X
     X = (X + ZN/X) / 2.
     GOTO 100
200  CONTINUE
C    THE SQUARE ROOT OF ZN IS NOW IN X
This program is indivisible in conventional languages.

Each approx is derived from the previous one by the func
next N x = (x + N/x) / 2

Calling this function f, the sequence of approx is
[a0, f a0, f(f a0), f(f(f a0)), ..]

repeat f a = cons a (repeat f (f a))  -- for that

repeat (next N) a0   -- to compute approx 

   Takes a tolerance & a list of approx & looks down the list for
   two succ approx that differ by no more than the given tolerance.
       within eps (cons a (cons b rest)) = 
       = b ,                       if abs(a-b) <= eps
       = within eps (cons b rest),  otherwise 

       sqrt a0 eps N = within eps (repeat (next N) a0)        
       

     Type declarations :
        Introduce a new name for an existing type

        type String = [Char]

      Data declarations :
        Completely new type can be declared by
        specifying its values

         data Tree = Leaf Int | Node Tree Int Tree

          t :: Tree
          t = Node (Node (Leaf 1) 3 (Leaf 4)) 5
                   (Node (Leaf 6) 7 (Leaf 9))

     -- 5 3 7 : interbal nodes  -- 1 4 6 9 : leaves 

To handle nullable values we use an Algebraic Data Type
called Maybe
data Maybe a = Just a
               | Nothing
               deriving (Show)


safediv :: Int → Int → Maybe Int
safediv _ 0 = Nothing           --wildcard pattern
safediv m n = Just (m ‘div ‘ n)
               

        A parser is a program that takes a string of characters
and produces some form  of tree that makes the syntactic
structure of the string explicit.

        2 ∗ 3 + 4                                     
  type Parser = String → Tree

  type Parser = String → (Tree, String)

  type Parser = String → [(Tree, String)]

  type Parser a = String → [(a, String)]

         Basic parsers :    

Fails if the input string is empty & succeeds
with the first character as the result value otherwise:
      item :: Parser Char
      item = λinp → case inp of
                [] → []
                (x : xs) → [(x , xs)]              

The parser return v always succeeds :
return :: a → Parser a
return v = λinp → [(v , inp)]
The dual parser failure always fails :
failure :: Parser a
failure = λinp → [ ]

Defining our own application function:
   parse :: Parser a → String → [(a, String)]
   parse p inp = p inp     --Identity function

   > parse (return 1) "abc"
     [(1, "abc")]

   > parse failure "abc"
     []

   > parse item "abc"
     [(’a’, "bc")]           

      A parser type is a monad a math structure that has proved
      useful for  modelling many different kind of computation .
      MONAD :
      Is a computation that returns a value of type a.     
        item :: Parser a
             :: string -> [(a , String)]

        ♥ monads    M a
        M : Complicated computation
        that delivers the value of type a

       Type of monad abstract away from that computation.

  Sequencing :
Way of combining two parsers :
(>>=) :: Parser a → (a → Parser b) → Parser b
p >>= f = λinp → case parse p inp of
          [] → []
          [(v , out)] → parse (f v ) out    

do notation :
p :: Parser (Char , Char )
p = do x ← item
    item
    y ← item
    return (x , y)

IO MONAD

   But to be useful as well as beautiful, a language must
   manage the “Awkward Squad”:

    Input/Output
    Imperative update
    Error recovery (eg, timeout, divide by zero, etc.)
    Foreign-language interfaces
    Concurrency control

   Conflict : Laziness and side effects are incompatible

          Monadic I/O: The Key Idea :

          A value of type (IO t) is an “action”

          When performed, an action may do some
          input/output and deliver a result of type t

          type IO t = World -> (t, World)					

• General concept from category theory
 Adopted in Haskell for I/O, side effects, ...

• A monad consists of:
 – A type constructor M
 – A function bind :: M a -> ( a -> M b) -> M b
 – A function return :: a -> M a

          main = do
               foo <- putStrLn "Hello, what's your name?"
               name <- getLine
               putStrLn ("Hey " ++ name ++ ", you rock!")           

Category theory

Quick sort in C vs in Haskell

											void qsort(int a[], int lo, int h ){
															int h, l, p, t;
															if (lo < hi) {
																			l = lo;
																			h = hi;
																			p = a[hi];
																			do {
																					while ((l < h) && (a[l] <= p))
															           l = l+1;
															       while ((h > l) && (a[h] >= p))
															           h = h-1;
														       	if (l < h) {
														              	t = a[l];
															             a[l] = a[h];
															             a[h] = t; }
						} while (l < h);
      a[hi] = a[l];
      a[l] = p;
      qsort( a, lo, l-1 );
      qsort( a, l+1, hi );
   }
}

Qicksort in haskell

qsort [] = []
qsort (x:xs) = qsort ys ++ [x] ++ qsort zs
               where
                  ys = [y | y <- xs, y <= x]
                  zs = [z | z <- xs, z > x]