Haskell - 101

An introduction to Haskell and Functional Programming, for absolute beginners. Presented during a joint NCR Haskell and Linux Delhi meetup in July.

Transcript

1. HASKELL 101 FOR ABSOLUTE BEGINNERS ANUPAM JAIN
2. HASKELL 101 FUNCTIONAL PROGRAMMING ▸ SIMPLICITY ▸ MODULARITY ▸ ABSTRACTION ▸ COMPOSITION 2 SOFTWARE DESIGN
3. HASKELL 101 SIMPLICITY ▸ First Class Functions. That’s it. ▸ Declarative ▸ Immutable 3
4. HASKELL 101 THIS IS SPARTA HASKELL 1 module Main where 2 3 main :: IO () 4 main = do 5 putStrLn "Hello Haskell!" 6 4
5. HASKELL 101 THIS IS SPARTA HASKELL 1 module Main where 2 3 main :: IO () 4 main = do 5 putStrLn "What is your name?" 6 name <- getLine 7 putStrLn ("Hello " ++ name ++ “!") 8 5
6. HASKELL 101 THIS IS SPARTA HASKELL 1 module Main where 2 3 main :: IO () 4 main = do 5 name <- getName 6 putStrLn ("Hello " ++ name ++ "!") 7 8 getName :: IO String 9 getName = do 10 putStrLn "What is your name?" 11 getLine 6
7. HASKELL 101 “IO” DENOTES MUTATION 1 main :: IO () 2 main = do 3 name <- getName 4 showGreeting name 5 6 showGreeting :: String -> IO () 7 showGreeting name = putStrLn (greeting name) 8 9 getName :: IO String 10 getName = ... 11 12 greeting :: String -> String 13 greeting name = "Hello " ++ name ++ "!" 7
8. HASKELL 101 DATA TYPES 1 data Maybe a 2 = Nothing 3 | Just a 4 5 data Either a b 6 = Left a 7 | Right b 8 9 data List a 10 = Empty 11 | Cons a (List a) 12 13 data Tree a 14 = Leaf a 15 | Branch (Tree a) (Tree a) 16 8
9. HASKELL 101 COMPOSITION VS INHERITANCE ▸ Don’t inherit, compose ▸ Vehicle > Car > RacingCar ▸ data RacingCar = RacingCar VehicleData CarData RacingCarData 9
10. HASKELL 101 PATTERN MATCHING 1 data List a 2 = Empty 3 | Cons a (List a) 4 5 cdr :: List a -> List a 6 cdr Empty = ?? 7 cdr (Cons _ rest) = rest 8 9 car :: List a -> a 10 car Empty = ?? 11 car (Cons a _) = a 12 10
11. HASKELL 101 PATTERN MATCHING 1 data List a 2 = Empty 3 | Cons a (List a) 4 5 cdr :: List a -> List a 6 cdr Empty = Empty 7 cdr (Cons _ rest) = rest 8 9 car :: List a -> Maybe a 10 car Empty = Nothing 11 car (Cons a _) = Just a 12 13 data Maybe a = Nothing | Just a 14 11
12. HASKELL 101 TYPE SAFE WEB ROUTING data MyRoute = HomeR | HelloR Text renderRoute :: MyRoute -> [Text] parseRoute :: [Text] -> MyRoute 12 Check out https://github.com/ajnsit/wai-routes
13. HASKELL 101 GENERATED WEB SERVER ROUTING case getPathInfo req of "hello" : arg : [] -> case getReqMethod req of GET -> getHello arg req POST -> postHello arg req 13
14. HASKELL 101 REAL WORLD HASKELL getAlbumsR :: Handler AlbumRoute getAlbumsR = runHandlerM $ do Just token <- reqHeader “Authorisation” auth <- liftIO $ post (showRoute ValidateR) token if isValid auth then status 403 >> json err else json albums 14
15. HASKELL 101 RECURSION 1 data List a 2 = Empty 3 | Cons a (List a) 4 5 concat :: List a -> List a -> List a 6 concat Empty b = b 7 concat a Empty = a 8 concat (Cons x xs) b@(Cons _ _) 9 = Cons x (concat xs b) 10 15
16. HASKELL 101 PYTHON 1 class Cell: 2 def __init__( self, data, next = None ): 3 self.data = data 4 self.next = next 5 6 def concat(A, B): 7 current = A 8 while current.next != None: 9 current = current.next 10 current.next = B 11 return A 16
17. HASKELL 101 PYTHON def concat(A, B): current = A while current.next != None: current = current.next current.next = B return A 17 concat Empty b = b concat a Empty = a concat (Cons x xs) b = Cons x (concat xs b) HASKELL FIGHT!
18. HASKELL 101 PYTHON def concat(A, B): current = A while current.next != None: current = current.next current.next = B return A 18 concat Empty b = b concat a Empty = a concat (Cons x xs) b = Cons x (concat xs b) HASKELL TEST assertEq(concat('','bar'), 'bar') assertEq(concat('foo',''), 'foo') assertEq(concat(‘foo’,'bar'), 'foobar')
19. HASKELL 101 PYTHON def concat(A, B): current = A while current.next != None: current = current.next current.next = B return A 19 concat Empty b = b concat a Empty = a concat (Cons x xs) b = Cons x (concat xs b) HASKELL
20. THERE ARE TWO WAYS OF CONSTRUCTING A SOFTWARE DESIGN: ONE WAY IS TO MAKE IT SO COMPLICATED THAT THERE ARE NO OBVIOUS DEFICIENCIES, AND THE OTHER WAY IS TO MAKE IT SO SIMPLE THAT THERE ARE OBVIOUSLY NO DEFICIENCIES. - C.A.R. Hoare, 1980 ACM Turing Award Lecture HASKELL 101 20
21. HASKELL 101 SUM NUMBERS FROM 1 TO 10 1 total = 0, count = 1 2 while count <= 10: 3 total = total + count 4 count = count + 1 21 1 total = sum [1..10]
22. HASKELL 101 ABSTRACTION ▸ The shared vocabulary that allows us to write concise, high level, programs 22
23. HASKELL 101 SHARED VOCABULARY COMPARED 1 total = 0, count = 1 2 while count <= 10: 3 total = total + count 4 count = count + 1 23 1 total = sum [1..10]
24. HASKELL 101 SUM ELEMENTS OF A LIST 1 sum :: [Int] -> Int 2 sum [] = 0 3 sum (x:xs) = x + sum xs 4 24
25. HASKELL 101 MULTIPLY ELEMENTS OF A LIST 1 prod :: [Int] -> Int 2 prod [] = 0 3 prod (x:xs) = x * sum xs 4 25
26. HASKELL 101 ABSTRACTION 1 fold :: (a -> Int -> a) -> a -> [Int] -> a 2 fold _ a [] = a 3 fold f a (x:xs) = fold f (f a x) xs 4 26
27. HASKELL 101 FOLD OVER ELEMENTS OF A LIST 1 sum = fold (+) 0 2 prod = fold (*) 1 3 27
28. HASKELL 101 IS ANY/ALL BOOLEAN TRUE 1 any = fold (||) False 2 all = fold (&&) True 3 28
29. HASKELL 101 ARE ANY/ALL ELEMENTS > 3 1 anyLarge = fold (\p e -> p || e > 3) False 2 allLarge = fold (\p e -> p && e > 3) True 3 29
30. HASKELL 101 ARE ANY/ALL ELEMENTS DIGITS 1 anyDigit = fold (\p e -> p || isDigit e) False 2 allDigit = fold (\p e -> p && isDigit e) True 3 30
31. HASKELL 101 MORE ABSTRACTION! 1 foldMap :: (a -> Int -> a) -> (Int -> Int) -> a -> [Int] -> a 2 foldMap _ _ a [] = a 3 foldMap f m a (x:xs) = foldMap f m (f a (m x)) xs 4 31
32. HASKELL 101 ARE ANY/ALL ELEMENTS > 3 1 anyLarge = foldMap (||) (> 3) False 2 allLarge = foldMap (&&) (> 3) True 3 32
33. HASKELL 101 ARE ANY/ALL ELEMENTS DIGITS 1 anyDigit = foldMap (||) isDigit False 2 allDigit = foldMap (&&) isDigit True 3 33
34. HASKELL 101 WHY? 34
35. HASKELL 101 WHY ▸ Easy to understand what's going on ▸ Cleanly separated “logic” ((&&), isdigit, etc.) ▸ Common machinery (foldMap) can be easily reused ▸ Easy to test functions in isolation 35
36. HASKELL 101 BUT… ▸ foldMap has 3 arguments that are not easy to remember ▸ It's harder to generalise this pattern. Should we keep on adding arguments to fold/foldMap? 36
37. HASKELL 101 WE CAN ABSTRACT FURTHER 1 compose2 :: (a -> b -> d) -> (x -> b) -> a -> x -> d 2 compose2 f m a x = f a (m x) 3 foldMap f m a (x:xs) = foldMap f m (f a (m x)) xs 4 = foldMap f m (compose2 f m a x) xs foldMap f m a (x:xs) = fold (compose2 f m) a x xs 37
38. HASKELL 101 ARE ANY/ALL ELEMENTS > 3 1 anyLarge = fold (compose2 (||) (> 3)) False 2 allLarge = fold (compose2 (&&) (> 3)) True 3 38
39. HASKELL 101 ARE ANY/ALL ELEMENTS DIGITS 1 anyDigit = fold (compose2 (||) isDigit) False 2 allDigit = fold (compose2 (&&) isDigit) True 3 39
40. HASKELL 101 MUCH BETTER ▸ We removed an extra function (foldMap) which was actually not needed ▸ Our existing machinery (fold) turned out to be powerful enough to support our logic ▸ We reduced code complexity by introducing another “orthogonal” and “generic” shared vocabulary (compose2) 40
41. HASKELL 101 ARE ANY/ALL ELEMENTS DIGITS 1 anyDigit = fold (compose2 (||) isDigit) False 2 allDigit = fold (compose2 (&&) isDigit) True 3 41
42. PERFECTION IS ATTAINED NOT WHEN THERE IS NOTHING MORE TO ADD, BUT WHEN THERE IS NOTHING MORE TO REMOVE. - Antoine de Saint Exupéry HASKELL 101 42
43. HASKELL 101 GO DEEPER 1 (.) :: (b -> c) -> (a -> b) -> a -> c 2 (.) f g a = f (g a) 3 4 flip :: (a -> b -> c) -> b -> a -> c 5 flip f b a = f a b 6 43
44. HASKELL 101 ARE ANY/ALL ELEMENTS DIGITS 1 anyDigit = fold (flip ((||) . isDigit)) False 2 allDigit = fold (flip ((&&) . isDigit)) True 3 44
45. HASKELL 101 FUNCTIONS ARE DATA PIPELINES (flip ((||) . isDigit)) a b = ((||) . isDigit) b a = ((||) (isDigit b)) a = a || isDigit b 45
46. HASKELL 101 FUNCTOR CLASS 1 class Functor f where 2 fmap :: (a -> b) -> f a -> f b 46
47. HASKELL 101 FOLDABLE CLASS 1 class Foldable f where 2 foldr :: (b -> a -> b) -> b -> f a -> b 47
48. HASKELL 101 LIST INSTANCES 2 instance Functor [] where 3 fmap f [] = [] 4 fmap f (x:xs) = (f x: map f xs) 5 6 instance Foldable [] where 7 foldl f b [] = b 8 foldl f b (x:xs) = foldl f (f b x) xs 48
49. HASKELL 101 ANY DATA STRUCTURE CAN BE FOLDED ▸ When Data is Non-Recursive, its the same as fmap ▸ When a data structure is recursive, each recursive part needs to be handled separately 49
50. HASKELL 101 TREE 2 instance Functor Tree where 3 fmap f (Leaf a) = Leaf (f a) 4 fmap f (Branch x y) = Branch (fmap f x) (fmap f y) 5 6 instance Foldable Tree where 7 foldl f b (Leaf a) = f b a 8 foldl f b (Branch x y) = ?? (foldl f b x) (foldl f b y) 50
51. HASKELL 101 FOLD TREE 1 foldTree :: (b -> a -> b) -> (b -> b -> b) -> b 2 -> Tree a -> b 3 foldTree f g b (Leaf a) = f b a 4 foldTree f g b (Branch x y) 5 = g (foldTree f g b x) (foldTree f g b y) 51
52. HASKELL 101 ANOTHER COMMON PATTERN 1 foldTree :: (b -> a -> b) -> (b -> b -> b) -> b 2 -> Tree a -> b 3 foldTree f g b (Leaf a) = f b a 4 foldTree f g b (Branch x y) 5 = g (foldTree f g b x) (foldTree f g b y) 52
53. HASKELL 101 MONOID 1 class Monoid m where 2 (<>) :: m -> m -> m 53
54. HASKELL 101 FOLDABLE TREE REVISITED 1 foldTree :: Monoid b => (b -> a -> b) -> b 2 -> Tree a -> b 3 foldTree f b (Leaf a) = f b a 4 foldTree f b (Branch x y) 5 = foldTree f b x <> foldTree f b y 54
55. FIN Questions?