Look into ways of querying an ets table

[RobStallion]

I want to look into ways of querying ets tables.

If we can find a way to query the ets table by distance, then we would not need to query postgres. This will be a change to the way that we currently use in CS but is worth looking into.

[RobStallion]

Possible solution

Found ets.fun2ms function which allows us to create a function which can filter results.

iex> :ets.new :test, [:named_table]
:test
iex> :ets.insert(:test, {1, 1})
true
iex> :ets.insert(:test, {2, 2})
true
iex> fun = :ets.fun2ms(fn {k, v} when n < 2 -> {k, v} end)
[{{:"$1", :"$2"}, [{:<, :"$2", 2}], [:"$1"]}]
iex> :ets.select(:test, fun) 
[{1, 1}]

This shows that we can filter by function (in the CS implementation we only ever do exact lookups.

Next step is to try and create a more advanced function (goal is to have a function which can take a lat-long from the ets table and filter by how close it is to a given lat-long).

[RobStallion]

Trying to move the "query" logic into the function body (as apposed to having it in a guard clause like the example above) returns the following error...

iex> fun = :ets.fun2ms(fn {k, v} -> (if k < 2, do: {k, v}) end)
Error: the language element case (in body) cannot be translated into match_spec
{:error, :transform_error}

Appears all filtering needs to be done with guard clauses.

[RobStallion]

Opened an SO question here

[RobStallion]

The answer to my SO question says that we cannot do checks inside the function. This will make it more difficult to do looks ups from the ets table.

Looking into a solution that can be used in the guard clause.

[RobStallion]

Elixir only allows very specific functions to work inside of a guard clause (mostly kernel functions from what I can see) so if we are going to filter the "stores" by distance using only ets we are going to have to be able to do everything using 'basic' functions.

example...

iex()> :ets.new :n, [:named_table]
:n
iex(2)> :ets.insert :n, [{1,1},{2,2},{3,3}]
true
iex(3)> fun = :ets.fun2ms  fn {k, v} when k * v < 9 -> {k,v} end
[{{:"$1", :"$2"}, [{:<, {:*, :"$1", :"$2"}, 9}], [{{:"$1", :"$2"}}]}]
iex(4)> :ets.select :n, fun
[{1, 1}, {2, 2}]

This shows that we can do more complicated searches using the values stored in the ets table.

Next steps

• Create a function that can work out the distance between to sets of lat-long values
• See if we can use this function in the guard clause.
  • If the function can be used in, turn into marco to allow it to be used in guard clause (see here for more info.

[RobStallion]

using an online calculator, I can see the distance between the following lat-longs sets

Going to try and replicate this in elixir. Have seen the function in JS. Going to try and convert this to elixir syntax...

var R = 6371e3; // metres
var φ1 = lat1.toRadians();
var φ2 = lat2.toRadians();
var Δφ = (lat2-lat1).toRadians();
var Δλ = (lon2-lon1).toRadians();

var a = Math.sin(Δφ/2) * Math.sin(Δφ/2) +
        Math.cos(φ1) * Math.cos(φ2) *
        Math.sin(Δλ/2) * Math.sin(Δλ/2);
var c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a));

var d = R * c;

The site that had this code is https://www.movable-type.co.uk/scripts/latlong.html

[RobStallion]

The formula for working out the distance between 2 sets of lat long values is called the Haversine formula.

Elixir implementation

defmodule Haversine do
  @v  :math.pi / 180
  @r  6372.8            # km for the earth radius

  def distance({lat1, long1}, {lat2, long2}) do
    dlat  = :math.sin((lat2 - lat1) * @v / 2)
    dlong = :math.sin((long2 - long1) * @v / 2)
    a = dlat * dlat + dlong * dlong * :math.cos(lat1 * @v) * :math.cos(lat2 * @v)
    @r * 2 * :math.asin(:math.sqrt(a))
  end
end

This gives the same results as the site above...

iex()> e2 = {51.535574, -0.074558}
{51.535574, -0.074558}
iex()> n1 = {51.543562, -0.088456}
{51.543562, -0.088456}

iex()> Haversine.distance e2, n1
1.3091215324867733

