English3000
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.
Marked As Solved
OvermindDL1
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).
Also Liked
peerreynders
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).
peerreynders
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
Popular in Questions
Other popular topics
Latest on Elixir Forum
Sponsor Spotlight
Courses that'll move you from confusion to "Aha, now I get it!"
Categories:
Sub Categories:
Forums
Our Sponsors
Build Elixir applications with speed and confidence.
Supporting innovation across the BEAM ecosystem.
We build reliable cloud platforms for business-critical systems.
Catch errors, track performance, monitor hosts and more.
Practical resources that improve the lives of professional developers.
Develop your skills with books, videos, and courses.
Enabling companies to succeed by building software people love.
Courses that'll move you from confusion to "Aha, now I get it!"