Functional Go

In this talk I discuss whether applying some of the principles of programming language to Go is possible or makes sense.

Can we build the Maybe and Many monads in Go? Well, yes!
Is it a good idea? Well, probably not

Presented at http://dotgo.eu 2015 in Paris

Transcript

1. Functional Go
2. Why would you do that?
3. quicksort [] = [] quicksort (x:xs) = let smaller = quicksort [a | a <- xs, a <= x] bigger = quicksort [a | a <- xs, a > x] in smaller ++ [x] ++ bigger Quicksort in Haskell
4. Live coding Andrew Sorensen Keynote at OSCON
5. What is functional programming?
6. Functional programming - no mutable state - functions as first class objects
7. No mutable state - simply a choice - no for loops
8. func SumI(vs []int) int { s := 0 for _, v := range vs { s += v } return v } Iterative sum
9. func SumI(vs []int) int { s := 0 for _, v := range vs { s += v } return v } Iterative fun is not functional
10. func SumR(vs []int) int { if len(vs) == 0 { return 0 } return vs[0] + Sum(vs[1:]) } Recursive sum
11. Is it fast? PASS BenchmarkSumI-4 3000000 462 ns/op BenchmarkSumR-4 300000 4707 ns/op
12. func SumTR(vs []int, s int) int { if len(vs) == 0 { return s } return Sum(vs[1:], s + vs[0]) } Tail recursion
13. PASS BenchmarkSumI-4 3000000 462 ns/op BenchmarkSumR-4 300000 4707 ns/op BenchmarkSumTR-4 300000 5056 ns/op Is it fast?
14. func SumTRG(vs []int, s int) int { begin: if len(vs) == 0 { return s } vs, s = vs[1:], s + vs[0] goto begin } Tail recursion with faked optimization
15. PASS BenchmarkSumI-4 3000000 462 ns/op BenchmarkSumR-4 300000 4707 ns/op BenchmarkSumTR-4 300000 5056 ns/op BenchmarkSumTRG-4 1000000 1587 ns/op Is it fast?
16. This is not about the speed, clearly
17. Functions are first class objects - as parameters - as returned values - in Go they can be used anywhere!
18. Functions applied on functions - map, filter, fold, etc High order functions
19. map ( ) → [ ] → [ ]
20. ( ) → [ ] → [ ] = int = bool
21. func Map(f func(v int) bool, vs []int) []bool { if len(vs) == 0 { return nil } return append( []bool{f(vs[0])}, Map(f, vs[1:])...) } Map on concrete types
22. func Map(f func(v int) bool, vs []int) []bool { if len(vs) == 0 { return nil } return append( Map(f, vs[:len(vs)-1]), vs[len(vs)-1]) } Map on concrete types (reversed order)
23. func main() { isEven := func(v int) bool { return v%2 == 0 } nums := []int{1, 2, 3, 4, 5, 6} fmt.Println(Map(isEven, nums)) // [false true false true false true] } Map on concrete types
24. template< , > func Map(f func(a ) , vs [] ) [] If Go had generics
25. func(a ) ⇒ interface{} [] ⇒ interface{} [] ⇒ interface{} But it doesn’t
26. func Map(f interface{}, vs interface{}) interface{}
27. func Map(f interface{}, vs interface{}) interface{}
28. “embrace the interface” but not too much
29. func Map(f interface{}, vs interface{}) interface{}
30. Representing functions type Func struct { in reflect.Type out reflect.Type f func(interface{}) interface{} } func (f Func) Call(v interface{}) interface{} { return f.f(v) }
31. func NewFunc(f interface{}) (*Func, error) { // check type of f and return an error if needed return &Func{ in: tf.In(0), out: tf.Out(0), f: func(x interface{}) interface{} { out := vf.Call([]reflect.Value{reflect.ValueOf(x)}) return out[0].Interface() }, }, nil } Representing functions: NewFunc
32. func Must(f *Func, err error) *Func { if err != nil { panic(err) } return f } Representing functions: Must
33. func Map(f interface{}, vs interface{}) interface{} func Map(f *Func, vs interface{}) interface{}
34. func Map(f *Func, vs interface{}) interface{}
35. type List struct { Head interface{} Tail *List } func Map(f *Func, l *List) *List { if l == nil { return nil } return &List{f.Call(l.Head), Map(f, l.Tail)} } A simple List
36. Should this be a method? Of what?
37. func (l *List) Map(f *Func) *List { if l == nil { return nil } return &List{ f.Call(l.Head), Map(f, l.Tail), } } Map in Go, as a method of List
38. toUpper := Must(NewFunc(strings.ToUpper)) m := &List{“hello”, &List{“bye”, nil}} res := m.Map(toUpper) fmt.Println(res) // “HELLO”, “BYE” Using map
39. typeclasses: an interlude
40. The Show typeclass class Show a where show :: a -> String
41. type Stringer interface { String() string } The Stringer interface
42. The Eq typeclass class Eq a where (==) :: a -> a -> Bool (/=) :: a -> a -> Bool
43. type Equatable interface { Equals(e Equatable) bool } satisfied by an Integer type func (i Integer) Equals(j Integer) bool The Equatable interface
44. typeclasses are “like” interfaces
45. What else can we map over?
46. Lists Maps Trees … What can we map over?
47. func (l *List) Map(f *Func) *List type Mapper interface { Map(*Func) ??? } Mapper interface
48. class Functor f a where fmap :: (a -> b) -> f a -> f b Functor typeclass
49. fmap ( ) → ( ) → ( )
50. A couple of useful functors
51. maybe
52. type Maybe struct { Value interface{} } func (m Maybe) Map(f *Func) Maybe { if m.Value == nil { return Maybe{} } return Maybe{ f.Call(m.Value) } } Maybe
53. Once we create a Func: toUpper := Must(NewFunc(strings.ToUpper)) We can call it with a value: m := Maybe{“hello”} res := m.Map(toUpper) fmt.Println(res.Value) // “HELLO” Maybe
54. Once we create a Func: toUpper := Must(NewFunc(strings.ToUpper)) Or without it: m := Maybe{} res := m.Map(toUpper) fmt.Println(res.Value) // <nil> Maybe
55. toUpper := Must(NewFunc(strings.ToUpper)) twice := Must(NewFunc(func(s string) string { return s+s })) m := Maybe{“hello”} res := m.Map(toUpper).Map(twice) fmt.Println(res.Value) // “HELLOHELLO” Maybe chained
56. An actual use case → → →⛅ person address city weather
57. type Person struct{ address *Address } type Address struct{ city *City } type City struct{ weather *Weather } type Weather struct{ desc string } func (p Person) Address() *Address { return p.address } func (a Address) City() *City { return a.city } func (c City) Weather() *Weather { return c.weather } func (w Weather) Desc() string { return w.desc } An actual use case
58. func (p Person) Weather() string { a := p.Address() if a == nil { return “no weather” } c := a.City() if c == nil { return “no weather” } w := c.Weather() if w == nil { return “no weather” } return w.Description() } An actual use case
59. func (p Person) Weather() string { m := Maybe{p}. Map(Must(NewFunc(func(p Person) *Address { return p.address }))). Map(Must(NewFunc(func(a Address) *City { return a.city }))). ... Maybe chained
60. We can obtain a function from a value: var p Person p.Address // func() *Address Or from a type Person.Address // func(Person) *Address Method values
61. func (p Person) Weather() string { w := Maybe{p}. Map(Must(NewFunc(Person.Address))). Map(Must(NewFunc(Address.City))). Map(Must(NewFunc(City.Weather))). Map(Must(NewFunc(Weather.Description))) if w.Value == nil { return “no weather” } return w.Value.(string) } Maybe chained
62. func (m Maybe) Do(fs ...interface{}) (Maybe, error) { if len(fs) == 0 { return m, nil } f, err := NewFunc(fs[0]) if err != nil { return Maybe{}, err } return m.Map(f).Do(fs[1:]...) } Chaining map with Maybe.Do
63. func (p Person) Weather() string { w := Maybe{p}.Do( Person.Address, Address.City, City.Weather, Weather.Description) if w.Value == nil { return “no weather” } return w.Value.(string) } Chaining map with Maybe.Do
64. many
65. type Many struct { Head interface{} Tail *Many } Many
66. func (m *Many) Map(f *Func) *Many { if m == nil { return nil } res := m.Tail.Map(f) // append all elements from the result for _, v := range toSlice(f.Call(m.Head)) { r = &Many{v, res} } return res } Many
67. Once we create a Func: toUpper := Must(NewFunc(strings.ToUpper)) We can call it with a value: m := Many{“hello there”, “good bye”} res := m.Map(toUpper) fmt.Println(res.Value) // “HELLO THERE”, “GOOD BYE” Many
68. If we have a new function: toUpper := Must(NewFunc(strings.ToUpper)) fields := Must(NewFunc(strings.Fields)) Or without it: m := Many{“hello there”, “good bye”} res := m.Map(toUpper).Map(fields) fmt.Println(res.Value) // “HELLO”, “THERE”, “GOOD”, “BYE” Many chained
69. An actual use case → → →〰 library books pages lines
70. type Library struct{ books []Book } type Book struct{ pages []Page } type Page struct{ lines []Line } type Line struct{ text string } func (l Library) Books() []Book { return l.books } func (b Book) Pages() []Page { return b.pages } func (p Page) Lines() []Line { return p.lines } func (l Line) Text() string { return l.text } An actual use case
71. An actual use case words := make(map[string]int) for _, b := range l.Books() { for _, p := range b.Pages() { for _, l := range p.Lines() { for _, word := range strings.Fields(l.Text()) { words[word]++ } } } }
72. NewMany(l). Map(Must(NewFunc(Library.Books))). Map(Must(NewFunc(Book.Pages))). Map(Must(NewFunc(Page.Lines))). Map(Must(NewFunc(Line.Text))). Map(Must(NewFunc(strings.Fields))). Map(Must(NewFunc(func(s string) bool { count[s]++; return true }))) Many chained
73. Many Do _, err := NewMany(m).Do( Library.Books, Book.Pages, Page.Lines, Line.Text, strings.Field, func(s string) bool { count[s]++; return true }) if err != nil { // type error }
74. Many Do w, err := NewMany(m). Do( Library.Books, Book.Pages, Page.Lines, Line.Text, strings.Field) if err != nil { // type error } w.Each(func(s string) { count[s]++ })
75. Functional Go - Doable - but slower than normal code - requires reflection - Inspiration for good APIs - functors to abstract function application - what could we do with monads?
76. @francesc Merci
77. Composition of functions func Compose(f, g *Func) (*Func, error) { if g.out != f.in { return nil, fmt.Errorf("can't compose: %v != %v", g.out, f.in) } return &Func{ g.in, f.out, func(x interface{}) interface{} { return f.Call(g.Call(x)) }, }, nil }
78. func (m Maybe) Map(f *Func) Maybe { if m.Value == nil { return Maybe{} } r := f.Call(m.Value) vr := reflect.ValueOf(r) if vr.Kind() == reflect.Ptr && vr.IsNil() { return Maybe{} } return Maybe{r} } Mapping over a Maybe and handling nil pointers