Next step is to try and use this in a guard clause.

[RobStallion]

have managed to convert the above into a macro...

defmodule HaversineMacro do
  @v  :math.pi / 180
  @r  6372.8

  defmacro distance({{lat1, {:-, _, [long1]}}, {lat2, {:-, _, [long2]}}}) do
    dlat  = :math.sin((lat2 - lat1) * @v / 2)
    dlong = :math.sin((long2 - long1) * @v / 2)
    a = dlat * dlat + dlong * dlong * :math.cos(lat1 * @v) * :math.cos(lat2 * @v)
    res = @r * 2 * :math.asin(:math.sqrt(a))
    quote do
      unquote(res)
    end
  end
end

This can be used in iex like so...

iex()> import HaversineMacro
HaversineMacro
iex()> n1 = {51.543562, -0.088456}
{51.543562, -0.088456}
iex()> e2 = {51.535574, -0.074558}
{51.535574, -0.074558}
iex()> f = fn(ll1, ll2) when distance({{51.543562, -0.088456}, {51.535574, -0.074558}}) < 5 -> "this macro works" end
#Function<12.128620087/2 in :erl_eval.expr/5>
iex()> f.(n1, e2)
"this macro works"

The distance macro is being called with the lat-long values from n1 and e2 (2 areas I know are close by) and the resulting distance is being checked to see if it is less than 5km. If so it just returns the string "this macro works".

The problem I am having now is that I cannot use the values being passed into the anonymous function in the distance macro call

e.g.

iex()> f = fn(ll1, ll2) when distance({e2, n1}) < 5 -> "this macro works" end
** (FunctionClauseError) no function clause matching in HaversineMacro.distance/1

