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

The Power of Composition

The Power of Composition

Composition is a fundamental principle of functional programming, but how is it different from an object-oriented approach, and how do you use it in practice?

In this talk for beginners, we'll start by going over the basic concepts of functional programming, and then look at some different ways that composition can be used to build large things from small things.

After that, we'll see how composition is used in practice, beginning with a simple FizzBuzz example, and ending with a complete (object-free!) web application.

Scott Wlaschin

June 11, 2020
Tweet

More Decks by Scott Wlaschin

Other Decks in Programming

Transcript

  1. The Power Of Composition 1. The philosophy of composition 2.

    Ideas of functional programming – Functions and how to compose them – Types and how to compose them 3. Composition in practice – Roman Numerals – FizzBuzz gone functional – Uh oh, monads! – A web service
  2. Prerequisites for understanding composition • You must have been a

    child at some point • You must have played with Lego • You must have played with toy trains
  3. Lego Philosophy 1. All pieces are designed to be connected

    2. The pieces are reusable in many contexts 3. Connect two pieces together and get another "piece" that can still be connected
  4. Wooden Railway Track Philosophy 1. All pieces are designed to

    be connected 2. The pieces are reusable in many contexts 3. Connect two pieces together and get another "piece" that can still be connected
  5. Connect two pieces together and get another "piece" that can

    still be connected You can keep adding and adding.
  6. Four ideas behind FP Function 3. Types are not classes

    1. Functions are things 2. Build bigger functions using composition 4. Build bigger types using composition
  7. The Tunnel of Transformation Function apple -> banana A function

    is a thing which transforms inputs to outputs
  8. A function is a standalone thing, not attached to a

    class It can be used for inputs and outputs of other functions
  9. New Function apple -> cherry Can't tell it was built

    from smaller functions! Where did the banana go?
  10. int add1(int x) => x + 1; int times2(int x)

    => x * 2; int square(int x) => x * x; add1(5); // = 6 times2(add1(5)); // = 12 square(times2(add1(5))); // = 144 Nested function calls can be confusing if too deep
  11. 5 |> add1 // = 6 5 |> add1 |>

    times2 // = 12 5 |> add1 |> times2 |> square // = 144 add1 times2 square 5 6 12 144 F# example
  12. Low-level operation Service AddressValidator A “Service” is just like a

    microservice but without the "micro" in front Validation Result Address Low-level operation Low-level operation
  13. So, what is a type then? A type is a

    just a name for a set of things Set of valid inputs Set of valid outputs Function
  14. Set of valid inputs Set of valid outputs Function 1

    2 3 4 5 6 This is type "integer" A type is a just a name for a set of things
  15. Set of valid inputs Set of valid outputs Function This

    is type "string" "abc" "but" "cobol" "double" "end" "float" A type is a just a name for a set of things
  16. Set of valid inputs Set of valid outputs Function This

    is type "Person" Donna Roy Javier Mendoza Nathan Logan Shawna Ingram Abel Ortiz Lena Robbins Gordon Wood A type is a just a name for a set of things
  17. Set of valid inputs Set of valid outputs Function This

    is type "Fruit" A type is a just a name for a set of things
  18. Set of valid inputs Set of valid outputs Function This

    is a type of Fruit->Fruit functions A type is a just a name for a set of things
  19. Compose with “AND” enum AppleVariety { Red, Green } enum

    BananaVariety { Yellow, Brown } enum CherryVariety { Tart, Sweet } struct FruitSalad { AppleVariety Apple; BananaVariety Banana; CherryVariety Cherry; } C# example Apple AND Banana AND Cherry
  20. Compose with “AND” type AppleVariety = Red | Green type

    BananaVariety = Yellow | Brown type CherryVariety = Tart | Sweet type FruitSalad = { Apple: AppleVariety Banana: BananaVariety Cherry: CherryVariety } F# example
  21. Snack = OR OR Compose with “OR” type Snack =

    | Apple of AppleVariety | Banana of BananaVariety | Cherry of CherryVariety
  22. Some requirements: We accept three forms of payment: Cash, Paypal,

    or CreditCard. For Cash we don't need any extra information For Paypal we need an email address For Cards we need a card type and card number
  23. interface IPaymentMethod {..} class Cash() : IPaymentMethod {..} class Paypal(string

    emailAddress): IPaymentMethod {..} class Card(string cardType, string cardNo) : IPaymentMethod {..} In OO design you would probably implement it as an interface and a set of subclasses, like this:
  24. type EmailAddress = string type CardNumber = string In F#

    you would probably implement by composing types, like this:
  25. type EmailAddress = ... type CardNumber = … type CardType

    = Visa | Mastercard type CreditCardInfo = { CardType : CardType CardNumber : CardNumber }
  26. type EmailAddress = ... type CardNumber = ... type CardType

    = ... type CreditCardInfo = ... type PaymentMethod = | Cash | PayPal of EmailAddress | Card of CreditCardInfo
  27. type EmailAddress = ... type CardNumber = ... type CardType

    = ... type CreditCardInfo = ... type PaymentMethod = | Cash | PayPal of EmailAddress | Card of CreditCardInfo type PaymentAmount = decimal type Currency = EUR | USD | RUB
  28. type EmailAddress = ... type CardNumber = ... type CardType

    = ... type CreditCardInfo = ... type PaymentMethod = | Cash | PayPal of EmailAddress | Card of CreditCardInfo type PaymentAmount = decimal type Currency = EUR | USD | RUB type Payment = { Amount : PaymentAmount Currency : Currency Method : PaymentMethod }
  29. type EmailAddress = ... type CardNumber = ... type CardType

    = ... type CreditCardInfo = ... type PaymentMethod = | Cash | PayPal of EmailAddress | Card of CreditCardInfo type PaymentAmount = decimal type Currency = EUR | USD | RUB type Payment = { Amount : PaymentAmount Currency : Currency Method : PaymentMethod }
  30. type Deal = Deck -> (Deck * Card) type PickupCard

    = (Hand * Card) -> Hand type Suit = Club | Diamond | Spade | Heart type Rank = Two | Three | Four | Five | Six | Seven | Eight | Nine | Ten | Jack | Queen | King | Ace type Card = { Suit:Suit; Rank:Rank } type Hand = Card list type Deck = Card list type Player = {Name:string; Hand:Hand} type Game = { Deck:Deck; Players:Player list } The domain on one screen!
  31. type CardType = Visa | Mastercard type CardNumber = string

    type EmailAddress = string type PaymentMethod = | Cash | PayPal of EmailAddress | Card of CreditCardInfo | Bitcoin of BitcoinAddress
  32. A big topic and not enough time   More

    on DDD and designing with types at fsharpforfunandprofit.com/ddd
  33. To Roman Numerals • Task: How to convert an arabic

    integer to roman numerals? • 5 => "V" • 12 => "XII" • 107 => "CVII"
  34. To Roman Numerals • Use the "tally" approach – Start

    with N copies of "I" – Replace five "I"s with a "V" – Replace two "V"s with a "X" – Replace five "X"s with a "L" – Replace two "L"s with a "C" – etc
  35. string ToRomanNumerals(int number) { // define a helper function for

    each step string replace_IIIII_V(string s) => s.Replace("IIIII", "V"); string replace_VV_X(string s) => s.Replace("VV", "X"); string replace_XXXXX_L(string s) => s.Replace("XXXXX", "L"); string replace_LL_C(string s) => s.Replace("LL", "C"); // then combine them using piping return new string('I', number) .Pipe(replace_IIIII_V) .Pipe(replace_VV_X) .Pipe(replace_XXXXX_L) .Pipe(replace_LL_C); } C# example
  36. let toRomanNumerals number = // define a helper function for

    each step let replace_IIIII_V str = replace "IIIII" "V" str let replace_VV_X str = replace "VV" "X" str let replace_XXXXX_L str = replace "XXXXX" "L" str let replace_LL_C str = replace "LL" "C" str // then combine them using piping String.replicate number "I" |> replace_IIIII_V |> replace_VV_X |> replace_XXXXX_L |> replace_LL_C F# example
  37. function A Input Output function B Input 1 Output Input

    2 Challenge #1: How can we compose these? 
  38. Input A Uncurried Function Input B Output C Curried Function

    Input A Intermediate Function Output C Input B What is currying? after currying Function as output
  39. Input A Uncurried Function Input B Output C Curried Function

    Input A Intermediate Function Output C Input B What is currying? One input One input Currying means that *every* function can be converted to a series of one input functions
  40. Replace Old New Old New After currying Func<string,string> replace(string oldVal,

    string newVal) => input => input.Replace(oldVal, newVal);
  41. Replace Old New Old New After currying Func<string,string> replace(string oldVal,

    string newVal) => input => input.Replace(oldVal, newVal);
  42. Func<string,string> replace(string oldVal, string newVal) => input => input.Replace(oldVal, newVal);

    Replace Old New Old New After currying This lambda (function) is returned one-parameter function
  43. string ToRomanNumerals(int number) { // define a general helper function

    Func<string,string> replace( string oldValue, string newValue) => input => input.Replace(oldValue, newValue); // then use piping return new string('I', number) .Pipe(replace("IIIII","V")) .Pipe(replace("VV","X")) .Pipe(replace("XXXXX","L")) .Pipe(replace("LL","C")); } C# example
  44. string ToRomanNumerals(int number) { // define a general helper function

    Func<string,string> replace( string oldValue, string newValue) => input => input.Replace(oldValue, newValue); // then use piping return new string('I', number) .Pipe(replace("IIIII","V")) .Pipe(replace("VV","X")) .Pipe(replace("XXXXX","L")) .Pipe(replace("LL","C")); } C# example
  45. string ToRomanNumerals(int number) { // define a general helper function

    Func<string,string> replace( string oldValue, string newValue) => input => input.Replace(oldValue, newValue); // then use piping return new string('I', number) .Pipe(replace("IIIII","V")) .Pipe(replace("VV","X")) .Pipe(replace("XXXXX","L")) .Pipe(replace("LL","C")); } C# example Only 2 of the 3 parameters are passed in The other parameter comes from the pipeline
  46. let toRomanNumerals number = // no helper function needed. //

    currying occurs automatically in F# // combine using piping String.replicate number "I" |> replace "IIIII" "V" |> replace "VV" "X" |> replace "XXXXX" "L" |> replace "LL" "C" F# example
  47. let toRomanNumerals number = // no helper function needed. //

    currying occurs automatically in F# // combine using piping String.replicate number "I" |> replace "IIIII" "V" |> replace "VV" "X" |> replace "XXXXX" "L" |> replace "LL" "C" Only 2 of the 3 parameters are passed in F# example The other parameter comes from the pipeline
  48. Partial Application let add x y = x + y

    let multiply x y = x * y 5 |> add 2 |> multiply 3 Piping provides the missing argument partial application
  49. Partial Application Replace ReplaceOldNew Old New Old New String.replicate number

    "I" |> replace "IIIII" "V" |> replace "VV" "X" |> replace "XXXXX" "L" |> replace "LL" "C" Only 2 parameters passed in Piping provides the missing argument
  50. let toRomanNumerals number = String.replicate number "I" |> replace "IIIII"

    "V" |> replace "VV" "X" |> replace "XXXXX" "L" |> replace "LL" "C" Composable => extensible // can easily add new segments to the pipeline |> replace "VIIII" "IX" |> replace "IIII" "IV" |> replace "LXXXX" "XC"
  51. function A Input Output function B Input Output 1 Output

    2 Challenge #2: How can we compose these? 
  52. FizzBuzz definition Write a program that takes a number as

    input • For multiples of three print "Fizz" • For multiples of five print "Buzz" • For multiples of both three and five print "FizzBuzz" • Otherwise, print the original number
  53. let fizzBuzz n = if (isDivisibleBy n 15) then printfn

    "FizzBuzz" else if (isDivisibleBy n 3) then printfn "Fizz" else if (isDivisibleBy n 5) then printfn "Buzz" else printfn "%i" n let isDivisibleBy n divisor = (n % divisor) = 0 // helper function A simple F# implementation
  54. let fizzBuzz n = if (isDivisibleBy n 15) then printfn

    "FizzBuzz" else if (isDivisibleBy n 3) then printfn "Fizz" else if (isDivisibleBy n 5) then printfn "Buzz" else printfn "%i" n let isDivisibleBy n divisor = (n % divisor) = 0 // helper function A simple F# implementation
  55. Unhandled Handled Input -> type FizzBuzzResult = | Unhandled of

    int // the original int | Handled of string // "Fizz", Buzz", etc Idea from http://weblog.raganwald.com/2007/01/dont-overthink-fizzbuzz.html or
  56. type FizzBuzzResult = | Unhandled of int // the original

    int | Handled of string // "Fizz", Buzz", etc let handle divisor label n = if (isDivisibleBy n divisor) then Handled label else Unhandled n Idea from http://weblog.raganwald.com/2007/01/dont-overthink-fizzbuzz.html
  57. type FizzBuzzResult = | Unhandled of int // the original

    int | Handled of string // "Fizz", Buzz", etc let handle divisor label n = if (isDivisibleBy n divisor) then Handled label else Unhandled n
  58. 12 |> handle 3 "Fizz" // Handled "Fizz" 10 |>

    handle 3 "Fizz" // Unhandled 10 10 |> handle 5 "Buzz" // Handled "Buzz" handle 5 "Buzz"
  59. let fizzbuzz n = let result15 = n |> handle

    15 "FizzBuzz" match result15 with | Handled str -> str | Unhandled n -> let result3 = n |> handle 3 "Fizz" match result3 with | Handled str -> str | Unhandled n -> let result5 = n |> handle 5 "Buzz" match result5 with | Handled str -> str | Unhandled n -> string n // convert to string First implementation attempt
  60. let fizzbuzz n = let result15 = n |> handle

    15 "FizzBuzz" match result15 with | Handled str -> str | Unhandled n -> let result3 = n |> handle 3 "Fizz" match result3 with | Handled str -> str | Unhandled n -> let result5 = n |> handle 5 "Buzz" match result5 with | Handled str -> str | Unhandled n -> // do something with Unhandled value
  61. let fizzbuzz n = let result15 = n |> handle

    15 "FizzBuzz" match result15 with | Handled str -> str | Unhandled n -> let result3 = n |> handle 3 "Fizz" match result3 with | Handled str -> str | Unhandled n -> // do something with Unhandled value // ... // ...
  62. let fizzbuzz n = let result15 = n |> handle

    15 "FizzBuzz" match result15 with | Handled str -> str | Unhandled n -> // do something with Unhandled value // ... // ...
  63. let ifUnhandledDo f result = match result with | Handled

    str -> Handled str | Unhandled n -> f n
  64. let fizzbuzz n = n |> handle 15 "FizzBuzz" |>

    ifUnhandledDo (handle 3 "Fizz") |> ifUnhandledDo (handle 5 "Buzz") |> lastStep
  65. let fizzbuzz n = n |> handle 15 "FizzBuzz" |>

    ifUnhandledDo (handle 3 "Fizz") |> ifUnhandledDo (handle 5 "Buzz") |> lastStep
  66. let fizzbuzz n = n |> handle 15 "FizzBuzz" |>

    ifUnhandledDo (handle 3 "Fizz") |> ifUnhandledDo (handle 5 "Buzz") |> lastStep
  67. let fizzbuzz n = n |> handle 15 "FizzBuzz" |>

    ifUnhandledDo (handle 3 "Fizz") |> ifUnhandledDo (handle 5 "Buzz") |> lastStep
  68. let fizzbuzz n = n |> handle 15 "FizzBuzz" |>

    ifUnhandledDo (handle 3 "Fizz") |> ifUnhandledDo (handle 5 "Buzz") |> lastStep let lastStep result = match result with | Handled str -> str | Unhandled n -> string(n) // convert to string
  69. let fizzbuzz n = n |> handle 15 "FizzBuzz" |>

    ifUnhandledDo (handle 3 "Fizz") |> ifUnhandledDo (handle 5 "Buzz") |> lastStep Composable => easy to extend
  70. let fizzbuzz n = n |> handle 15 "FizzBuzz" |>

    ifUnhandledDo (handle 3 "Fizz") |> ifUnhandledDo (handle 5 "Buzz") |> ifUnhandledDo (handle 7 "Baz") |> lastStep Composable => easy to extend
  71. let fizzbuzz n = n |> handle 15 "FizzBuzz" |>

    ifUnhandledDo (handle 3 "Fizz") |> ifUnhandledDo (handle 5 "Buzz") |> ifUnhandledDo (handle 7 "Baz") |> ifUnhandledDo (handle 11 "Pozz") |> lastStep Composable => easy to extend
  72. let fizzbuzz n = n |> handle 15 "FizzBuzz" |>

    ifUnhandledDo (handle 3 "Fizz") |> ifUnhandledDo (handle 5 "Buzz") |> ifUnhandledDo (handle 7 "Baz") |> ifUnhandledDo (handle 11 "Pozz") |> ifUnhandledDo (handle 13 "Tazz") |> lastStep Composable => easy to extend
  73. let taskExample input = let taskX = startTask input taskX.WhenFinished

    (fun x -> let taskY = startAnotherTask x taskY.WhenFinished (fun y -> let taskZ = startThirdTask y taskZ.WhenFinished (fun z -> etc
  74. let taskExample input = let taskX = startTask input taskX.WhenFinished

    (fun x -> let taskY = startAnotherTask x taskY.WhenFinished (fun y -> let taskZ = startThirdTask y taskZ.WhenFinished (fun z -> do something
  75. let taskExample input = let taskX = startTask input taskX.WhenFinished

    (fun x -> let taskY = startAnotherTask x taskY.WhenFinished (fun y -> do something
  76. let whenFinishedDo f task = task.WhenFinished (fun taskResult -> f

    taskResult) let taskExample input = startTask input |> whenFinishedDo startAnotherTask |> whenFinishedDo startThirdTask |> whenFinishedDo ... Parameterize the next step
  77. let bind nextFunction result = match result with | Unhandled

    n -> nextFunction n | Handled str -> Handled str Two-track input Two-track output
  78. let bind nextFunction result = match result with | Unhandled

    n -> nextFunction n | Handled str -> Handled str Two-track input Two-track output
  79. let bind nextFunction result = match result with | Unhandled

    n -> nextFunction n | Handled str -> Handled str Two-track input Two-track output
  80. let bind nextFunction result = match result with | Unhandled

    n -> nextFunction n | Handled str -> Handled str Two-track input Two-track output
  81. let bind nextFunction result = match result with | Unhandled

    n -> nextFunction n | Handled str -> Handled str Two-track input Two-track output
  82. FP terminology • A monad is – A data type

    – With an associated "bind" function – (and some other stuff) • A monadic function is – A switch/points function – "bind" is used to compose them type FizzBuzzResult = | Unhandled of int | Handled of string
  83. function A Input Output function B Input Output 1 Output

    2 Challenge #2: How can we compose these? 
  84. = >=> The result is another HttpHandler so you can

    keep adding and adding Composition of HttpHandlers Kleisli composition symbol
  85. choose [ path "/hello" >=> OK "Hello" path "/goodbye" >=>

    OK "Goodbye" ] Pick first path that succeeds
  86. let app = choose [ ] startWebServer defaultConfig app A

    complete web app GET >=> choose [ path "/hello" >=> OK "Hello" path "/goodbye" >=> OK "Goodbye" ] POST >=> choose [ path "/hello" >=> OK "Hello POST" path "/goodbye" >=> OK "Goodbye POST" ]
  87. Review • The philosophy of composition – Connectable, reusable parts

    – Building bigger things from smaller things • FP principles: – Composable functions – Composable types
  88. Review A taste of various composition techniques: – Piping with

    "|>" – Currying/partial application – Composition using "bind" (monads!) – Kleisli composition using ">=>" Don't worry about understanding it all, but hopefully it's not so scary now!
  89. Why bother? Benefits of composition: • Reusable parts – no

    strings attached • Testable – parts can be tested in isolation • Understandable – data flows in one direction • Maintainable – all dependencies are explicit • Extendable – can add new parts without touching old code • A different way of thinking – it's good for your brain to learn new things!