Functional Patterns: Composition and Implicitness

This is part 2 of a series of articles entitled Functional Patterns.

Make sure to check out the rest of the articles!

The Monoid

Partial Application

Often we talk about currying in an imperative context, it seems unnecessary as it is extra overhead just to be able to deal with multiple arguments.

After all, why should you write a => b => a + b when you can write it with (a, b) => a + b?

And the reason is the main power of currying patterns: Partial Application.

In a non-curried declaration we can really only have:


<span># Python </span>
<span>def</span> <span>add</span><span>(</span><span>a</span><span>,</span> <span>b</span><span>):</span>
    <span>return</span> <span>a</span> <span>+</span> <span>b</span>
<span>print</span><span>(</span><span>add</span><span>(</span><span>4</span><span>,</span> <span>5</span><span>))</span>    <span># 9 </span><span>print</span><span>(</span><span>add</span><span>(</span><span>4</span><span>,</span> <span>3</span><span>))</span>    <span># 7 </span>
<span># Python </span>
<span>def</span> <span>add</span><span>(</span><span>a</span><span>,</span> <span>b</span><span>):</span>
    <span>return</span> <span>a</span> <span>+</span> <span>b</span>

<span>print</span><span>(</span><span>add</span><span>(</span><span>4</span><span>,</span> <span>5</span><span>))</span>    <span># 9 </span><span>print</span><span>(</span><span>add</span><span>(</span><span>4</span><span>,</span> <span>3</span><span>))</span>    <span># 7 </span>
# Python 
def add(a, b):
    return a + b

print(add(4, 5))    # 9 print(add(4, 3))    # 7

Enter fullscreen mode Exit fullscreen mode

But because curried functions return us another function, we can decide to keep it in a partially-applied state.


<span>def</span> <span>add</span><span>(</span><span>a</span><span>):</span>
    <span>return</span> <span>lambda</span> <span>b</span><span>:</span> <span>a</span> <span>+</span> <span>b</span>
<span>print</span><span>(</span><span>add</span><span>(</span><span>4</span><span>)(</span><span>5</span><span>))</span>    <span># 9 </span>
<span># or ... </span>
<span>add4</span> <span>=</span> <span>add</span><span>(</span><span>4</span><span>)</span>       <span># A function that takes 1 argument and adds 4 </span>                    <span># It's a `partially-applied` version of the original `add` function. </span>
<span>print</span><span>(</span><span>add4</span><span>(</span><span>5</span><span>))</span>      <span># 9 </span><span>print</span><span>(</span><span>add4</span><span>(</span><span>3</span><span>))</span>      <span># 7 </span>
<span>def</span> <span>add</span><span>(</span><span>a</span><span>):</span>
    <span>return</span> <span>lambda</span> <span>b</span><span>:</span> <span>a</span> <span>+</span> <span>b</span>

<span>print</span><span>(</span><span>add</span><span>(</span><span>4</span><span>)(</span><span>5</span><span>))</span>    <span># 9 </span>
<span># or ... </span>
<span>add4</span> <span>=</span> <span>add</span><span>(</span><span>4</span><span>)</span>       <span># A function that takes 1 argument and adds 4 </span>                    <span># It's a `partially-applied` version of the original `add` function. </span>
<span>print</span><span>(</span><span>add4</span><span>(</span><span>5</span><span>))</span>      <span># 9 </span><span>print</span><span>(</span><span>add4</span><span>(</span><span>3</span><span>))</span>      <span># 7 </span>
def add(a):
    return lambda b: a + b

print(add(4)(5))    # 9 
# or ... 
add4 = add(4)       # A function that takes 1 argument and adds 4                     # It's a `partially-applied` version of the original `add` function. 
print(add4(5))      # 9 print(add4(3))      # 7

Enter fullscreen mode Exit fullscreen mode

Since arguments are handled in separate functions, we can pre-apply some arguments that might fit our use-case without having to rewrite similar logic.


<span>def</span> <span>resize_image</span><span>(</span><span>image_type</span><span>):</span>
    <span>def</span> <span>resize</span><span>(</span><span>image</span><span>,</span> <span>x</span><span>,</span> <span>y</span><span>):</span>
        <span># some extra logic </span>        <span>return</span> <span>resized_image</span>
    <span>if</span> <span>image_type</span> <span>==</span> <span>"</span><span>svg</span><span>"</span><span>:</span>
        <span># some extra logic </span>
    <span>return</span> <span>resize</span>
<span>resize_svg</span>  <span>=</span> <span>resize</span><span>(</span><span>"</span><span>svg</span><span>"</span><span>)</span>
<span>resize_png</span>  <span>=</span> <span>resize</span><span>(</span><span>"</span><span>png</span><span>"</span><span>)</span>
<span>resize_jpg</span>  <span>=</span> <span>resize</span><span>(</span><span>"</span><span>jpg</span><span>"</span><span>)</span>
<span># ... </span>
<span>def</span> <span>resize_image</span><span>(</span><span>image_type</span><span>):</span>
    <span>def</span> <span>resize</span><span>(</span><span>image</span><span>,</span> <span>x</span><span>,</span> <span>y</span><span>):</span>
        <span># some extra logic </span>        <span>return</span> <span>resized_image</span>

    <span>if</span> <span>image_type</span> <span>==</span> <span>"</span><span>svg</span><span>"</span><span>:</span>
        <span># some extra logic </span>
    <span>return</span> <span>resize</span>