Although the values in distance({{51.543562, -0.088456}, {51.535574, -0.074558}} are the same as calling distance({e2, n1})`, this is not working due to how macros work.

Not sure if this is just a problem in iex. Going to try in a mix project and see if I have the same results.

[RobStallion]

I'm having a lot of issues turning this into a marco. Going to read metaprogramming elixir to see if I can learn anything about how this could be done.

Will add what I can to the learn elixir readme

[RobStallion]

I have come back to looking into this now that I have a better understanding of macros.

Somewhat surprisingly to myself my previous macro was not a million miles away.
There were a few things I was doing wrong in the failing code above...

iex()> f = fn(ll1, ll2) when distance({e2, n1}) < 5 -> "this macro works" end
** (FunctionClauseError) no function clause matching in HaversineMacro.distance/1

It was not working because I was not passing the variables from the anonymous function to the distance macro. E.g. it should have been distance({ll1, ll2}).

This was the first error I came across (and honestly that part wasn't even to do with macros at all. Just me missing the obvious 🙄)

[RobStallion]

After I updated the anonymous function, I was getting an issue where the macro would work with values but not variables.

e.g.

iex()> distance {{51.543562, -0.088456}, {51.535574, -0.074558}}
1.3091215324867733

iex()> distance {n1, e2}
** (FunctionClauseError) no function clause matching in Haversine.distance/1
    (haversine) expanding macro: Haversine.distance/1
    iex:5: (file)

n1 & e2 were variables defined in one of the comments above

There were a few things wrong here.

First, I was not using quote and unquote correctly when I defined the macro. It turns out to use a variable in a marco is has to be unquoted. See this SO question for more info.

So I ended up with something that looked like....

  defmacro d({{lat1, {:-, _, [long1]}}, {lat2, {:-, _, [long2]}}}) do
    quote do
      v = :math.pi / 180
      r = 6372.8

      dlat  = :math.sin((unquote(lat2) - unquote(lat1)) * v / 2)
      dlong = :math.sin((unquote(long2) - unquote(long1)) * v / 2)
      a = dlat * dlat + dlong * dlong * :math.cos(unquote(lat1) * v) * :math.cos(unquote(lat2) * v)
      res = r * 2 * :math.asin(:math.sqrt(a))
      res
    end
  end

However, again this worked with arguments but not variables...

iex()> d {{51.543562, -0.088456}, {51.535574, -0.074558}}
1.3091215324867733
iex()> d {n1, e2}
** (FunctionClauseError) no function clause matching in Haversine.d/1
    (haversine) expanding macro: Haversine.d/1
    iex:4: (file)

[RobStallion]

This next error was because it was saying there were no matching function clauses.

** (FunctionClauseError) no function clause matching in Haversine.d/1

Let's see what a log or the argument shows...

  defmacro d({ll1, _ll2}) do
    IO.inspect(ll1, label: "before quote")
    quote do
      IO.inspect(unquote(ll1), label: "unquote")
    end
  end

iex()> d {n1, e2}
before quote: {:n1, [line: 5], nil}
unquote: {51.543562, -0.088456}

The macro receives the argument ll1 as {:n1, [line: 5], nil}. This is why we were not getting a match with the previous definition of the function. The way around this is to remove the pattern match from the def of the function.

So we end up with something that looks like...

  defmacro d(ll1, ll2) do
    quote do
      lat1 = elem(unquote(ll1), 0)
      long1 = elem(unquote(ll1), 1)
      lat2 = elem(unquote(ll2), 0)
      long2 = elem(unquote(ll2), 1)

      v = :math.pi / 180
      r = 6372.8

      dlat  = :math.sin((lat2 - lat1) * v / 2)
      dlong = :math.sin((long2 - long1) * v / 2)
      a = dlat * dlat + dlong * dlong * :math.cos(lat1 * v) * :math.cos(lat2 * v)
      res = r * 2 * :math.asin(:math.sqrt(a))
      res
    end
  end

I have updated the macro to take 2 arguments now. Inside the quote block we are assigning our lat1/etc variables by first unquote-ing what is passed into the macro and then using the elem function to assign the variables.

so unquote({:n1, [line: 5], nil} == {51.543562, -0.088456}

[RobStallion]

This now works in the terminal...

iex()> d n1, e2
1.3091215324867733

[RobStallion]

However, remember that we wanted this to work in a guard clause. Let's see what happens when we do this...

iex(5)> f = fn(ll1, ll2) when d(ll1, ll2) < 5 -> "worked" end
** (CompileError) iex:5: invalid expression in guard, = is not allowed in guards. To learn more about guards, visit: https://hexdocs.pm/elixir/guards.html
    (haversine) expanding macro: Haversine.d/2
    iex:5: (file)

This is not failing because the = sign (among others) is not allowed to be used in a guard clause.

If we visit the link the error message displays you can learn more. https://hexdocs.pm/elixir/guards.html

[RobStallion]

So it tells us that we can only use specific functions and expressions in a guard clause which means that we will need to find a way to replicate the logic without using =.

If we do that we end up with something like...

  defmacro calc_distance(ll1, ll2) do
    quote do
      :math.sin((elem(unquote(ll2), 1) - elem(unquote(ll1), 1)) * (3.141592653589793 / 180) / 2)
      |> square()
      |> Kernel.*(:math.cos(elem(unquote(ll1), 0) * (3.141592653589793 / 180)))
      |> Kernel.*(:math.cos(elem(unquote(ll2), 0) * (3.141592653589793 / 180)))
      |> Kernel.+(squarer(:math.sin((elem(unquote(ll2), 0) - elem(unquote(ll1), 0)) * (3.141592653589793 / 180) / 2)))
      |> :math.sqrt()
      |> :math.asin()
      |> Kernel.*(2)
      |> Kernel.*(6372.8)
    end
  end

pretty ugly looking if I do say so myself but it works.

Let's test this in the terminal.

iex()> calc_distance n1, e2
1.3091215324867733

Nice. This is working as we would expect without assigning any variables.

However, it STILL doesn't work as a guard clause. This is because the :math functions are not "guard friendly" (not sure what the correct term for this is)

We can see this in iex again

iex()> f = fn(ll1, ll2) when calc_distance(ll1, ll2) < 5 -> "worked" end
** (CompileError) iex:6: cannot invoke remote function :math.sin/1 inside guard
    (stdlib) lists.erl:1354: :lists.mapfoldl/3
    (haversine) expanding macro: Haversine.square/1
    iex:6: (file)
    (elixir) expanding macro: Kernel.|>/2
    iex:6: (file)

In order for us to get this to work in a guard clause, all the function calls inside of it are going to have to be made into macros first.

If you have a really keen eye you might have noticed this line...

      |> square()

This was a macro I made to test the theory that we cannot use functions in a guard clause macro but we can use marcos

[RobStallion]

let's show how this works...

  def squarer(n) do
    n * n
  end

  defmacro test_squarer(n) do
    quote do
      squarer(unquote(n))
    end
  end

  defmacro square(n) do
    quote do
      unquote(n) * unquote(n)
    end
  end

  defmacro test_square(n) do
    quote do
      square(unquote(n))
    end
  end

Above I have defined a function squarer/1 which takes a number and squares it.
I have defined a macro which uses this function called test_squarer

I have also defined a macro called square which squares a number
I have defined a macro which users this macro called test_square

Lets use these in iex

iex()> test_square 5
25
iex()> test_squarer 5
25

We can see that both macros work as expected when called normally. Now let's try using them as guard clauses now.

iex(4)> fn(n) when test_square(n) < 30 -> "works" end
#Function<6.128620087/1 in :erl_eval.expr/5>
iex(5)> fn(n) when test_squarer(n) < 30 -> "works" end
** (CompileError) iex:5: cannot invoke remote function Haversine.squarer/1 inside guard
    (haversine) expanding macro: Haversine.test_squarer/1
    iex:5: (file)

As we can see, test_squarer (the macro the uses a function) fails while test_square works.

[RobStallion]

This means that we need to recreate all the functions that are not allowed to be used in a guard clause.

In our case that means the :math functions.

[RobStallion]

Recreating the :math functions being used as macros is a lot harder than I originally thought.

I'm not currently sure if it is hard because I don't fully understand the maths myself or because it is high level elixir. I am leaning toward the former though. If anyone has any knowledge/understanding about how functions like sin or cos work then please feel free to comment here.

I have opened a SO question about it.

[RobStallion]

Someone answered my SO question from above and pointed to this wiki that describes a formula for the approximation of the sine function.

I will look into this solution for a little while to see if I can replicate this logic in elixir. If I can replicate the functions, I then need to see how accurate the approximations are. If they are not good enough then I may need to find another approach.

[RobStallion]

I don't think I understand the math well enough

Screenshot from wiki...

My understanding of this is...

  def sin(x) do
    top = 16 * x * (:math.pi - x)
    bottom = 5 * square(:math.pi) - 4 * x * (:math.pi - x)

    top / bottom
  end

But when I compare my sin function vs math.sin from erlang I get pretty different results...

iex()> MyMath.sin 5
-0.5236641910564511
iex()> :math.sin 5
-0.9589242746631385

[RobStallion]

As I cannot get the sine function working I have decided to leave the macro approach for now and focus on the suggestion given in this SO comment.

I will aim to use the Haversine.calc_distance function we have created with the :ets.foldl function from erlang.

[RobStallion]

iex()> n1 = {51.543562, -0.088456}
{51.543562, -0.088456}

iex()> :ets.new :latlong, [:named_table]
:postcodes

iex()> :ets.insert :latlong, [n1]
true

iex()> :ets.foldl(fn(ll, acc) -> if Haversine.calc_distance(ll, {51.535574, -0.074558}) < 5, do: [ll | acc], else: acc  end, [], :latlong)
[{51.543562, -0.088456}]

iex()> :ets.foldl(fn(ll, acc) -> if Haversine.calc_distance(ll, {51.535574, -0.074558}) < 1, do: [ll | acc], else: acc  end, [], :latlong)
[]

The steps above...

1. create a variable for a lat-long value.
2. create an :ets table called :latlong
3. insert the variable into the ets table
4. called ets.foldl with the calc_distance function. The arguments passed to calc_distance are the lat-long value from the ets table and a hard-coded lat-long value (say a users location). If the result of the calc_distance function is less than 5km between the value in the ets table and the hardcoded value, return the value from the ets table. This returns our value from the ets table.
5. Same as step 4 but instead of grabbing values within a 5k range, grab values within a 1k range. This returns nothing.

It appears that we may be able to query our ets table for nearby stores.