Functional Programming Patterns

There are numerous patterns that anyone who wants to become a functional programmer needs to know. Without these patterns he will experience different forms of "stuckness". We use the underlying structure of the problems that we are trying to solve to uncover patterns that we can use to solve them.

The [GOF design patterns][https://en.wikipedia.org/wiki/Design_Patterns] are a good example of discovering structure in problems and codifying them into patterns.

Here we will review simple patterns that arise when solving problems using functional techniques. Becoming familiar with the patterns and understanding how they are used is a good start. Then depending on your aptitude/interest you can explore/learn the underlying mathematical structure.

The best way to explore some of these patterns are by looking at some interesting Programming problems. We can solve these problems using functional programming techniques.

Solving a version of the Expression Problem

The expression problem is very simple to state but solving this problem exposes some of the intricate properties of programming Languages.

Here is a concrete representation of the problem. Build a program that can evaluate mathematical expressions like ((3+5)*2).

Now notice that to solve this problem we need to support different operator types like +, - etc. And support the addition of new operators say *, / .

Additionally we have different ways to process an expression. For example we can either evaluate the expression or display the expression. We need to be able to support the addition of new ways to process expressions and also support the addition of new operators.

The solution shown below uses the following features of Elm:

• Algebraic Data types
• Expressions represented as recursive data structures
• Pattern matching is used to get type based dispatch
• Multiple processing functions (eval/render) for different behavior
• Recursion for Expression Tree traversal

import Graphics.Element exposing (..)

type Expr =
  Val Float
  |Add Expr Expr
  |Sub Expr Expr
  |Mul Expr Expr
  |Div Expr Expr

eval : Expr -> Float
eval aExpr =
  case aExpr of
    Val x -> x
    Add l r -> eval l + eval r
    Sub l r -> eval l - eval r
    Mul l r -> eval l * eval r
    Div l r -> eval l / eval r

display : Expr -> String
display aExpr =
  case aExpr of
    Val x -> toString x
    Add l r -> "(" ++ display l ++ "+"  ++ display r ++ ")"
    Sub l r -> "(" ++ display l ++ "-"  ++ display r ++ ")"
    Mul l r -> "(" ++ display l ++ "*"  ++ display r ++ ")"
    Div l r -> "(" ++ display l ++ "/"  ++ display r ++ ")"

--building an expression for ((3+5)*2)
aExpr : Expr
aExpr = (Mul (Add (Val 3) (Val 5)) (Val 2))

main =
  flow down [
              show ("display aExpr : " ++ (display aExpr ))
              ,print "eval aExpr : " (eval aExpr )
            ]

--a helper function to make display easier
print message value = show (message ++ (toString value))

Function Chains

Here are a couple of problems that we can solve using function chains. This is a very powerful and general procedure that allows us to build complex functionality out of smaller/simpler functions.

Find the sum of the square of the numbers in a list greater than a threshold value.

import Graphics.Element exposing (..)
import String exposing (toList)

-- for each element of the list take the second power
-- then filter out the elements that are greater than the threshold
-- the sum all the elements
processList threshold =
  List.map ((^)2)
  >> List.filter (\x -> x > threshold)
  >> List.foldr (+) 0

main =
  flow down [
              print "process list : " (processList 1 [1..100])
            ]
--a helper function to make display easier
print message value = show (message ++ (toString value))

Finding letter frequency in a string

Given a string find the letter frequency for letters in a given string.

import Graphics.Element exposing (..)
import List.Extra exposing (group)
import String exposing (toList)

--find the frequency of letters occurring in a string
findLetterFrequency : String -> List ( Maybe Char, Int )
findLetterFrequency str =
  List.Extra.group (String.toList str)
  |>List.map (\e -> ((List.head e), (List.length e)))

findLetterFrequency1 : String -> List ( Char, Int )
findLetterFrequency1 str =
  List.Extra.group (String.toList str)
  |>List.map (\e -> (extractChar (List.head e), (List.length e)))

extractChar : Maybe Char -> Char
extractChar m =
 case m of
  Just x -> x
  Nothing -> ' '

main =
  flow down [
              print "process list : " (processList 1 [1..10])
              ,print "process list : " (findLetterFrequency "hello")

            ]

--a helper function to make display easier
print message value = show (message ++ (toString value))

Newton's Method for finding roots

Let us see if we can write a program to find the nthRoots of a number. This program illustrates the power of combining iteration/recursion with function calls, to create powerful programs.

This is called Newton's method, named after Isaac Newton. Here is the code implementing Newton's method:

import Graphics.Element exposing (show, flow, down)
import List exposing (..)

until : (a -> Bool) -> (a -> a) -> a -> a
until p f x = case (p x) of
   True -> x
   False -> until p f (f x)

-- Newtons Method
deriv f x =
  let
    dx = 0.0001
  in  (f(x + dx) - f(x))/dx

newton f = let
             satis y = abs(f y) < eps
             eps = 0.0001
             improve y = y-(f y/deriv f y)
           in until satis improve

sqRtNewton x = let f y = y^2 - x
                in newton f x

cubeRtNewton x = let f y = y^3 - x
                in newton f x

main = flow down [
              print "square root of 2 using Newton's method : " (sqRtNewton 3)
             ,print "cube root of 2 using Newton's method : " (cubeRtNewton 3)
            ]

--a helper function to make display easier
print message value = show (message ++ (toString value))

Coins Change problem - Greedy Algorithm

Using Tuples

import Graphics.Element exposing (show, flow, down)
import List exposing (..)

coins = [100, 50, 25, 10, 1]
initialAmount = 46

initialData : (Int, List Int)
initialData = (initialAmount, [])

makeChange : (Int, List Int) -> List Int -> (Int, List Int)
makeChange data coins =
  foldl makeChangeForCoin data coins

makeChangeForCoin : Int -> (Int, List Int) -> (Int, List Int)
makeChangeForCoin  coin data=
  let remaining =  fst data%coin
      numCoins = fst data//coin
  in (remaining, numCoins:: snd data)

main = show ("Given the coins " ++ toString(coins) ++ "to make change for the amount: "  
            ++ toString(initialAmount) ++  " we need " ++
            (toString (makeChange  initialData coins |> snd |> reverse)))

Using Records

import Graphics.Element exposing (show, flow, down)
import List exposing (..)

coins =
 [100, 50, 25, 10, 1]

initialAmount =
 62

initialData :Data
initialData =
 {amount = initialAmount, coinsUsed = []}

type alias Data =
 {amount : Int, coinsUsed : List Int}

makeChange : Data -> List Int -> Data
makeChange data coins =
 foldl makeChangeForCoin data coins

makeChangeForCoin : Int -> Data -> Data
makeChangeForCoin  coin data =
 let
  remaining =  
   data.amount % coin
  numCoins =
   data.amount // coin
  in {data | amount =
               remaining
             ,coinsUsed =
               numCoins::data.coinsUsed}

computeAndDisplayChange : String
computeAndDisplayChange =
 makeChange initialData coins|> .coinsUsed |> reverse |> toString

main = show ("Given the coins " ++ toString(coins) ++ "to make change for the amount: "  
            ++ toString(initialAmount) ++  " we need " ++
            computeAndDisplayChange)