Upgrade to Pro — share decks privately, control downloads, hide ads and more …

NSLondon 10 -- Introduction to Functional Progr...

NSLondon 10 -- Introduction to Functional Programming / Haskell

My 'Introduction to Functional Programming / Haskell' from NSLondon 10

Johannes Weiss

June 26, 2014
Tweet

More Decks by Johannes Weiss

Other Decks in Programming

Transcript

  1. FP? Haskell Side Effects Monads Bonus End Introduction to Functional

    Programming / Haskell Johannes Weiß @johannesweiss NSLondon 10 Johannes Weiß Introduction to Functional Programming / Haskell
  2. FP? Haskell Side Effects Monads Bonus End Definition Definition of

    Functional Programming [...] functional programming is a programming paradigm, a style of building the structure and elements of computer programs, that treats computation as the evaluation of mathematical functions and avoids state and mutable data. Wikipedia 1 1https://en.wikipedia.org/wiki/Functional programming Johannes Weiß Introduction to Functional Programming / Haskell
  3. FP? Haskell Side Effects Monads Bonus End Intro Type System

    Laziness Purity Currying What is Haskell? Haskell will serve as an example for a functional programming language. But there are many others (e.g. Lisp, Erlang, Scala, F#, ML, Closure, etc.) Haskell is a computer programming language. In particular, it is a polymorphically statically typed, lazy, purely functional language, quite different from most other programming languages. Haskell Wiki 2 2http://www.haskell.org/haskellwiki/Introduction Johannes Weiß Introduction to Functional Programming / Haskell
  4. FP? Haskell Side Effects Monads Bonus End Intro Type System

    Laziness Purity Currying Haskell in one slide (credits to Simon PJ) filter :: (a -> Bool) -> [a] -> [a] filter pred [] = [] filter pred (x:xs) -- (1 : (2 : (3: []))) == [1,2,3] | pred x = x : filter pred xs | otherwise = filter pred xs Type signature Higher order Polymorphism (works for any type a) Function defined by pattern matching Guards distinguish sub–cases f x y rather that f(x,y) Johannes Weiß Introduction to Functional Programming / Haskell
  5. FP? Haskell Side Effects Monads Bonus End Intro Type System

    Laziness Purity Currying filter in Objective-C NSArray *filter(BOOL(^pred)(id obj), NSArray *list) { NSMutableArray *objsPassingTest = [NSMutableArray array]; for (id x in list) { if (pred && pred(x)) { [objsPassingTest addObject:x]; } } return [objsPassingTest copy]; } Johannes Weiß Introduction to Functional Programming / Haskell
  6. FP? Haskell Side Effects Monads Bonus End Intro Type System

    Laziness Purity Currying filter in Swift func filter<T>(pred: (T -> Bool), list: T[]) -> T[] { var filtered : T[] = [] for x in list { if pred(x) { filtered += x; } } return filtered; } Johannes Weiß Introduction to Functional Programming / Haskell
  7. FP? Haskell Side Effects Monads Bonus End Intro Type System

    Laziness Purity Currying Static Types Haskell’s type system is strongly and statically typed (so is Swift’s). • Strong type system: Fine grained set of types (characters, booleans, and integers are not the same) • Static type system: types known at compile time C is weakly but statically typed. Objective-C is weakly typed and a hybrid between static and dynamic typing (type id can be anything without even needing a cast). Johannes Weiß Introduction to Functional Programming / Haskell
  8. FP? Haskell Side Effects Monads Bonus End Intro Type System

    Laziness Purity Currying Polymorphism The type system supports (multiple forms) of polymorphism: • Parametric Polymorphism (similar to Java, .Net Generics) -- Standard Functions map :: (a -> b) -> [a] -> [b] length :: [a] -> Int odd :: Integral a => a -> Bool -- 1: map as (String -> Int) -> [String] -> [Int] strLens = map length ["C", "Objective-C", "C++"] strLens = [1, 11, 3] -- the result -- 2: map as (Int -> Bool) -> [Int] -> [Bool] oddInts = map odd [1, 2, 3, 4, 5] oddInts = [True,False,True,False,True] -- the result Johannes Weiß Introduction to Functional Programming / Haskell
  9. FP? Haskell Side Effects Monads Bonus End Intro Type System

    Laziness Purity Currying Polymorphism • Ad–hoc Polymorphism (similar to Operator Overloading) -- (==) :: Eq a => a -> a -> Bool okIntegers :: Bool okIntegers = 1 == 2 -- is False okStrings :: Bool okStrings = "foo" == "foo" -- is True compileTimeError = "foo" == True {- Couldn’t match expected type ‘[Char]’ with actual type ‘Bool’ In the second argument of ‘(==)’, namely ‘True’ In the expression: "foo" == True In an equation for ‘compileTimeError’: compileTimeError = "foo" == True -} Johannes Weiß Introduction to Functional Programming / Haskell
  10. FP? Haskell Side Effects Monads Bonus End Intro Type System

    Laziness Purity Currying Type Classes class Eq a where (==) :: a -> a -> Bool (/=) :: a -> a -> Bool -- not strictly needed data Maybe a = Just a | Nothing -- example: Just "Hello World!" :: Maybe String instance Eq a => Eq (Maybe a) where mL == mR = case (mL, mR) of (Just l , Just r ) -> l == r (Nothing, Nothing) -> True _ -> False Johannes Weiß Introduction to Functional Programming / Haskell
  11. FP? Haskell Side Effects Monads Bonus End Intro Type System

    Laziness Purity Currying Maybe in Swift enum Maybe<A> { case Just(A) case Nothing } func ==<A:Equatable>(mL:Maybe<A>,mR:Maybe<A>)->Bool { switch ((mL, mR)) { case (.Just(let l), .Just(let r)): return l == r case (.Nothing, .Nothing): return true default: return false } } Johannes Weiß Introduction to Functional Programming / Haskell
  12. FP? Haskell Side Effects Monads Bonus End Intro Type System

    Laziness Purity Currying Laziness Haskell is a language which does lazy evaluation. This means: An expression is evaluated when some other computation needs the value. {- important to know: The cons (:) operator: [1, 2, 3] == 1 : 2 : 3 : [] Standard Library: take :: Int -> [a] -> [a] -} endlessFrom :: Integer -> [Integer] endlessFrom n = n : endlessFrom (n+1) first5 :: [Integer] first5 = take 5 (endlessFrom 1) first5 = [1,2,3,4,5] -- the result Johannes Weiß Introduction to Functional Programming / Haskell
  13. FP? Haskell Side Effects Monads Bonus End Intro Type System

    Laziness Purity Currying Purity • Pure computations yield the same value each time they are invoked. • No actions (often called side effects) allowed! • That allows laziness (can be evaluated at any time) • Consequences: • No I/O (user input, random values, etc.) in pure computations • No state • No variables (writing to variables is a side effect) • No side effects • Advantages • Concurrency — no problem with pure computations • Referential transparency gives room for compiler optimisations • Types speak: Same function parameters ⇒ same return value Johannes Weiß Introduction to Functional Programming / Haskell
  14. FP? Haskell Side Effects Monads Bonus End Intro Type System

    Laziness Purity Currying Currying -- Standard Library -- foldl :: (a -> b -> a) -> a -> [b] -> a -- | Adds four numbers. sum4 :: Num a => a -> a -> a -> a -> a sum4 a b c d = foldl (+) 0 [a, b, c, d] -- | Adds three numbers. sum3 :: Num a => a -> a -> a -> a sum3 = sum4 0 In fact, all Haskell functions have one parameter! sum4 1 2 3 4 == ((((sum4 1) 2) 3) 4) == 10 Prelude> :type sum4 sum4 :: Num b => b -> b -> b -> b -> b Prelude> :type sum4 1 sum4 1 :: Num b => b -> b -> b -> b Prelude> :type sum4 1 2 sum4 1 2 :: Num b => b -> b -> b Prelude> :type sum4 1 2 3 sum4 1 2 3 :: Num b => b -> b Prelude> :type sum4 1 2 3 4 sum4 1 2 3 4 :: Num b => b Johannes Weiß Introduction to Functional Programming / Haskell
  15. FP? Haskell Side Effects Monads Bonus End Real–world Intro Example

    Real–World Programs That looks nice but how to write real–world programs? Real programs need side effects! (Otherwise it’s pointless to even run them) Johannes Weiß Introduction to Functional Programming / Haskell
  16. FP? Haskell Side Effects Monads Bonus End Real–world Intro Example

    Side Effects There are many different kinds of side effects: • Global side effects (such as I/O) • Local side effects (such as reading and writing to local variables) Johannes Weiß Introduction to Functional Programming / Haskell
  17. FP? Haskell Side Effects Monads Bonus End Real–world Intro Example

    Side Effects First idea (like in most languages): putStr :: String -> () -- like void putStr(NSString *) But, that would mean filter can do arbitrary things as well, e.g. filterBad :: (a -> Bool) -> [a] -> [a] filterBad pred [] = [] filterBad pred (x:xs) | pred x = x : filter pred xs | otherwise = launchTheMissiles And what does the following mean? [putStr "foo", putStr "bar"] Keep in mind: order of evaluation, laziness! Johannes Weiß Introduction to Functional Programming / Haskell
  18. FP? Haskell Side Effects Monads Bonus End Real–world Intro Example

    Fun $ xcrun swift Welcome to Swift! Type :help for assistance. 1> :version lldb-320.3.100 1> let xs = [println("foo"), println("bar")] Segmentation fault: 11 (core dumped) Johannes Weiß Introduction to Functional Programming / Haskell
  19. FP? Haskell Side Effects Monads Bonus End Real–world Intro Example

    YO! Johannes Weiß Introduction to Functional Programming / Haskell
  20. FP? Haskell Side Effects Monads Bonus End Real–world Intro Example

    The main idea A value of type IO t is an “action” that, when performed, may do some input/output before delivering a result of type t. putStr :: String -> IO () • An action is a first class value • Evaluating an action has no effect; performing the action has an effect • Approximation: type IO a = World -> (a, World) i.e. putStr :: String -> World -> ((), World) Johannes Weiß Introduction to Functional Programming / Haskell
  21. FP? Haskell Side Effects Monads Bonus End Real–world Intro Example

    Somewhat Real World Program -- getLine :: IO String -- putStr :: String -> IO () -- main is the entry point of a Haskell program main :: IO () main = do putStr "Hey there, what’s your name? " name <- getLine putStr ("Hello " ++ name ++ "!\n") • The do–notation looks deliberately imperative. Johannes Weiß Introduction to Functional Programming / Haskell
  22. FP? Haskell Side Effects Monads Bonus End Intro What? STM

    Special Case I/O? • So did Haskell just special case I/O operations with the do notation? No! • In fact, the do notation is syntactical sugar for monadic computations. Johannes Weiß Introduction to Functional Programming / Haskell
  23. FP? Haskell Side Effects Monads Bonus End Intro What? STM

    What is a Monad? A monad is defined by the following type class. class Monad m where -- | Sequentially compose two actions, passing -- any value produced by the first as an -- argument to the second. (>>= aka "bind") (>>=) :: m a -> (a -> m b) -> m b -- | Inject a value into the monadic type. return :: a -> m a instance Monad IO where [...] Johannes Weiß Introduction to Functional Programming / Haskell
  24. FP? Haskell Side Effects Monads Bonus End Intro What? STM

    What’s that all about? No worries, monads are an abstract concept which looks complicated at first. Bear with me for some real world examples. For now, one of the monad analogies are enough. I’d go for 1 or 2. 1 Warm, fuzzy things (Simon PJ “feels that the term Monad is far too imposing”) 2 Programmable semicolons 3 Burritos, space suits, ... (the infamous Monad tutorials) Examples for Monads • State — local side efects (like local variables) • Maybe (like Swift’s optional chaining) • Parsers (parser combinators) • I/O Johannes Weiß Introduction to Functional Programming / Haskell
  25. FP? Haskell Side Effects Monads Bonus End Intro What? STM

    Tackling concurrency with STM (Software Transactional Memory) atomically :: STM a -> IO a newTVar :: a -> STM (TVar a) -- new tx var readTVar :: TVar a -> STM a -- read contents writeTVar :: TVar a -> a -> STM () -- write contents Johannes Weiß Introduction to Functional Programming / Haskell
  26. FP? Haskell Side Effects Monads Bonus End Intro What? STM

    A classic example: Accounting type Account = TVar Int deposit :: Account -> Int -> STM () deposit k amount = do bal <- readTVar k writeTVar k (bal + amount) withdraw :: Account -> Int -> STM () withdraw k amount = deposit k (- amount) transfer :: Account -> Account -> Int -> IO () transfer k1 k2 amount = atomically (do deposit k2 amount withdraw k1 amount) Johannes Weiß Introduction to Functional Programming / Haskell
  27. FP? Haskell Side Effects Monads Bonus End Intro What? STM

    Composability of STM splitTransfer :: Account -> Account -> Account -> Int -> IO () splitTransfer k1 k2 k3 amount = atomically $ do withdraw k1 (2 * amount) deposit k2 amount deposit k3 amount Johannes Weiß Introduction to Functional Programming / Haskell
  28. FP? Haskell Side Effects Monads Bonus End Bonus Material :-)

    Here some bonus material. Added that after the talk because some nice guy made me aware I totally missed adding some Haskell resources. Thanks for that! The books are free to read online btw. • Book: Learn You a Haskell for a Great Good 3 • Book: Real World Haskell 4 • FPComplete’s School of Haskell 5 • NSLondon Demo Project (runnable in the browser) 6 3http://learnyouahaskell.com/ 4http://book.realworldhaskell.org/ 5https://www.fpcomplete.com/school 6https://www.fpcomplete.com/user/johannesweiss/adopted/nslondon10demo Johannes Weiß Introduction to Functional Programming / Haskell
  29. FP? Haskell Side Effects Monads Bonus End Thank you! Questions?

    Johannes Weiß Introduction to Functional Programming / Haskell