<span>resize_svg</span>  <span>=</span> <span>resize</span><span>(</span><span>"</span><span>svg</span><span>"</span><span>)</span>
<span>resize_png</span>  <span>=</span> <span>resize</span><span>(</span><span>"</span><span>png</span><span>"</span><span>)</span>
<span>resize_jpg</span>  <span>=</span> <span>resize</span><span>(</span><span>"</span><span>jpg</span><span>"</span><span>)</span>
<span># ... </span>
def resize_image(image_type):
    def resize(image, x, y):
        # some extra logic         return resized_image

    if image_type == "svg":
        # some extra logic 
    return resize

resize_svg  = resize("svg")
resize_png  = resize("png")
resize_jpg  = resize("jpg")
# ...

Enter fullscreen mode Exit fullscreen mode

And now we pretty much have a Builder pattern minus all of the disgusting OOP.

Composition and Combinators

In the functional style, complexity comes from simple functions composed together.


<span>reverse</span><span>(</span><span>map</span><span>(</span><span>lambda</span> <span>a</span><span>:</span> <span>a</span><span>*</span><span>a</span><span>,</span> <span>[</span><span>4</span><span>,</span><span>5</span><span>,</span><span>3</span><span>,</span><span>2</span><span>]))</span>
<span># or ... </span>
<span>reverse</span><span>([</span><span>a</span><span>*</span><span>a</span> <span>for</span> <span>a</span> <span>in</span> <span>[</span><span>4</span><span>,</span><span>5</span><span>,</span><span>3</span><span>,</span><span>2</span><span>]])</span>
<span>reverse</span><span>(</span><span>map</span><span>(</span><span>lambda</span> <span>a</span><span>:</span> <span>a</span><span>*</span><span>a</span><span>,</span> <span>[</span><span>4</span><span>,</span><span>5</span><span>,</span><span>3</span><span>,</span><span>2</span><span>]))</span>

<span># or ... </span>
<span>reverse</span><span>([</span><span>a</span><span>*</span><span>a</span> <span>for</span> <span>a</span> <span>in</span> <span>[</span><span>4</span><span>,</span><span>5</span><span>,</span><span>3</span><span>,</span><span>2</span><span>]])</span>
reverse(map(lambda a: a*a, [4,5,3,2]))

# or ... 
reverse([a*a for a in [4,5,3,2]])

Enter fullscreen mode Exit fullscreen mode

Here we are squaring all the numbers in an array, and then reversing the resulting array. When we find ourselves saying “and then” after describing what a function does, this is already actually composition! And in a functional paradigm, that’s pretty much where all the logic happens, in composition.

Moreover, the type of composition you’re probably most accustomed to is actually, what we call a combinator.

Combinators (from the field of mathematics called lambda calculus, and eventually combinatory logic [which is different from combinatorics!]) are patterns which describe the way you are to compose functions together.

In fact, this manner of composition is called the Bluebird (or B-Combinator). The definition is as follows:


<span>// javascript for terse lambdas</span>
<span>B</span> <span>=</span> <span>f</span> <span>=></span> <span>g</span> <span>=></span> <span>a</span> <span>=></span> <span>f</span><span>(</span><span>g</span><span>(</span><span>a</span><span>))</span>
<span>// javascript for terse lambdas</span>
<span>B</span> <span>=</span> <span>f</span> <span>=></span> <span>g</span> <span>=></span> <span>a</span> <span>=></span> <span>f</span><span>(</span><span>g</span><span>(</span><span>a</span><span>))</span>
// javascript for terse lambdas
B = f => g => a => f(g(a))

Enter fullscreen mode Exit fullscreen mode

And it checks out, the g function is applied first to a, then f is applied to its result!

Let’s see an example of the B-combinator in use.


<span>B</span> <span>=</span> <span>lambda</span> <span>f</span><span>:</span> <span>lambda</span> <span>g</span><span>:</span> <span>lambda</span> <span>a</span><span>:</span> <span>f</span><span>(</span><span>g</span><span>(</span><span>a</span><span>))</span>
<span># curried map </span><span>c_map</span> <span>=</span> <span>lambda</span> <span>f</span><span>:</span> <span>lambda</span> <span>a</span><span>:</span> <span>map</span><span>(</span><span>f</span><span>,</span> <span>a</span><span>)</span>
<span># our original composition </span><span>reverse</span><span>(</span><span>map</span><span>(</span><span>lambda</span> <span>a</span><span>:</span> <span>a</span><span>*</span><span>a</span><span>,</span> <span>[</span><span>4</span><span>,</span><span>5</span><span>,</span><span>3</span><span>,</span><span>2</span><span>]))</span>
<span># The same expression written with the Bluebird # (spaces are added for clarity) </span><span>B </span><span>(</span><span>reverse</span><span>)</span> <span>(</span><span>c_map</span><span>(</span><span>lambda</span><span>:</span> <span>a</span><span>*</span><span>a</span><span>))</span> <span>([</span><span>4</span><span>,</span> <span>5</span><span>,</span> <span>3</span><span>,</span> <span>2</span><span>])</span>
<span>B</span> <span>=</span> <span>lambda</span> <span>f</span><span>:</span> <span>lambda</span> <span>g</span><span>:</span> <span>lambda</span> <span>a</span><span>:</span> <span>f</span><span>(</span><span>g</span><span>(</span><span>a</span><span>))</span>

<span># curried map </span><span>c_map</span> <span>=</span> <span>lambda</span> <span>f</span><span>:</span> <span>lambda</span> <span>a</span><span>:</span> <span>map</span><span>(</span><span>f</span><span>,</span> <span>a</span><span>)</span>

