関数型プログラミングの世界
?
24 likes?3,713 views
関数型プログラミングで重要となる高階関数と遅延評価について紹介。時間の関係で、遅延評価については Why Functional Programming Matters とその関連 URL の紹介しかしていない。
![Haskell [ ]
e.g. []
[1, 2, 3]
(:)
e.g. [1] => 1 : []
[1, 2, 3] => 1 : 2 : 3 : []
Monday, June 13, 2011 21](https://image.slidesharecdn.com/whyfp-110612091857-phpapp01/85/-21-320.jpg)
![(:) LISP
cons
cons Haskell
cons :: a -> [a] -> [a] --
cons x [] = [x] --
cons x1 (x2:xs) = x1 : (cons x2 xs)
Monday, June 13, 2011 22](https://image.slidesharecdn.com/whyfp-110612091857-phpapp01/85/-22-320.jpg)
![cons :: a -> [a] -> [a] --
cons x [] = [x] --
cons x1 (x2:xs) = x1 : (cons x2 xs)
// C++
template <typename a>
std::list<a>
cons(a const& x, std::list<a> const& xs);
Monday, June 13, 2011 23](https://image.slidesharecdn.com/whyfp-110612091857-phpapp01/85/-23-320.jpg)
![cons :: a -> [a] -> [a] --
cons x [] = [x] --
cons x1 (x2:xs) = x1 : (cons x2 xs)
e.g. cons 0 [1,2,3,4]
=> x1 0, x2 1, xs [2,3,4]
Monday, June 13, 2011 24](https://image.slidesharecdn.com/whyfp-110612091857-phpapp01/85/-24-320.jpg)
![(Int)
sum
sum :: [Int] -> Int
sum [] = 0
sum (n:ns) = n + (sum ns)
Monday, June 13, 2011 25](https://image.slidesharecdn.com/whyfp-110612091857-phpapp01/85/-25-320.jpg)
![cons sum
cons :: a -> [a] -> [a]
cons x [] = [x]
cons x1 (x2:xs) = x1 : (cons x2 xs)
sum :: [Int] -> Int
sum [] = 0
sum (n:ns) = n + (sum ns)
Monday, June 13, 2011 26](https://image.slidesharecdn.com/whyfp-110612091857-phpapp01/85/-26-320.jpg)
![cons x [] = [x]
sum [] = 0
cons x1 (x2:xs) = x1 : (cons x2 xs)
sum (n :ns) = n + (sum ns)
Monday, June 13, 2011 27](https://image.slidesharecdn.com/whyfp-110612091857-phpapp01/85/-27-320.jpg)
![(Int)
product
product :: [Int] -> Int
product [] = 1
product (n:ns) = n * product ns
Monday, June 13, 2011 28](https://image.slidesharecdn.com/whyfp-110612091857-phpapp01/85/-28-320.jpg)
![cons x [] = [x]
sum [] = 0
product [] = 1
cons x1 (x2:xs) = x1 : (cons x2 xs)
sum (n :ns) = n + (sum ns)
product (n :ns) = n * (product ns)
Monday, June 13, 2011 29](https://image.slidesharecdn.com/whyfp-110612091857-phpapp01/85/-29-320.jpg)
![(Bool)
allTrue
allTrue :: [Bool] -> Bool
allTrue [] = True
allTrue (b:bs) = b && allTrue ns
Monday, June 13, 2011 30](https://image.slidesharecdn.com/whyfp-110612091857-phpapp01/85/-30-320.jpg)
![(Bool)
anyTrue
anyTrue :: [Bool] -> Bool
anyTrue [] = False
anyTrue (b:bs) = b || anyTrue ns
Monday, June 13, 2011 31](https://image.slidesharecdn.com/whyfp-110612091857-phpapp01/85/-31-320.jpg)
![cons x [] = [x]
sum [] = 0
product [] = 1
allTrue [] = True
anyTrue [] = False
cons x1 (x2:xs) = x1 : (cons x2 xs)
sum (n :ns) = n + (sum ns)
product (n :ns) = n * (product ns)
allTrue (b :bs) = b && (allTrue bs)
anyTrue (b :bs) = b || (anyTrue bs)
Monday, June 13, 2011 32](https://image.slidesharecdn.com/whyfp-110612091857-phpapp01/85/-32-320.jpg)
![cons x [] = [x]
sum [] = 0
product [] = 1
allTrue [] = True
anyTrue [] = False
cons x1 (x2:xs) = x1 : (cons x2 xs)
sum (n :ns) = n + (sum ns)
product (n :ns) = n * (product ns)
allTrue (b :bs) = b && (allTrue bs)
anyTrue (b :bs) = b || (anyTrue bs)
Monday, June 13, 2011 32](https://image.slidesharecdn.com/whyfp-110612091857-phpapp01/85/-33-320.jpg)
![reduce :: (a -> [a] -> a) -> a -> [a] -> a
reduce f x0 [] = x0
reduce f x0 (x1:xs) = f x1 (reduce f x0 xs)
sum = reduce (+) 0
product = reduce (*) 1
allTrue = reduce (&&) True
anyTrue = reduce (||) False
Monday, June 13, 2011 33](https://image.slidesharecdn.com/whyfp-110612091857-phpapp01/85/-34-320.jpg)
![reduce :: (a -> [a] -> a) -> a -> [a] -> a
reduce f x0 [] = x0
reduce f x0 (x1:xs) = f x1 (reduce f x0 xs)
sum = reduce (+) 0
product = reduce (*) 1
allTrue = reduce (&&) True
anyTrue = reduce (||) False
Monday, June 13, 2011 33](https://image.slidesharecdn.com/whyfp-110612091857-phpapp01/85/-35-320.jpg)
![reduce :: (a -> [a] -> a) -> a -> [a] -> a
reduce f x0 [] = x0
reduce f x0 (x1:xs) = f x1 (reduce f x0 xs)
sum = reduce (+) 0
product = reduce (*) 1
allTrue = reduce (&&) True
anyTrue = reduce (||) False
Monday, June 13, 2011 33](https://image.slidesharecdn.com/whyfp-110612091857-phpapp01/85/-36-320.jpg)
![reduce :: (a -> [a] -> a) -> a -> [a] -> a
reduce f x0 [] = x0
reduce f x0 (x1:xs) = f x1 (reduce f x0 xs)
sum = reduce (+) 0
product = reduce (*) 1
allTrue = reduce (&&) True
anyTrue = reduce (||) False
Monday, June 13, 2011 33](https://image.slidesharecdn.com/whyfp-110612091857-phpapp01/85/-37-320.jpg)
![cons reduce
append :: [a] -> [a] -> [a]
append xs ys = reduce (:) ys xs
append [1,2] [3,4]
-> reduce (:) [3,4] [1,2]
-> reduce (:) [3,4] (1:2:[])
-> 1 : (reduce (:) [3,4] (2:[]))
-> 1 : 2 : (reduce (:) [3,4] [])
-> 1 : 2 : [3,4]
-> [1,2,3,4]
Monday, June 13, 2011 34](https://image.slidesharecdn.com/whyfp-110612091857-phpapp01/85/-38-320.jpg)
![-- Haskell
reduce (+) 0 [1..10]
// C++
int ns[] = {1,2,3,4,5,6,7,8,9,10};
std::accumulate(ns, ns + 10, 0, &std::plus<int>);
# Ruby
[*1..10].inject(0, :+)
Monday, June 13, 2011 41](https://image.slidesharecdn.com/whyfp-110612091857-phpapp01/85/-45-320.jpg)
関数型プログラミングの世界
- 1. Welcome to the world of the functional programming Kenta Murata 2011.06.11 #osc11do Monday, June 13, 2011 1
- 2. Monday, June 13, 2011 2
- 3. mrkn Ruby Ruby http://www.flickr.com/photos/koichiroo/5244581973/ Monday, June 13, 2011 3
- 4. Monday, 1 2010 3 June 13, 2011 4
- 5. Welcome to the world of the functional programming Kenta Murata 2011.06.11 #osc11do Monday, June 13, 2011 5
- 6. Functional Programming Monday, June 13, 2011 6
- 7. Imperative Programming Procedural Programming Monday, June 13, 2011 7
- 8. Fortran Basic Cobol Algol C C++ Java LISP Monday, June 13, 2011 8
- 9. Monday, June 13, 2011 9
- 10. Functional Programming Monday, June 13, 2011 10
- 11. High-order Functions Lazy Evaluation Monday, June 13, 2011 11
- 12. Functions as Building Blocks for constructing programs http://www.flickr.com/photos/stevendepolo/5597111652 Monday, June 13, 2011 12
- 13. Functions as Glue for bonding functions http://www.flickr.com/photos/pseudoego/5417919481 Monday, June 13, 2011 13
- 14. A lot of programming languages available for functional programming http://www.flickr.com/photos/32712959@N07/3222623206 Monday, June 13, 2011 14
- 15. Monday, June 13, 2011 15
- 16. Monday, June 13, 2011 16
- 17. Monday, June 13, 2011 17
- 18. High-order Functions Monday, June 13, 2011 18
- 19. Monday, June 13, 2011 19
- 20. Monday, June 13, 2011 20
- 21. Haskell [ ] e.g. [] [1, 2, 3] (:) e.g. [1] => 1 : [] [1, 2, 3] => 1 : 2 : 3 : [] Monday, June 13, 2011 21
- 22. (:) LISP cons cons Haskell cons :: a -> [a] -> [a] -- cons x [] = [x] -- cons x1 (x2:xs) = x1 : (cons x2 xs) Monday, June 13, 2011 22
- 23. cons :: a -> [a] -> [a] -- cons x [] = [x] -- cons x1 (x2:xs) = x1 : (cons x2 xs) // C++ template <typename a> std::list<a> cons(a const& x, std::list<a> const& xs); Monday, June 13, 2011 23
- 24. cons :: a -> [a] -> [a] -- cons x [] = [x] -- cons x1 (x2:xs) = x1 : (cons x2 xs) e.g. cons 0 [1,2,3,4] => x1 0, x2 1, xs [2,3,4] Monday, June 13, 2011 24
- 25. (Int) sum sum :: [Int] -> Int sum [] = 0 sum (n:ns) = n + (sum ns) Monday, June 13, 2011 25
- 26. cons sum cons :: a -> [a] -> [a] cons x [] = [x] cons x1 (x2:xs) = x1 : (cons x2 xs) sum :: [Int] -> Int sum [] = 0 sum (n:ns) = n + (sum ns) Monday, June 13, 2011 26
- 27. cons x [] = [x] sum [] = 0 cons x1 (x2:xs) = x1 : (cons x2 xs) sum (n :ns) = n + (sum ns) Monday, June 13, 2011 27
- 28. (Int) product product :: [Int] -> Int product [] = 1 product (n:ns) = n * product ns Monday, June 13, 2011 28
- 29. cons x [] = [x] sum [] = 0 product [] = 1 cons x1 (x2:xs) = x1 : (cons x2 xs) sum (n :ns) = n + (sum ns) product (n :ns) = n * (product ns) Monday, June 13, 2011 29
- 30. (Bool) allTrue allTrue :: [Bool] -> Bool allTrue [] = True allTrue (b:bs) = b && allTrue ns Monday, June 13, 2011 30
- 31. (Bool) anyTrue anyTrue :: [Bool] -> Bool anyTrue [] = False anyTrue (b:bs) = b || anyTrue ns Monday, June 13, 2011 31
- 32. cons x [] = [x] sum [] = 0 product [] = 1 allTrue [] = True anyTrue [] = False cons x1 (x2:xs) = x1 : (cons x2 xs) sum (n :ns) = n + (sum ns) product (n :ns) = n * (product ns) allTrue (b :bs) = b && (allTrue bs) anyTrue (b :bs) = b || (anyTrue bs) Monday, June 13, 2011 32
- 33. cons x [] = [x] sum [] = 0 product [] = 1 allTrue [] = True anyTrue [] = False cons x1 (x2:xs) = x1 : (cons x2 xs) sum (n :ns) = n + (sum ns) product (n :ns) = n * (product ns) allTrue (b :bs) = b && (allTrue bs) anyTrue (b :bs) = b || (anyTrue bs) Monday, June 13, 2011 32
- 34. reduce :: (a -> [a] -> a) -> a -> [a] -> a reduce f x0 [] = x0 reduce f x0 (x1:xs) = f x1 (reduce f x0 xs) sum = reduce (+) 0 product = reduce (*) 1 allTrue = reduce (&&) True anyTrue = reduce (||) False Monday, June 13, 2011 33
- 35. reduce :: (a -> [a] -> a) -> a -> [a] -> a reduce f x0 [] = x0 reduce f x0 (x1:xs) = f x1 (reduce f x0 xs) sum = reduce (+) 0 product = reduce (*) 1 allTrue = reduce (&&) True anyTrue = reduce (||) False Monday, June 13, 2011 33
- 36. reduce :: (a -> [a] -> a) -> a -> [a] -> a reduce f x0 [] = x0 reduce f x0 (x1:xs) = f x1 (reduce f x0 xs) sum = reduce (+) 0 product = reduce (*) 1 allTrue = reduce (&&) True anyTrue = reduce (||) False Monday, June 13, 2011 33
- 37. reduce :: (a -> [a] -> a) -> a -> [a] -> a reduce f x0 [] = x0 reduce f x0 (x1:xs) = f x1 (reduce f x0 xs) sum = reduce (+) 0 product = reduce (*) 1 allTrue = reduce (&&) True anyTrue = reduce (||) False Monday, June 13, 2011 33
- 38. cons reduce append :: [a] -> [a] -> [a] append xs ys = reduce (:) ys xs append [1,2] [3,4] -> reduce (:) [3,4] [1,2] -> reduce (:) [3,4] (1:2:[]) -> 1 : (reduce (:) [3,4] (2:[])) -> 1 : 2 : (reduce (:) [3,4] []) -> 1 : 2 : [3,4] -> [1,2,3,4] Monday, June 13, 2011 34
- 39. Monday, June 13, 2011 35
- 40. Monday, June 13, 2011 36
- 41. Monday, June 13, 2011 37
- 42. Functions as Building Blocks for constructing programs http://www.flickr.com/photos/stevendepolo/5597111652 Monday, June 13, 2011 38
- 43. Functions as Glue for bonding functions http://www.flickr.com/photos/pseudoego/5417919481 Monday, June 13, 2011 39
- 44. Monday, June 13, 2011 40
- 45. -- Haskell reduce (+) 0 [1..10] // C++ int ns[] = {1,2,3,4,5,6,7,8,9,10}; std::accumulate(ns, ns + 10, 0, &std::plus<int>); # Ruby [*1..10].inject(0, :+) Monday, June 13, 2011 41
- 46. Monday, June 13, 2011 42
- 47. Lazy Evaluation Monday, June 13, 2011 43
- 48. Monday, June 13, 2011 44
- 49. Monday, June 13, 2011 45
- 52. http://weblog.raganwald.com/2007/03/why-why-functional-programming-matters.html Monday, June 13, 2011 48
- 53. language evaluation pureness Haskell lazy pure Concurrent Clean lazy pure OCaml strict impure F# strict impure Scheme strict impure Monday, June 13, 2011 49
- 54. language evaluation pureness Haskell lazy pure Concurrent Clean lazy pure OCaml strict impure F# strict impure Scheme strict impure Monday, June 13, 2011 50
- 55. Monday, June 13, 2011 51
- 56. Monday, 1 2010 3 June 13, 2011 52
- 57. Functional Programming Monday, June 13, 2011 53
- 58. A lot of programming languages available for functional programming http://www.flickr.com/photos/32712959@N07/3222623206 Monday, June 13, 2011 54
- 59. Monday, June 13, 2011 55
- 60. High-order Functions Monday, June 13, 2011 56
- 61. Functions as Building Blocks for constructing programs http://www.flickr.com/photos/stevendepolo/5597111652 Monday, June 13, 2011 57
- 62. Functions as Glue for bonding functions http://www.flickr.com/photos/pseudoego/5417919481 Monday, June 13, 2011 58
- 63. Lazy Evaluation Monday, June 13, 2011 59
- 64. Monday, June 13, 2011 60
Editor's Notes
- \n
- \n
- \n
- \n
- \n
- \n
- \n
- \n
- \n
- \n
- \n
- \n
- \n
- \n
- \n
- \n
- \n
- \n
- \n
- \n
- \n
- \n
- \n
- \n
- \n
- \n
- \n
- \n
- \n
- \n
- \n
- \n
- \n
- \n
- \n
- \n
- \n
- \n
- \n
- \n
- \n
- \n
- \n
- \n
- \n
- \n
- \n
- \n
- \n
- \n
- \n
- \n
- \n
- \n
- \n
- \n
- \n
- \n
- \n
- \n
- \n
- \n
- \n
- \n
- \n
- \n