One post tagged with "recursion"

Composability is the name of the game when it comes to writing Ecto queries. With such a beautifully designed DSL given to us, we should make full use of its design to build our queries.

A Brief on Recursive Functions​

Recursive functions are functions that call themselves. There is the risk of functions becoming infinite loops if they are not given exit conditions.

Here's an example:

def eat(food) when food == "biscuits" do
   eat(food, "water") 
end

def eat(food) do
   eat(food, nil) 
end

# return the final digestable result
def eat(food, drink) do
   {food, drink}
end

In the example, we keep calling the eat function until we end up with a digestable form of input, a food input and drink.

Building Queries Based on Flags​

When we want to build a query, the most simple way (as an end user) would be to use flags. This allows the user to describe the type of data that they want returned.

For example, if I wanted to specify a filter, all I would need to do is add an option where_id: 5 to filter the query to all records where the id is 5.

Hence, ideally, we should interface with our function like so:

...
food = list_food(is_dry: true, origin: "us")

Using Enum.reduce/3 for a Naive Implementation​

Utilizing Enum.reduce/3 is an extremely simple way to build up your query, as it will iterate over all your options and call a function for each option.

def list_food(opts \\ [])
   # we give some default options, in this case we limit the output to 5 by default
   opts = Enum.into(opts, %{limit: 5})
   base_query = from(f in Food)
   
   # the base query is the accumulator, and we constantly call the function for each option pair 
   Enum.reduce(opts, base_query, &build_query/2)
   |> Repo.all()
end

# the accumulator is always the second argument
# the map key-value pairs are passed as tuples
def build_query({:limit, value}, query), do: limit(query, value)

# to filter by origin, a string column
def build_query({:origin, loc}, query) when is_binary(loc), do: where(query,[f], f.origin == ^loc)

# to filter by dryness
def build_query({:is_dry, true}, query), do: where(query,[f], f.type == "dry")

# this is for unrecognized options
def build_query(_, query), do: query

This implementation will work for simple situations, but what if we have an option that depends on another option? Or what if we need to access multiple options at once?

Ah, these issues are not so simple to solve when using Enum.reduce/3 as the backbone for our recursive query building.

What other methods can we use, then, for managing the recursive nature of our function? Why, the head-tail recursion technique, of course!

Head-Tail Recursion Implementation​

Let's re-implement the function, but this time, addressing our new list of concerns.

This function needs to:

1. access all options at the same time
2. control the option execution order

def list_food(opts \\ [])
   # our defaults
   opts = Enum.into(opts, %{limit: 5}) 
  
   from(f in Food)
   |> build_query(opts)
   |> Repo.all()
end

# we expect the 2 arity function to always receive the option as a map.
# We then convert the map to a list of keys, and use it as the 3rd parameter
def build_query(query, opts), do: build_query(query, opts, Map.keys(opts))

# match for the :limit option
def build_query(q, %{limit: value}, [:limit | t]) do
  limit(query, value)
  |> build_query(opts, t)
end

# match for the :origin option
def build_query(q, %{origin: loc}, [:origin | t]) when is_binary(loc) do
  where(query,[f], f.origin == ^loc)
  |> build_query(opts, t)
end

# match for the :is_dry option
def build_query(q, %{is_dry: true}, [:is_dry | t]) do
  where(query,[f], food.type == "dry")
  |> build_query(opts, t)
end

# control the option execution stack as needed
# to process this option, we need to have a join with brands first 
def build_query(q, %{country: iso}, [:is_dry | t]) when is_binary(iso) do
  if has_named_binding?(q, :brands) do
    # we utilize the named binding to filter by the country's ISO abbreviation
    where(query,[f, brands: b], b.iso == ^iso)
    |> build_query(opts, t)
  else
    # add the :brands key to the front of the stack, then add country again, then the remaining tail end. 
    build_query(q, opts, [:brands, :country] ++ t)
  end
end

# we add this join on demand, as not every query needs it
def build_query(q, _opts, [:brands |t]) do
   join(:left, [f], b in Brands, on: food.brand_id == b.id, as: :brands)
   |> build_query(opts, t)
end

# this is for unrecognized options, we skip over it
def build_query(q, opts, [_ | t]), do: build_query(q, opts, t)

# no more options to process, let's exit the function now
def build_query(q, _, []), do: q

Let's break this down:

1. We call the function with a map of our options
2. We convert these options into a list of keys, and pass it as the 3rd parameter of our recursive function.
3. For each option handler, we match on our required option keys in the map (on the 2nd parameter), and on the head of the list. Essentially, we are popping off an option from the stack of option keys we need to process.
4. If we have pre-requisite conditions before processing the option, we can call add in or sort the option stack to ensure oure requisite option is processed first before the current option is procesed (see the :country option handler and how it checks for the :brands join before adding a where clause to the query).
5. Call the function again with the tail-end of the option stack, ensuring that each option in the stack is processed.
6. Exit the recursive function when all options are processed and an empty list is remaining.

Although more verbose, this gives you the ultimate control over the flow of query building, as well as allowing you full access to all options at the same time.

Other Benefits​

Besides composability at outer layers of your application, you can also utilize this to build your subqueries easily.

For example, you can use this technique to build queries for other tables, then use the resultant query in a subquery.

A super simplified example:

...
food_query = from(f in Food)
|> Foods.build_query(is_dry: true)

# to get all dry restraunt food
from(r in RestrauntFoods,
  join: f in subquery(food_query),
  on: r.food_id == f.id
)
|> Repo.all()
...

I usually use the above in situations where the subqueries are complex aggregations and would benefit from the re-usability.

The head-tail recursion method is very common in Elixir, and having it in your Ecto query building toolbox would save you from re-writing many queries from scratch.