<span># our original composition </span><span>reverse</span><span>(</span><span>map</span><span>(</span><span>lambda</span> <span>a</span><span>:</span> <span>a</span><span>*</span><span>a</span><span>,</span> <span>[</span><span>4</span><span>,</span><span>5</span><span>,</span><span>3</span><span>,</span><span>2</span><span>]))</span>

<span># The same expression written with the Bluebird # (spaces are added for clarity) </span><span>B </span><span>(</span><span>reverse</span><span>)</span> <span>(</span><span>c_map</span><span>(</span><span>lambda</span><span>:</span> <span>a</span><span>*</span><span>a</span><span>))</span> <span>([</span><span>4</span><span>,</span> <span>5</span><span>,</span> <span>3</span><span>,</span> <span>2</span><span>])</span>
B = lambda f: lambda g: lambda a: f(g(a))

# curried map c_map = lambda f: lambda a: map(f, a)

# our original composition reverse(map(lambda a: a*a, [4,5,3,2]))

# The same expression written with the Bluebird # (spaces are added for clarity) B (reverse) (c_map(lambda: a*a)) ([4, 5, 3, 2])

Enter fullscreen mode Exit fullscreen mode

And let’s add on another combinator called the Thrush combinator, which is pretty useless in imperative programming. All it does is apply a function f to a value a.


<span>T</span> <span>=</span> <span>f</span> <span>=></span> <span>a</span> <span>=></span> <span>f</span><span>(</span><span>a</span><span>)</span>
<span>T</span> <span>=</span> <span>f</span> <span>=></span> <span>a</span> <span>=></span> <span>f</span><span>(</span><span>a</span><span>)</span>
T = f => a => f(a)

Enter fullscreen mode Exit fullscreen mode

However, this is an important building block in a pure and lazy functional language such as Haskell, as it allows us to evaluate the function f first, before applying it.

And now we should be able to read all common Haskell syntax!


<span>-- B-Combinator</span>
<span>(</span><span>.</span><span>)</span> <span>::</span> <span>(</span><span>b</span> <span>-></span> <span>c</span><span>)</span> <span>-></span> <span>(</span><span>a</span> <span>-></span> <span>b</span><span>)</span> <span>-></span> <span>a</span> <span>-></span> <span>c</span>
<span>(</span><span>.</span><span>)</span> <span>f</span> <span>g</span> <span>a</span> <span>=</span> <span>f</span> <span>(</span><span>g</span> <span>a</span><span>)</span>
<span>-- T-Combinator</span>
<span>(</span><span>$</span><span>)</span> <span>::</span> <span>(</span><span>a</span> <span>-></span> <span>b</span><span>)</span> <span>-></span> <span>a</span> <span>-></span> <span>b</span>
<span>(</span><span>$</span><span>)</span> <span>f</span> <span>a</span> <span>=</span> <span>f</span> <span>a</span>
<span>infixr</span> <span>0</span> <span>$</span>  <span>-- the left argument is evaluated first</span>
<span>-- infix versions of functions have the first argument on the left, and the second on the right</span>
<span>-- f . g == (.) f g</span>
<span>ans</span> <span>::</span> <span>[</span><span>Int</span><span>]</span>
<span>ans</span> <span>=</span> <span>reverse</span> <span>.</span> <span>map</span> <span>(</span><span>\</span><span>a</span> <span>-></span> <span>a</span><span>*</span><span>a</span><span>)</span> <span>$</span> <span>[</span><span>4</span><span>,</span> <span>5</span><span>,</span> <span>3</span><span>,</span> <span>2</span><span>]</span>
<span>-- B-Combinator</span>
<span>(</span><span>.</span><span>)</span> <span>::</span> <span>(</span><span>b</span> <span>-></span> <span>c</span><span>)</span> <span>-></span> <span>(</span><span>a</span> <span>-></span> <span>b</span><span>)</span> <span>-></span> <span>a</span> <span>-></span> <span>c</span>
<span>(</span><span>.</span><span>)</span> <span>f</span> <span>g</span> <span>a</span> <span>=</span> <span>f</span> <span>(</span><span>g</span> <span>a</span><span>)</span>

<span>-- T-Combinator</span>
<span>(</span><span>$</span><span>)</span> <span>::</span> <span>(</span><span>a</span> <span>-></span> <span>b</span><span>)</span> <span>-></span> <span>a</span> <span>-></span> <span>b</span>
<span>(</span><span>$</span><span>)</span> <span>f</span> <span>a</span> <span>=</span> <span>f</span> <span>a</span>
<span>infixr</span> <span>0</span> <span>$</span>  <span>-- the left argument is evaluated first</span>

<span>-- infix versions of functions have the first argument on the left, and the second on the right</span>
<span>-- f . g == (.) f g</span>
<span>ans</span> <span>::</span> <span>[</span><span>Int</span><span>]</span>
<span>ans</span> <span>=</span> <span>reverse</span> <span>.</span> <span>map</span> <span>(</span><span>\</span><span>a</span> <span>-></span> <span>a</span><span>*</span><span>a</span><span>)</span> <span>$</span> <span>[</span><span>4</span><span>,</span> <span>5</span><span>,</span> <span>3</span><span>,</span> <span>2</span><span>]</span>
-- B-Combinator
(.) :: (b -> c) -> (a -> b) -> a -> c
(.) f g a = f (g a)

-- T-Combinator
($) :: (a -> b) -> a -> b
($) f a = f a
infixr 0 $  -- the left argument is evaluated first

