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 Schö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
