Thinking Functionally in Ruby

A talk about functional programming in general and Ruby's Enumerable module in particular.

Given at the October 2009 LRUG meeting (http://lrug.org/meetings/2009/09/18/october-2009-meeting/). There's a video of this talk at http://skillsmatter.com/podcast/ajax-ria/enumerators.

Transcript

1. THINKING FUNCTIONALLY IN RUBY. @tomstuart
2. Functional programming is a pretty neat idea. 1:
3. Enumerable contains some useful methods. 2:
4. I hope these things are connected.
5. (Functional programming is a pretty neat idea) 1.
6. What is functional programming?
7. A programming style.
8. Two broad families of languages:
9. 1. Lisp-like •Scheme •Common Lisp •Dylan •Clojure •Dynamically typed •Homoiconic (code is data) •Lists are fundamental
10. 2. ML-like •Standard ML •Haskell •OCaml •Scala (sort of) •Statically typed (+ reconstruction) •Code is not data •ADTs and pattern matching
11. Functions as values
12. What is a function?
16. 1 7 2 3 6 4 5 4 2 6 8 3 7 1
17. Functions as values
18. “First-class functions” Implies: higher-order functions “closures”, “lambdas”, “anonymous functions”
19. No side effects
20. Values are immutable All functions do is return their result No state No I/O
21. (In reality, different languages accomplish this to varying degrees.)
22. Implies: recursion Implies: persistent data structures
23. So what?
24. Unfortunately...
25. Declarative programming is counterintuitive when youʼre accustomed to imperative programming WHAT! HOW!
26. Copying is expensive
27. But!
28. Referential transparency “an expression can be replaced with its value” • Good for efficiency • caching/memoisation/inlining • ultimately more efficient • Good for programmer understanding • state is incredibly hard to deal with • ultimately more intuitive • Good for code reuse and testing
29. Highly expressive Deeply satisfying Strongly compositional
30. Future-proof •Mooreʼs Law is running out of steam •similar transistor density, more cores •The futureʼs concurrent •Concurrent access to mutable state is hard... •but not if you donʼt have mutable state! •Parallelising an algorithm is hard... •but itʼs easier if your code isnʼt overspecified
31. OK seriously: so what?
32. Ruby can do some of this. Not really a functional language, but we can pretend and get some of the benefits.
33. Use function values lambda { |x| x + 1 } blocks, procs
34. Consider treating your values as immutable State is rarely worth it. It will kill you in the end.
35. http://clojure.org/state
36. Use the functional-flavoured parts of the standard library
37. Be declarative. Think functionally. What, not how.
38. 2. (Enumerable contains some useful methods)
39. Enumerable#zip
40. [1, 2, 3, 4]. zip([5, 6, 7, 8]) [1, 2, 3, 4]. zip([5, 6, 7, 8])
41. 2 1 3 4 6 5 7 8
42. 2 1 3 4 6 5 7 8
43. [ ] 2 1 3 4 6 5 7 8 [ ] , , , , [ ] [ ] [ ] , , ,
44. [1, 2, 3, 4]. zip([5, 6, 7, 8], [9, 10, 11, 12])
45. Enumerable#select (a.k.a. #find_all)
46. { |x| x.odd? }
47. 1 1 ?
48. 1 1 ? !
49. 1 1 ? ! 2 2 ?
50. 1 1 ? ! 2 2 ? "
51. [1, 2, 3, 4]. select { |x| x.odd? }
52. 1 2 3 4 2 1 3 4 ? ? ? ?
53. 1 2 3 4 2 1 3 4 ? ? ? ? ! " " !
54. 1 3 1 3 ? ? ! ! 1 3
55. 1 3 [ ] ,
56. Enumerable#partition
57. [1, 2, 3, 4]. partition { |x| x.odd? }
58. 1 2 3 4 2 1 3 4 ? ? ? ?
59. 1 2 3 4 2 1 3 4 ? ? ? ? ! " " !
60. 1 ? ! 4 ? " 2 ? " 3 ? !
61. 1 ? ! 4 ? " 2 ? " 3 ? ! 1 3 2 4
62. 1 3 [ ] , 2 4 [ ] , , [ ]
63. Enumerable#map (a.k.a. #collect)
64. { |x| x * 3 }
65. 2 2 6 ×3
66. 2 2 6 ×3
67. [1, 2, 3, 4]. map { |x| x * 3 }
68. 1 2 3 4 2 1 3 4 6 3 9 12 ×3 ×3 ×3 ×3
69. 1 2 3 4 2 1 3 4 6 3 9 12 ×3 ×3 ×3 ×3
70. 6 3 9 12 [ ] , , ,
71. Enumerable#inject (a.k.a. #reduce)
72. { |x, y| x + y }
73. 3 3 5 5 8 +
74. 3 3 5 5 8 +
75. [1, 2, 3, 4]. inject(0) { |x,y| x+y } [1, 2, 3, 4]. inject(0) { |x,y| x+y }
76. 1 2 3 4 1 2 3 4 0 1 3 6 10 + + + +
77. 1 1 2 3 3 6 4 0 1 2 3 4 0 1 3 6 10 + + + +
78. module Enumerable def inject(initial) result = initial for element in self result = yield(result, element) end result end end
79. a.k.a. “left fold” (foldl, fold_left)
80. 1 2 3 4 0
81. 10 (((0 + 1) + 2) + 3) + 4
82. ...versus “right fold” (foldr, fold_right)
83. 1 2 3 4 0
84. 10 1 + (2 + (3 + (4 + 0)))
85. The initial argument is optional...
86. [1, 2, 3, 4]. inject { |x,y| x+y }
87. [1, 2, 3, 4]. inject { |x,y| x+y } [2, 3, 4]. inject(1) { |x,y| x+y }
88. ...but only if the output is the same type as the input...
89. >> ['El', 'rug']. inject(0) { |l,s| l + s.length } => 5 >> ['El', 'rug']. inject { |l,s| l + s.length } TypeError: can't convert Fixnum into String from (irb):1:in `+' from (irb):1 from (irb):1:in `inject' from (irb):1:in `each' from (irb):1:in `inject' from (irb):1
90. ...and itʼs meaningful to get nil when the collection is empty
91. >> [].inject { |x,y| x+y } => nil >> [].inject(0) { |x,y| x+y } => 0 >> [].inject(1) { |x,y| x*y } => 1
92. COMPOSE!
93. [1, 2, 3, 4]. map { |x| x * 3 }. inject(0) { |x| x+y }
94. 1 2 3 4 2 1 3 4 6 3 9 12 ×3 ×3 ×3 ×3 0 0 3 9 18 30 + + + +
95. 3 6 9 12 1 2 3 4 2 1 3 4 6 3 9 12 ×3 ×3 ×3 ×3 3 9 18 0 0 3 9 18 30 + + + +
96. I am so excited. What now?
97. Review your Ruby code. Func it up.
98. result = '' for name in names unless result.empty? result << ', ' end result << name end result
99. result = '' for name in names unless result.empty? result << ', ' end result << name end result names.join(', ') !
100. def count_mines_near(x, y) count = 0 for i in x-1..x+1 for j in y-1..y+1 count += 1 if mine_at?(i, j) end end count end
101. def count_mines_near(x, y) count = 0 for i in x-1..x+1 for j in y-1..y+1 count += 1 if mine_at?(i, j) end end count end def count_mines_near(x, y) ((x-1..x+1).entries * 3).sort. zip((y-1..y+1).entries * 3). select { |x, y| mine_at?(x, y) }. length end !
102. def count_mines_near(x, y) ((x-1..x+1).entries * 3).sort. zip((y-1..y+1).entries * 3). select { |x, y| mine_at?(x, y) }. length end [1, 2, 3, 1, 2, 3, 1, 2, 3] [1, 1, 1, 2, 2, 2, 3, 3, 3] .sort = # = (2, 8)
103. def count_mines_near(x, y) ((x-1..x+1).entries * 3).sort. zip((y-1..y+1).entries * 3). select { |x, y| mine_at?(x, y) }. length end [1, 2, 3, 1, 2, 3, 1, 2, 3] [1, 1, 1, 2, 2, 2, 3, 3, 3] [7, 8, 9, 7, 8, 9, 7, 8, 9] [[1, 7], [1, 8], [1, 9], [2, 7], [2, 8], [2, 9], [3, 7], [3, 8], [3, 9]] .sort = .zip( ) = # = (2, 8)
104. def count_mines_near(x, y) ((x-1..x+1).entries * 3).sort. zip((y-1..y+1).entries * 3). select { |x, y| mine_at?(x, y) }. length end [1, 2, 3, 1, 2, 3, 1, 2, 3] [1, 1, 1, 2, 2, 2, 3, 3, 3] [7, 8, 9, 7, 8, 9, 7, 8, 9] [[1, 7], [1, 8], [1, 9], [2, 7], [2, 8], [2, 9], [3, 7], [3, 8], [3, 9]] .sort = .zip( ) = .select {…} = [[1, 8], [3, 7]] .length = 2 # = (2, 8)
105. def count_mines_near(x, y) ((x-500..x+500).entries * 1001).sort. zip((y-500..y+500).entries * 1001). select { |x, y| mine_at?(x, y) }. length end [ [1, 7], [1, 8], …, [1, 1007], [2, 7], [2, 8], …, [2, 1007], …, …, …, [1000, 7], [1000, 8], …, [1000, 1007], [1001, 7], [1000, 8], …, [1001, 1007]]
106. [ [1, 7], [1, 8], …, [1, 1007], [2, 7], [2, 8], …, [2, 1007], …, …, …, [1000, 7], [1000, 8], …, [1000, 1007], [1001, 7], [1000, 8], …, [1001, 1007]] 173 96 121 78 237 705
107. def numbers_near(n, radius) ((n - radius)..(n + radius)).entries end def squares_near(x, y, radius) diameter = (radius * 2) + 1 (numbers_near(x, radius) * diameter). sort. zip(numbers_near(y, radius) * diameter) end def count_mines_near(x, y, radius = 1) squares_near(x, y, radius). select { |x, y| mine_at?(x, y) }. length end
108. Learn a functional language •OCaml •Scheme (Google “SICP”) •Clojure •Scala •Haskell? Erlang?
109. Thanks! @tomstuart / tom@experthuman.com
110. http://www.flickr.com/photos/somemixedstuff/2403249501/ http://en.wikipedia.org/wiki/File:Modified-pc-case.png