-- infix versions of functions have the first argument on the left, and the second on the right
-- f . g == (.) f g
ans :: [Int]
ans = reverse . map (\a -> a*a) $ [4, 5, 3, 2]

Enter fullscreen mode Exit fullscreen mode

Okay, well maybe not all syntax, but from inference, we can see where the combinators are used:

The B-Combinator composes reverse and a curried map
The T-Combinator applies the composed function to the array [4, 5, 3, 2]

Even more Combinators!

Composition happens so much in functional programming that mathematicians way smarter than us have actually written down and coined recurring patterns as even more combinators.

Combinators are called combinators because most of them are derived from combining other combinators.

Here are 3 combinators that are notable in my opinion (the rest is left for curious readers to read up on :>).

The Phi Combinator


<span>phi</span> <span>=</span> <span>f</span> <span>=></span> <span>g</span> <span>=></span> <span>h</span> <span>=></span> <span>a</span> <span>=></span> <span>f </span><span>(</span><span>g</span><span>(</span><span>a</span><span>))</span> <span>(</span><span>h</span><span>(</span><span>a</span><span>))</span>
<span>phi</span> <span>=</span> <span>f</span> <span>=></span> <span>g</span> <span>=></span> <span>h</span> <span>=></span> <span>a</span> <span>=></span> <span>f </span><span>(</span><span>g</span><span>(</span><span>a</span><span>))</span> <span>(</span><span>h</span><span>(</span><span>a</span><span>))</span>
phi = f => g => h => a => f (g(a)) (h(a))

Enter fullscreen mode Exit fullscreen mode

Function f is called with the arguments g(a) and h(a), or the result of calling g and h on a value a separately.

A great example of this pattern would be the average function.


<span>phi</span> <span>=</span> <span>lambda</span> <span>f</span><span>:</span> <span>lambda</span> <span>g</span><span>:</span> <span>lambda</span> <span>h</span><span>:</span> <span>lambda</span> <span>a</span><span>:</span> <span>f </span><span>(</span><span>g</span><span>(</span><span>a</span><span>))</span> <span>(</span><span>h</span><span>(</span><span>a</span><span>))</span>
<span>a</span> <span>=</span> <span>[</span><span>1</span><span>,</span> <span>2</span><span>,</span> <span>3</span><span>,</span> <span>4</span><span>,</span> <span>5</span><span>]</span>
<span>div</span> <span>=</span> <span>lambda</span> <span>a</span><span>:</span> <span>lambda</span> <span>b</span><span>:</span> <span>a</span> <span>/</span> <span>b</span>     <span># helper division function </span>
<span>print</span><span>(</span> <span>sum</span><span>(</span><span>a</span><span>)</span> <span>/</span> <span>len</span><span>(</span><span>b</span><span>)</span> <span>)</span>            <span># we can see the pattern emerge here </span>                                    <span># if we think of division as a function </span>
<span>average</span> <span>=</span> <span>phi </span><span>(</span><span>div</span><span>)</span> <span>(</span><span>sum</span><span>)</span> <span>(</span><span>len</span><span>)</span> <span>(</span><span>a</span><span>)</span>
<span>print</span><span>(</span><span>average</span><span>)</span>
<span>phi</span> <span>=</span> <span>lambda</span> <span>f</span><span>:</span> <span>lambda</span> <span>g</span><span>:</span> <span>lambda</span> <span>h</span><span>:</span> <span>lambda</span> <span>a</span><span>:</span> <span>f </span><span>(</span><span>g</span><span>(</span><span>a</span><span>))</span> <span>(</span><span>h</span><span>(</span><span>a</span><span>))</span>

<span>a</span> <span>=</span> <span>[</span><span>1</span><span>,</span> <span>2</span><span>,</span> <span>3</span><span>,</span> <span>4</span><span>,</span> <span>5</span><span>]</span>

<span>div</span> <span>=</span> <span>lambda</span> <span>a</span><span>:</span> <span>lambda</span> <span>b</span><span>:</span> <span>a</span> <span>/</span> <span>b</span>     <span># helper division function </span>
<span>print</span><span>(</span> <span>sum</span><span>(</span><span>a</span><span>)</span> <span>/</span> <span>len</span><span>(</span><span>b</span><span>)</span> <span>)</span>            <span># we can see the pattern emerge here </span>                                    <span># if we think of division as a function </span>
<span>average</span> <span>=</span> <span>phi </span><span>(</span><span>div</span><span>)</span> <span>(</span><span>sum</span><span>)</span> <span>(</span><span>len</span><span>)</span> <span>(</span><span>a</span><span>)</span>
<span>print</span><span>(</span><span>average</span><span>)</span>
phi = lambda f: lambda g: lambda h: lambda a: f (g(a)) (h(a))

a = [1, 2, 3, 4, 5]

div = lambda a: lambda b: a / b     # helper division function 
print( sum(a) / len(b) )            # we can see the pattern emerge here                                     # if we think of division as a function 
average = phi (div) (sum) (len) (a)
print(average)

Enter fullscreen mode Exit fullscreen mode


<span>-- haskell</span>
<span>import</span> <span>Control.Applicative</span>
<span>-- liftA2 is Haskell's phi combinator</span>
<span>average</span> <span>=</span> <span>liftA2</span> <span>div</span> <span>sum</span> <span>length</span> <span>[</span><span>1</span> <span>..</span> <span>5</span><span>]</span>
<span>-- haskell</span>
<span>import</span> <span>Control.Applicative</span>

