# Using functional design to reduce arity

I was implementing a tail recursive BST using functional design. However, I’m getting stumped in one area. Right now, my `insert/3` and `insert_or_traverse/4` both use 3 of the same arguments.

I’m trying to figure out how to refactor so that both have access to these arguments but I don’t have to pass all 3 to the helper function.

``````defmodule BST do
@type node :: %{value: any, left: node | nil, right: node | nil}
def node(value \\ nil, left \\ nil, right \\ nil) do
%{value: value, left: left, right: right}
end

def insert(nil, value), do: node(value)
def insert(%{value: nil} = root, value), do: node(value)
def insert(root, value), do: insert(root, root, value)

def insert(root, %{value: node_value} = tree, value) do
option = if node_value < value, do: :left, else: :right
insert_or_traverse(root, tree, value, option)
end

defp insert_or_traverse(root, tree, value, option) do
case Map.get(tree, option) do
nil -> Map.put(tree, option, node(value)); root
child -> insert(root, child, value)
end
end
end
``````

P.S. Doing a bit of research, there’s a body recursive implementation that doesn’t hit this problem.

Ok, think I figured out the answer:

`def insert(root), do: fn value -> insert(root, root, value) end`

Now a user would call:

iex> `insert_into_tree = BST.insert(node(1))`
`Function <...>`
iex> `new_root = insert_into_tree.(2)`
`%{value: 1, left: nil, right: %{value: 2, left: nil, right: nil} }`

So, `node |> BST.insert().(value) |> BST.insert().(value)`

And the term for this is partial application, which we achieve via our curried `insert/1` of `@spec insert(node) :: (number -> node)`.

Just wrote a blog post (an intro to functional programming & its design patterns) based upon this learning experience!

``````def insert(root), do: fn value -> insert(root, root, value) end
``````

My current understanding is that partial application is the process of taking a function `f` of arity `n` and a list of arguments of length `m` and producing a new function which has an arity less than `n` (usually `(n-m)`).

Your function `insert/1` simply returns an anonymous function `f/1`. Its implementation suggest that you are attempting to emulate the effects of partial application by capturing at least one of the arguments inside a closure for a function to be called at a later point in time.

If you had curried `insert/2` you would still end up with a function `f/2`, i.e. the arity would remain unchanged. However being curried `f(1)` would return `g/1` while `f(1,2)` would return a result value.

Example: What Ramda `curry` does for JavaScript (which actually goes even further as the `R.__` placeholder allows for the more general partial application of single argument values).

2 Likes

The source I based this off of defines partial application as reducing a `function/n` down to a `function/1` as achieved via currying.

In my given example, that is achieved by `insert/1`. If we needed, say, a logging dependency, we would pass that at this level. Our new `insert/2` would still produce a `function/1` anonymous function which we could then curry only our `value` to. It just so happens that my example required only 2 arguments. So, the implementation is currying and the design pattern is partial application.

If we add another method `delete/2`, we can invoke `insert/1` within it only once, passing down the `root`, and store the result as a variable. From then on, we only need to pass the `value` of the nodes we reorder into our variable, instead of also the `root` node with each call. This is a paradigmatic example of partial application (albeit, there’s a referencing issue with my implementation due to immutability).

Regardless, my example demonstrates how a function that requires many arguments can be turned into an API which requires fewer from the user and is thus more intuitive and composable.

Eh, that’s F#'s definition, and even then that’s a side site so I don’t think that is right anyway…

Curry: Break apart a function into single-argument functions that return a closure around the rest, thus turning `(int, int, int) -> int` into `int -> int -> int -> int`.

Partial Application: Where you supply partial arguments to a function call, thus creating a closure that accepts the rest.

Currying happens at the function definition site.

Partial Application happens at the call site.

Like let’s assume that a `_#` in an Elixir `&` call created a new argument in a closure, and you have a function `blah/3` that takes 3 arguments, then doing `&blah(1, _1, 2)` would partially apply the function blah with 2 argument (first and third) and left a ‘hole’ in the second argument, thus effectively making `fn a1 -> blah(1, a1, 2) end`. Where making blah a curried function would instead mean doing `def blah(a), do: fn b -> fn c -> a+b+c end end` and would have to be called like `blah(1).(2).(3)`, however note that this lets you in-order partially apply by just doing something like `blah(1).(2)`, but doesn’t let you out-of-order partially apply like the prior example without a proper partial application pattern like the above example has (which most curry’d languages work around by adding functions like swap and so forth).

2 Likes

There are a lot of confused explanations for partial application and currying.

I’m going back to why currying was invented in the first place:

Haskell book, p.10:

Each lambda can only bind one parameter and can only accept one argument. Functions that require multiple arguments have multiple, nested heads. When you apply it once and eliminate the first (leftmost) head, the next one is applied and so on. This formulation was originally discovered by Moses Schönfinkel in the 1920s but was later rediscovered and named after Haskell Curry and is commonly called currying.

In partial application you start with a function with multiple parameters and each partial application provides some of the arguments, creating a function with the remaining unapplied parameters.

Example language implementations:
Clojure
JavaScript

The point being - when performing partial application one of the arguments is usually the function that is subject to partial application.

FYI: SRP is misnamed:

Gather together those things that change for the same reason, and separate those things that change for different reasons.

So it’s about “reasons to change” rather than “single responsibility”.

I recommend watching
YOW! 2013 Kevlin Henney - The SOLID Design Principles Deconstructed

2 Likes