<span>-- liftA2 is Haskell's phi combinator</span>
<span>average</span> <span>=</span> <span>liftA2</span> <span>div</span> <span>sum</span> <span>length</span> <span>[</span><span>1</span> <span>..</span> <span>5</span><span>]</span>
-- haskell
import Control.Applicative

-- liftA2 is Haskell's phi combinator
average = liftA2 div sum length [1 .. 5]

Enter fullscreen mode Exit fullscreen mode

The Psi Combinator


<span>psi</span> <span>=</span> <span>f</span> <span>=></span> <span>g</span> <span>=></span> <span>a</span> <span>=></span> <span>b</span> <span>=></span> <span>f </span><span>(</span><span>g</span><span>(</span><span>a</span><span>))</span> <span>(</span><span>g</span><span>(</span><span>b</span><span>))</span>
<span>psi</span> <span>=</span> <span>f</span> <span>=></span> <span>g</span> <span>=></span> <span>a</span> <span>=></span> <span>b</span> <span>=></span> <span>f </span><span>(</span><span>g</span><span>(</span><span>a</span><span>))</span> <span>(</span><span>g</span><span>(</span><span>b</span><span>))</span>
psi = f => g => a => b => f (g(a)) (g(b))

Enter fullscreen mode Exit fullscreen mode

Function f is called with the arguments g(a) and g(b), or the result of calling g on value a and b separately.

There are two good examples that come to mind.


<span>// javascript</span>
<span>psi</span> <span>=</span> <span>f</span> <span>=></span> <span>g</span> <span>=></span> <span>a</span> <span>=></span> <span>b</span> <span>=></span> <span>f </span><span>(</span><span>g</span><span>(</span><span>a</span><span>))</span> <span>(</span><span>g</span><span>(</span><span>b</span><span>))</span>
<span>eq</span> <span>=</span> <span>a</span> <span>=></span> <span>b</span> <span>=></span> <span>a</span> <span>==</span> <span>b</span>   <span>// helper function for checking equality</span>
<span>// A simple way to compare arrays in javascript is to turn *both* of them into strings first.</span>
<span>a</span> <span>=</span> <span>[</span><span>2</span><span>,</span> <span>3</span><span>,</span> <span>4</span><span>]</span>
<span>b</span> <span>=</span> <span>[</span><span>3</span><span>,</span> <span>4</span><span>,</span> <span>5</span><span>]</span>
<span>console</span><span>.</span><span>log</span><span>(</span> <span>JSON</span><span>.</span><span>stringify</span><span>(</span><span>a</span><span>)</span> <span>==</span> <span>JSON</span><span>.</span><span>stringify</span><span>(</span><span>b</span><span>)</span> <span>)</span>
<span>console</span><span>.</span><span>log</span><span>(</span> <span>psi </span><span>(</span><span>eq</span><span>)</span> <span>(</span><span>JSON</span><span>.</span><span>stringify</span><span>)</span> <span>(</span><span>a</span><span>)</span> <span>(</span><span>b</span><span>)</span> <span>)</span>
<span>// The distance formula has you square *both* differences first, and then sqrt the sum.</span>
<span>distanceFormula</span> <span>=</span> <span>(</span><span>x2</span><span>,</span> <span>x1</span><span>,</span> <span>y2</span><span>,</span> <span>y1</span><span>)</span> <span>=></span> <span>{</span>
    <span>return</span> <span>psi </span><span>(</span><span>a</span> <span>=></span> <span>b</span> <span>=></span> <span>Math</span><span>.</span><span>sqrt</span><span>(</span><span>a</span> <span>+</span> <span>b</span><span>))</span> <span>(</span><span>a</span> <span>=></span> <span>a</span> <span>*</span> <span>a</span><span>)</span> <span>(</span><span>x2</span> <span>-</span> <span>x1</span><span>)</span> <span>(</span><span>y2</span> <span>-</span> <span>y1</span><span>))</span>
<span>}</span>
<span>// javascript</span>
<span>psi</span> <span>=</span> <span>f</span> <span>=></span> <span>g</span> <span>=></span> <span>a</span> <span>=></span> <span>b</span> <span>=></span> <span>f </span><span>(</span><span>g</span><span>(</span><span>a</span><span>))</span> <span>(</span><span>g</span><span>(</span><span>b</span><span>))</span>

<span>eq</span> <span>=</span> <span>a</span> <span>=></span> <span>b</span> <span>=></span> <span>a</span> <span>==</span> <span>b</span>   <span>// helper function for checking equality</span>

<span>// A simple way to compare arrays in javascript is to turn *both* of them into strings first.</span>
<span>a</span> <span>=</span> <span>[</span><span>2</span><span>,</span> <span>3</span><span>,</span> <span>4</span><span>]</span>
<span>b</span> <span>=</span> <span>[</span><span>3</span><span>,</span> <span>4</span><span>,</span> <span>5</span><span>]</span>

<span>console</span><span>.</span><span>log</span><span>(</span> <span>JSON</span><span>.</span><span>stringify</span><span>(</span><span>a</span><span>)</span> <span>==</span> <span>JSON</span><span>.</span><span>stringify</span><span>(</span><span>b</span><span>)</span> <span>)</span>

<span>console</span><span>.</span><span>log</span><span>(</span> <span>psi </span><span>(</span><span>eq</span><span>)</span> <span>(</span><span>JSON</span><span>.</span><span>stringify</span><span>)</span> <span>(</span><span>a</span><span>)</span> <span>(</span><span>b</span><span>)</span> <span>)</span>

<span>// The distance formula has you square *both* differences first, and then sqrt the sum.</span>
<span>distanceFormula</span> <span>=</span> <span>(</span><span>x2</span><span>,</span> <span>x1</span><span>,</span> <span>y2</span><span>,</span> <span>y1</span><span>)</span> <span>=></span> <span>{</span>
    <span>return</span> <span>psi </span><span>(</span><span>a</span> <span>=></span> <span>b</span> <span>=></span> <span>Math</span><span>.</span><span>sqrt</span><span>(</span><span>a</span> <span>+</span> <span>b</span><span>))</span> <span>(</span><span>a</span> <span>=></span> <span>a</span> <span>*</span> <span>a</span><span>)</span> <span>(</span><span>x2</span> <span>-</span> <span>x1</span><span>)</span> <span>(</span><span>y2</span> <span>-</span> <span>y1</span><span>))</span>
<span>}</span>
// javascript
psi = f => g => a => b => f (g(a)) (g(b))

eq = a => b => a == b   // helper function for checking equality

// A simple way to compare arrays in javascript is to turn *both* of them into strings first.
a = [2, 3, 4]
b = [3, 4, 5]

console.log( JSON.stringify(a) == JSON.stringify(b) )

console.log( psi (eq) (JSON.stringify) (a) (b) )

// The distance formula has you square *both* differences first, and then sqrt the sum.
distanceFormula = (x2, x1, y2, y1) => {
    return psi (a => b => Math.sqrt(a + b)) (a => a * a) (x2 - x1) (y2 - y1))
}

Enter fullscreen mode Exit fullscreen mode


<span>-- haskell</span>
<span>import</span> <span>Data.Function</span>
<span>-- `on` is Haskell's infix version of Psi</span>
<span>eqArr</span> <span>=</span> <span>((</span><span>==</span><span>)</span> <span>`</span><span>on</span><span>`</span> <span>show</span><span>)</span> <span>[</span><span>2</span><span>,</span><span>3</span><span>,</span><span>4</span><span>]</span> <span>[</span><span>3</span><span>,</span><span>4</span><span>,</span><span>5</span><span>]</span>
<span>distanceFormula</span> <span>x2</span> <span>x1</span> <span>y2</span> <span>y1</span> <span>=</span> <span>(</span><span>sqrt</span> <span>.:</span> <span>((</span><span>+</span><span>)</span> <span>`</span><span>on</span><span>`</span> <span>(</span><span>^</span><span>2</span><span>)))</span> <span>(</span><span>x2</span> <span>-</span> <span>x1</span><span>)</span> <span>(</span><span>y2</span> <span>-</span> <span>y1</span><span>)</span>
<span>-- haskell</span>
<span>import</span> <span>Data.Function</span>

<span>-- `on` is Haskell's infix version of Psi</span>
<span>eqArr</span> <span>=</span> <span>((</span><span>==</span><span>)</span> <span>`</span><span>on</span><span>`</span> <span>show</span><span>)</span> <span>[</span><span>2</span><span>,</span><span>3</span><span>,</span><span>4</span><span>]</span> <span>[</span><span>3</span><span>,</span><span>4</span><span>,</span><span>5</span><span>]</span>

<span>distanceFormula</span> <span>x2</span> <span>x1</span> <span>y2</span> <span>y1</span> <span>=</span> <span>(</span><span>sqrt</span> <span>.:</span> <span>((</span><span>+</span><span>)</span> <span>`</span><span>on</span><span>`</span> <span>(</span><span>^</span><span>2</span><span>)))</span> <span>(</span><span>x2</span> <span>-</span> <span>x1</span><span>)</span> <span>(</span><span>y2</span> <span>-</span> <span>y1</span><span>)</span>
-- haskell
import Data.Function

-- `on` is Haskell's infix version of Psi
eqArr = ((==) `on` show) [2,3,4] [3,4,5]

distanceFormula x2 x1 y2 y1 = (sqrt .: ((+) `on` (^2))) (x2 - x1) (y2 - y1)

Enter fullscreen mode Exit fullscreen mode

The Starling (S-Combinator)


<span>s</span> <span>=</span> <span>f</span> <span>=></span> <span>g</span> <span>=></span> <span>a</span> <span>=></span> <span>f </span><span>(</span><span>a</span><span>)</span> <span>(</span><span>g</span><span>(</span><span>a</span><span>))</span>
<span>s</span> <span>=</span> <span>f</span> <span>=></span> <span>g</span> <span>=></span> <span>a</span> <span>=></span> <span>f </span><span>(</span><span>a</span><span>)</span> <span>(</span><span>g</span><span>(</span><span>a</span><span>))</span>
s = f => g => a => f (a) (g(a))

Enter fullscreen mode Exit fullscreen mode

Function f is called with the arguments a and g(a), the result of calling g on value a.

For the ones with keen eyes, you can already probably notice that the S-Combinator is actually just a special form of the Phi combinator. And that’s because it is. Specifically, it is the Phi combinator with g as the identity function (or the I-Combinator) defined as:


<span>i</span> <span>=</span> <span>a</span> <span>=></span> <span>a</span>          <span>// the identity combinator simply returns its argument</span>
<span>s</span> <span>=</span> <span>f</span> <span>=></span> <span>g</span> <span>=></span> <span>a</span> <span>=></span> <span>phi </span><span>(</span><span>f</span><span>)</span> <span>(</span><span>i</span><span>)</span> <span>(</span><span>g</span><span>)</span> <span>(</span><span>a</span><span>)</span>
<span>i</span> <span>=</span> <span>a</span> <span>=></span> <span>a</span>          <span>// the identity combinator simply returns its argument</span>

<span>s</span> <span>=</span> <span>f</span> <span>=></span> <span>g</span> <span>=></span> <span>a</span> <span>=></span> <span>phi </span><span>(</span><span>f</span><span>)</span> <span>(</span><span>i</span><span>)</span> <span>(</span><span>g</span><span>)</span> <span>(</span><span>a</span><span>)</span>
i = a => a          // the identity combinator simply returns its argument

s = f => g => a => phi (f) (i) (g) (a)

Enter fullscreen mode Exit fullscreen mode

A great example would be checking if a string is a palindrome, wherein we compare a string to its reverse.


<span># python </span><span>s</span> <span>=</span> <span>lambda</span> <span>f</span><span>:</span> <span>lambda</span> <span>g</span><span>:</span> <span>lambda</span> <span>a</span><span>:</span> <span>f </span><span>(</span><span>a</span><span>)</span> <span>(</span><span>g</span><span>(</span><span>a</span><span>))</span>
<span>eq</span> <span>=</span> <span>lambda</span> <span>a</span><span>:</span> <span>lambda</span> <span>b</span><span>:</span> <span>a</span> <span>==</span> <span>b</span>     <span># curried helper </span>
<span>s </span><span>(</span><span>eq</span><span>)</span> <span>(</span><span>reverse</span><span>)</span> <span>(</span><span>"</span><span>racecar</span><span>"</span><span>)</span>
<span># python </span><span>s</span> <span>=</span> <span>lambda</span> <span>f</span><span>:</span> <span>lambda</span> <span>g</span><span>:</span> <span>lambda</span> <span>a</span><span>:</span> <span>f </span><span>(</span><span>a</span><span>)</span> <span>(</span><span>g</span><span>(</span><span>a</span><span>))</span>

<span>eq</span> <span>=</span> <span>lambda</span> <span>a</span><span>:</span> <span>lambda</span> <span>b</span><span>:</span> <span>a</span> <span>==</span> <span>b</span>     <span># curried helper </span>
<span>s </span><span>(</span><span>eq</span><span>)</span> <span>(</span><span>reverse</span><span>)</span> <span>(</span><span>"</span><span>racecar</span><span>"</span><span>)</span>
# python s = lambda f: lambda g: lambda a: f (a) (g(a))

eq = lambda a: lambda b: a == b     # curried helper 
s (eq) (reverse) ("racecar")

Enter fullscreen mode Exit fullscreen mode


<span>-- haskell</span>
<span>ans</span> <span>::</span> <span>Bool</span>
<span>ans</span> <span>=</span> <span>((</span><span>==</span><span>)</span> <span><*></span> <span>reverse</span><span>)</span> <span>"racecar"</span>   <span>-- (<*> is Haskell's infix version for the S-combinator)</span>
<span>-- haskell</span>
<span>ans</span> <span>::</span> <span>Bool</span>
<span>ans</span> <span>=</span> <span>((</span><span>==</span><span>)</span> <span><*></span> <span>reverse</span><span>)</span> <span>"racecar"</span>   <span>-- (<*> is Haskell's infix version for the S-combinator)</span>
-- haskell
ans :: Bool
ans = ((==) <*> reverse) "racecar"   -- (<*> is Haskell's infix version for the S-combinator)

Enter fullscreen mode Exit fullscreen mode

Implicitness

Using compositions and combinators allow us to write functions with implicit arguments. This is called its tacit or point-free form.

This means we no longer have to specify the arguments of our functions, as they are implicitly declared by the compositions we use, leaving us with a partially applied function.


<span>sqr</span> <span>=</span> <span>lambda</span> <span>a</span><span>:</span> <span>a</span><span>*</span><span>a</span> <span># helper for squaring </span><span>c_map</span> <span>=</span> <span>lambda</span> <span>f</span><span>:</span> <span>lambda</span> <span>a</span><span>:</span> <span>map</span><span>(</span><span>f</span><span>,</span> <span>a</span><span>)</span>
<span># Explicit form </span><span>def</span> <span>_sum_of_squares</span><span>(</span><span>arr</span> <span>:</span> <span>list</span><span>[</span><span>int</span><span>])</span> <span>-></span> <span>int</span><span>:</span>
    <span>squares</span> <span>=</span> <span>map</span><span>(</span><span>sqr</span><span>,</span> <span>arr</span><span>)</span>
    <span>return</span> <span>sum</span><span>(</span><span>squares</span><span>)</span>
<span># Implicit form </span><span>sum_of_squares</span> <span>=</span> <span>b </span><span>(</span><span>sum</span><span>)</span> <span>(</span><span>c_map</span><span>(</span><span>sqr</span><span>))</span>   <span># Note that we aren't providing the `arr` argument </span>
<span>sum_of_squares</span><span>([</span><span>1</span><span>,</span><span>2</span><span>,</span><span>3</span><span>])</span> <span># But we can still use it because sum_of_squares is partially applied </span>
<span>sqr</span> <span>=</span> <span>lambda</span> <span>a</span><span>:</span> <span>a</span><span>*</span><span>a</span> <span># helper for squaring </span><span>c_map</span> <span>=</span> <span>lambda</span> <span>f</span><span>:</span> <span>lambda</span> <span>a</span><span>:</span> <span>map</span><span>(</span><span>f</span><span>,</span> <span>a</span><span>)</span>

<span># Explicit form </span><span>def</span> <span>_sum_of_squares</span><span>(</span><span>arr</span> <span>:</span> <span>list</span><span>[</span><span>int</span><span>])</span> <span>-></span> <span>int</span><span>:</span>
    <span>squares</span> <span>=</span> <span>map</span><span>(</span><span>sqr</span><span>,</span> <span>arr</span><span>)</span>
    <span>return</span> <span>sum</span><span>(</span><span>squares</span><span>)</span>

<span># Implicit form </span><span>sum_of_squares</span> <span>=</span> <span>b </span><span>(</span><span>sum</span><span>)</span> <span>(</span><span>c_map</span><span>(</span><span>sqr</span><span>))</span>   <span># Note that we aren't providing the `arr` argument </span>
<span>sum_of_squares</span><span>([</span><span>1</span><span>,</span><span>2</span><span>,</span><span>3</span><span>])</span> <span># But we can still use it because sum_of_squares is partially applied </span>
sqr = lambda a: a*a # helper for squaring c_map = lambda f: lambda a: map(f, a)

# Explicit form def _sum_of_squares(arr : list[int]) -> int:
    squares = map(sqr, arr)
    return sum(squares)

# Implicit form sum_of_squares = b (sum) (c_map(sqr))   # Note that we aren't providing the `arr` argument 
sum_of_squares([1,2,3]) # But we can still use it because sum_of_squares is partially applied

Enter fullscreen mode Exit fullscreen mode

And this is how functional languages can get away with elegant point-free definitions. In fact, one of my favorite things to do when writing in functional languages is to refactor them into their tacit forms.


<span>import</span> <span>Control.Applicative</span>
<span>import</span> <span>Data.Function</span>
<span>sumOfSquares</span> <span>::</span> <span>[</span><span>Int</span><span>]</span> <span>-></span> <span>Int</span>
<span>sumOfSquares</span> <span>=</span> <span>sum</span> <span>.</span> <span>map</span> <span>(</span><span>^</span><span>2</span><span>)</span>
<span>isPalindrome</span> <span>::</span> <span>String</span> <span>-></span> <span>Bool</span>
<span>isPalindrome</span> <span>=</span> <span>(</span><span>==</span><span>)</span> <span><*></span> <span>reverse</span>
<span>isLonger</span> <span>::</span> <span>String</span> <span>-></span> <span>String</span> <span>-></span> <span>Bool</span>
<span>isLonger</span> <span>=</span> <span>(</span><span>></span><span>)</span> <span>`</span><span>on</span><span>`</span> <span>length</span>
<span>average</span> <span>::</span> <span>[</span><span>Int</span><span>]</span> <span>-></span> <span>Float</span>
<span>average</span> <span>=</span> <span>liftA2</span> <span>(</span><span>/</span><span>)</span> <span>(</span><span>sum</span><span>)</span> <span>(</span><span>length</span><span>)</span>
<span>import</span> <span>Control.Applicative</span>
<span>import</span> <span>Data.Function</span>

<span>sumOfSquares</span> <span>::</span> <span>[</span><span>Int</span><span>]</span> <span>-></span> <span>Int</span>
<span>sumOfSquares</span> <span>=</span> <span>sum</span> <span>.</span> <span>map</span> <span>(</span><span>^</span><span>2</span><span>)</span>

<span>isPalindrome</span> <span>::</span> <span>String</span> <span>-></span> <span>Bool</span>
<span>isPalindrome</span> <span>=</span> <span>(</span><span>==</span><span>)</span> <span><*></span> <span>reverse</span>

<span>isLonger</span> <span>::</span> <span>String</span> <span>-></span> <span>String</span> <span>-></span> <span>Bool</span>
<span>isLonger</span> <span>=</span> <span>(</span><span>></span><span>)</span> <span>`</span><span>on</span><span>`</span> <span>length</span>

<span>average</span> <span>::</span> <span>[</span><span>Int</span><span>]</span> <span>-></span> <span>Float</span>
<span>average</span> <span>=</span> <span>liftA2</span> <span>(</span><span>/</span><span>)</span> <span>(</span><span>sum</span><span>)</span> <span>(</span><span>length</span><span>)</span>
import Control.Applicative
import Data.Function

sumOfSquares :: [Int] -> Int
sumOfSquares = sum . map (^2)

isPalindrome :: String -> Bool
isPalindrome = (==) <*> reverse

isLonger :: String -> String -> Bool
isLonger = (>) `on` length

average :: [Int] -> Float
average = liftA2 (/) (sum) (length)

Enter fullscreen mode Exit fullscreen mode

Tacit definitions of course bring extra overhead to your code, but like many things in modern programming, they can serve as abstractions for programmers to be able to write terse and (subjectively) clean code by leveraging math.

Applying functional patterns in mostly imperative languages don’t really end up that nice-looking but I still hope you learned something new from this, and are able to apply the patterns in this article (probably not in production codebases) to your future code!

原文链接：Functional Patterns: Composition and Implicitness

展开阅读全文

文章版权声明 1、本网站名称：拾光赋
2、本站永久网址：https://www.blogs.ink
3、本网站的文章部分内容可能来源于网络，仅供大家学习与参考，如有侵权，请联系站长QQ：805375623进行删除处理。
4、本站一切资源不代表本站立场，并不代表本站赞同其观点和对其真实性负责。
5、本站一律禁止以任何方式发布或转载任何违法的相关信息，访客发现请向站长举报
6、本站资源大多存储在云盘，如发现链接失效，请联系我们我们会第一时间更新。

THE END