Funx: Building Lexicographic Sorts with Optics

“You’re not thinking fourth dimensionally!” — Doc Brown, Back to the Future Part II (1989)

We’ve seen how Lens and Prism let us extract values from nested data. Now we’ll use those same projections to build layered lexicographic sorts, one dimension at a time.

Setup

Let’s return to our transaction problem:

Transaction
└─ type
   ├─ Charge
   │  └─ payment
   │     ├─ CreditCard
   │     │  └─ amount   ← cc_payment
   │     └─ Check
   │        └─ amount   ← check_payment
   │
   └─ Refund
      └─ payment
         ├─ CreditCard
         │  └─ amount   ← cc_refund
         └─ Check
            └─ amount   ← check_refund

But limited to the payments:

import Funx.Macros, only: [ord_for: 2]
alias Funx.Optics.{Lens, Prism}

defmodule Check do
  alias Funx.Optics.Prism
  defstruct [:name, :routing_number, :account_number, :amount]

  def amount_prism do
    Prism.path([{__MODULE__, :amount}])
  end

  ord_for(Check, Lens.key(:name))
end

defmodule CreditCard do
  alias Funx.Optics.Prism
  defstruct [:name, :number, :expiry, :amount]

  def amount_prism do
    Prism.path([{__MODULE__, :amount}])
  end

  ord_for(CreditCard, Lens.key(:name))
end

First, we need some data:

alias Funx.Optics.{Lens, Prism}
alias Funx.Ord.Utils, as: OrdUtils
alias Funx.List

check_1 = %Check{name: "Frank", routing_number: "111000025", account_number: "0001234567", amount: 100}
check_2 = %Check{name: "Edith",   routing_number: "121042882", account_number: "0009876543", amount: 400}
check_3 = %Check{name: "Charles", routing_number: "026009593", account_number: "0005551122", amount: 200}

cc_1 = %CreditCard{name: "Dave", number: "4111", expiry: "12/26", amount: 400}
cc_2 = %CreditCard{name: "Alice",  number: "4242", expiry: "01/27", amount: 300}
cc_3 = %CreditCard{name: "Beth",   number: "1324", expiry: "06/25", amount: 100}

payment_data = [check_1, check_2, check_3, cc_1, cc_2, cc_3]

Elixir has Enum.sort_by/2, which takes a projection function:

name_projection = fn %{name: name} -> name end
Enum.sort_by(payment_data, name_projection)
# [
#   %CreditCard{name: "Alice", amount: 300, ...},
#   %CreditCard{name: "Beth", amount: 100, ...},
#   %Check{name: "Charles", amount: 200, ...},
#   %CreditCard{name: "Dave", amount: 400, ...},
#   %Check{name: "Edith", amount: 400, ...},
#   %Check{name: "Frank", amount: 100, ...}
# ]

Here, name_projection gets the :name key for sort_by/2.

Funx takes a projection too, but rather than having a separate sort_by function, it wraps projections in the contramap/1 function:

name_ord = OrdUtils.contramap(name_projection)
List.sort(payment_data, name_ord)
# [
#   %CreditCard{name: "Alice", amount: 300, ...},
#   %CreditCard{name: "Beth", amount: 100, ...},
#   %Check{name: "Charles", amount: 200, ...},
#   %CreditCard{name: "Dave", amount: 400, ...},
#   %Check{name: "Edith", amount: 400, ...},
#   %Check{name: "Frank", amount: 100, ...}
# ]

The nice thing about Funx’s contramap/1 is that it can also take an optic Lens:

name_ord = OrdUtils.contramap(Lens.key(:name))
List.sort(payment_data, name_ord)
# [
#   %CreditCard{name: "Alice", amount: 300, ...},
#   %CreditCard{name: "Beth", amount: 100, ...},
#   %Check{name: "Charles", amount: 200, ...},
#   %CreditCard{name: "Dave", amount: 400, ...},
#   %Check{name: "Edith", amount: 400, ...},
#   %Check{name: "Frank", amount: 100, ...}
# ]

If we need more complex ord logic we can always return to a projection function, but it’s nice to have the composability and predictable lawfulness of the Lens.

It’s easy to swap the lens to :amount:

amount_ord = OrdUtils.contramap(Lens.key(:amount))
List.sort(payment_data, amount_ord)
# [
#   %Check{name: "Frank", amount: 100, ...},
#   %CreditCard{name: "Beth", amount: 100, ...},
#   %Check{name: "Charles", amount: 200, ...},
#   %CreditCard{name: "Alice", amount: 300, ...},
#   %Check{name: "Edith", amount: 400, ...},
#   %CreditCard{name: "Dave", amount: 400, ...}
# ]

But what if we want to sort by :amount and then :name?

It can be challenging to compose lexicographic order logic by hand, which is why we often see these types of problems solved with multiple loops. But we can get there using composition, achieving the same result in a single sort.

Funx includes concat/1, where we can compose a list of Ord:

amount_name_ord = OrdUtils.concat([amount_ord, name_ord])
List.sort(payment_data, amount_name_ord)
# [
#   %CreditCard{name: "Beth", amount: 100, ...},
#   %Check{name: "Frank", amount: 100, ...},
#   %Check{name: "Charles", amount: 200, ...},
#   %CreditCard{name: "Alice", amount: 300, ...},
#   %CreditCard{name: "Dave", amount: 400, ...},
#   %Check{name: "Edith", amount: 400, ...}
# ]

Next, let’s try sorting by :routing_number:

routing_ord = OrdUtils.contramap(Lens.key(:routing_number))
List.sort(payment_data, routing_ord)
# ** (KeyError) key :routing_number not found in: %CreditCard{...}

When we use a Lens, we are stating, “All our items will have a routing number key.” Its job is to fail fast when we break that domain invariant. In this case, our payment data included a credit card, which does not have a valid routing number focus.

Instead, we need a Prism:

routing_ord = OrdUtils.contramap(Prism.key(:routing_number))
List.sort(payment_data, routing_ord)
# [
#   %CreditCard{name: "Dave", amount: 400, ...},
#   %CreditCard{name: "Alice", amount: 300, ...},
#   %CreditCard{name: "Beth", amount: 100, ...},
#   %Check{name: "Charles", amount: 200, routing_number: "026009593", ...},
#   %Check{name: "Frank", amount: 100, routing_number: "111000025", ...},
#   %Check{name: "Edith", amount: 400, routing_number: "121042882", ...}
# ]

With Prism.key(:routing_number), checks yield Just(routing_number) and credit cards yield Nothing. Nothing sorts before Just, so credit cards come first.

We can add an Ord to sort the credit cards by name:

route_name_ord = OrdUtils.concat([routing_ord, name_ord])
List.sort(payment_data, route_name_ord)
# [
#   %CreditCard{name: "Alice", amount: 300, ...},
#   %CreditCard{name: "Beth", amount: 100, ...},
#   %CreditCard{name: "Dave", amount: 400, ...},
#   %Check{name: "Charles", amount: 200, routing_number: "026009593", ...},
#   %Check{name: "Frank", amount: 100, routing_number: "111000025", ...},
#   %Check{name: "Edith", amount: 400, routing_number: "121042882", ...}
# ]

The checks can be sorted by :routing_number, but in this context the credit cards are equal with Nothing, so the :name sort is applied. This is the lexicographic sort in action.

Let’s reverse the sort, but only for routing_number:

route_name_ord = OrdUtils.concat([
  OrdUtils.reverse(routing_ord),
  name_ord
])
List.sort(payment_data, route_name_ord)
# [
#   %Check{name: "Edith", amount: 400, routing_number: "121042882", ...},
#   %Check{name: "Frank", amount: 100, routing_number: "111000025", ...},
#   %Check{name: "Charles", amount: 200, routing_number: "026009593", ...},
#   %CreditCard{name: "Alice", amount: 300, ...},
#   %CreditCard{name: "Beth", amount: 100, ...},
#   %CreditCard{name: "Dave", amount: 400, ...}
# ]

Funx includes a reverse/1, which flips the order.

Let’s take a look at how we might implement this with Enum.sort/2:

Enum.sort(payment_data, fn a, b ->
  ra = Map.get(a, :routing_number)
  rb = Map.get(b, :routing_number)

  cond do
    ra != nil and rb == nil ->
      true

    ra == nil and rb != nil ->
      false

    ra != nil and rb != nil and ra > rb ->
      true

    ra != nil and rb != nil and ra < rb ->
      false

    true ->
      a.name <= b.name
  end
end)
# [
#   %Check{name: "Edith", amount: 400, routing_number: "121042882", ...},
#   %Check{name: "Frank", amount: 100, routing_number: "111000025", ...},
#   %Check{name: "Charles", amount: 200, routing_number: "026009593", ...},
#   %CreditCard{name: "Alice", amount: 300, ...},
#   %CreditCard{name: "Beth", amount: 100, ...},
#   %CreditCard{name: "Dave", amount: 400, ...}
# ]

There are a couple of issues here. First, it’s ad hoc; it is not easily testable or shareable. Also it is a bit more difficult to read than the Funx version. And, as Ord composition can be arbitrarily large and complex, these problems will grow with size.

Let’s make our life easier by switching to Funx’s more declarative Ord DSL:

use Funx.Ord.Dsl
route_name_ord =
ord do
   desc Prism.path([{Check, :routing_number}])
   asc Lens.key(:name)
end
List.sort(payment_data, route_name_ord)
# [
#   %Check{name: "Edith", amount: 400, routing_number: "121042882", ...},
#   %Check{name: "Frank", amount: 100, routing_number: "111000025", ...},
#   %Check{name: "Charles", amount: 200, routing_number: "026009593", ...},
#   %CreditCard{name: "Alice", amount: 300, ...},
#   %CreditCard{name: "Beth", amount: 100, ...},
#   %CreditCard{name: "Dave", amount: 400, ...}
# ]

This solves the same sort problem. Behind the scenes it is just applying our contramap/1, concat/1 and reverse/1.

For simple cases we can shorten to a single atom, :name:

route_name_ord =
ord do
   desc :routing_number
   asc :name
end
List.sort(payment_data, route_name_ord)
# [
#   %Check{name: "Edith", amount: 400, routing_number: "121042882", ...},
#   %Check{name: "Frank", amount: 100, routing_number: "111000025", ...},
#   %Check{name: "Charles", amount: 200, routing_number: "026009593", ...},
#   %CreditCard{name: "Alice", amount: 300, ...},
#   %CreditCard{name: "Beth", amount: 100, ...},
#   %CreditCard{name: "Dave", amount: 400, ...}
# ]

The DSL automatically applies the default sort behavior at the end as a tiebreaker. And since we defined ord_for(CreditCard, Lens.key(:name)), the :name sort for our credit cards is automatically appended.

This means we can remove the explicit asc :name:

route_name_ord =
ord do
   desc :routing_number
end
List.sort(payment_data, route_name_ord)
# [
#   %Check{name: "Edith", amount: 400, routing_number: "121042882", ...},
#   %Check{name: "Frank", amount: 100, routing_number: "111000025", ...},
#   %Check{name: "Charles", amount: 200, routing_number: "026009593", ...},
#   %CreditCard{name: "Alice", amount: 300, ...},
#   %CreditCard{name: "Beth", amount: 100, ...},
#   %CreditCard{name: "Dave", amount: 400, ...}
# ]

Note that the :atom context is applying the Prism.

If the :routing_number is a domain invariant, we can explicitly choose a Lens:

route_name_ord =
ord do
   desc Lens.key(:routing_number)
end
List.sort(payment_data, route_name_ord)
# ** (KeyError) key :routing_number not found in: %CreditCard{...}

Which raises a fast failure.

So currently our sort has checks first. But what if we need credit cards first?

We can use or_else to replace Nothing with a value that sorts higher than the routing numbers.

In this case, a simple “a” will do the trick:

route_name_ord =
ord do
   desc :routing_number, or_else: "a"
end
List.sort(payment_data, route_name_ord)
# [
#   %CreditCard{name: "Alice", amount: 300, ...},
#   %CreditCard{name: "Beth", amount: 100, ...},
#   %CreditCard{name: "Dave", amount: 400, ...},
#   %Check{name: "Edith", amount: 400, routing_number: "121042882", ...},
#   %Check{name: "Frank", amount: 100, routing_number: "111000025", ...},
#   %Check{name: "Charles", amount: 200, routing_number: "026009593", ...}
# ]

Here, because this is a descending sort and “a” is larger than any of our routing numbers, the credit cards are sorted before checks. And because the credit cards are all equal with an “a”, they fall back to the :name order.

But there is a better way to solve our problem:

route_name_ord =
ord do
   desc CreditCard
   desc Prism.path([{Check, :routing_number}])
end
List.sort(payment_data, route_name_ord)
# [
#   %CreditCard{name: "Alice", amount: 300, ...},
#   %CreditCard{name: "Beth", amount: 100, ...},
#   %CreditCard{name: "Dave", amount: 400, ...},
#   %Check{name: "Edith", amount: 400, routing_number: "121042882", ...},
#   %Check{name: "Frank", amount: 100, routing_number: "111000025", ...},
#   %Check{name: "Charles", amount: 200, routing_number: "026009593", ...}
# ]

Here, we have the same result but without the brittle “a” domain logic.

We can also use prisms from the modules, such as CreditCard.amount_prism/0:

cc_amount_ord =
ord do
   asc CreditCard.amount_prism
end

With max!/2 we get the highest value:

List.max!(payment_data, cc_amount_ord)
# %CreditCard{name: "Dave", amount: 400, ...}

And min!/2:

List.min!(payment_data, cc_amount_ord)
# %Check{name: "Charles", amount: 200, ...}

Wait, that’s a Check!

Remember, cc_amount_ord isn’t a filter, so a check is still in the list.

We need this Ord:

cc_amount_min_ord =
ord do
   desc CreditCard
   asc CreditCard.amount_prism
end

List.min!(payment_data, cc_amount_min_ord)
# %CreditCard{name: "Beth", amount: 100, ...}

Nested Data

So far we’ve worked with flat payment data. Let’s see how this scales to our full nested transaction structure.

For instance, we can set a Lens for our Transaction that defaults to sort by payment :name:

defmodule Transaction do
  defstruct [:type]

  def type_prism do
    Prism.path([{__MODULE__, :type}])
  end

  ord_for(
    Transaction,
    Lens.path([:type, :payment, :name])
  )
end

defmodule Charge do
  alias Funx.Optics.Prism
  defstruct [:payment]

  def payment_prism do
    Prism.path([{__MODULE__, :payment}])
  end

  ord_for(
    Charge,
    Lens.path([:payment, :name])
  )
end

defmodule Refund do
  alias Funx.Optics.Prism
  defstruct [:payment]

  def payment_prism do
    Prism.path([{__MODULE__, :payment}])
  end

  ord_for(
    Refund,
    Lens.path([:payment, :name])
  )
end

And here is some transaction data:

refund_cc_1 =
%Transaction{
  type: %Refund{
    payment: %CreditCard{name: "Frank", number: "4333", expiry: "10/27", amount: 1200}
  }
}

refund_cc_2 =
%Transaction{
  type: %Refund{
    payment: %CreditCard{name: "Eve", number: "4555", expiry: "08/28", amount: 100}
  }
}

refund_check_1 =
  %Transaction{
    type: %Refund{
      payment: %Check{name: "Dave", routing_number: "123000025", account_number: "0001234567", amount: 1200}
    }
  }

charge_check_1 =
  %Transaction{
    type: %Charge{
      payment: %Check{name: "Charles", routing_number: "111000025", account_number: "0001234567", amount: 1000}
    }
  }

charge_cc_1 =
  %Transaction{
    type: %Charge{
      payment: %CreditCard{name: "Bob", number: "4444", expiry: "09/26", amount: 400}
    }
  }

charge_cc_2 =
  %Transaction{
    type: %Charge{
      payment: %CreditCard{name: "Alice", number: "4222", expiry: "11/25", amount: 100}
    }
  }

transactions = [refund_cc_1, refund_cc_2, refund_check_1, charge_check_1, charge_cc_1, charge_cc_2]

List.sort(transactions)
# [
#   %Transaction{type: %Charge{payment: %CreditCard{name: "Alice", amount: 100, ...}}},
#   %Transaction{type: %Charge{payment: %CreditCard{name: "Bob", amount: 400, ...}}},
#   %Transaction{type: %Charge{payment: %Check{name: "Charles", amount: 1000, ...}}},
#   %Transaction{type: %Refund{payment: %Check{name: "Dave", amount: 1200, ...}}},
#   %Transaction{type: %Refund{payment: %CreditCard{name: "Eve", amount: 100, ...}}},
#   %Transaction{type: %Refund{payment: %CreditCard{name: "Frank", amount: 1200, ...}}}
# ]

Notice the List.sort/1 with no ord falls back to the Transaction default we defined as ord_for(Transaction, Lens.path([:type, :payment, :name])).

And we can sort by :amount:

payment_amount_ord =
ord do
   asc Lens.path([:type, :payment, :amount])
end

List.sort(transactions, payment_amount_ord)
# [
#   %Transaction{type: %Charge{payment: %CreditCard{name: "Alice", amount: 100, ...}}},
#   %Transaction{type: %Refund{payment: %CreditCard{name: "Eve", amount: 100, ...}}},
#   %Transaction{type: %Charge{payment: %CreditCard{name: "Bob", amount: 400, ...}}},
#   %Transaction{type: %Charge{payment: %Check{name: "Charles", amount: 1000, ...}}},
#   %Transaction{type: %Refund{payment: %Check{name: "Dave", amount: 1200, ...}}},
#   %Transaction{type: %Refund{payment: %CreditCard{name: "Frank", amount: 1200, ...}}}
# ]

Notice the final tiebreaker is still Transaction’s default payment name ord.

And we can reuse our Ord in max!/2:

List.max!(transactions, payment_amount_ord)
# %Transaction{type: %Refund{payment: %CreditCard{name: "Frank", amount: 1200, ...}}}

Here, Frank’s credit card refund is our largest transaction.

And we can continue to use our composed prisms:

defmodule Processor do
  alias Funx.Optics.Prism

  def cc_payment_prism do
    Prism.compose([
      Transaction.type_prism(),
      Charge.payment_prism(),
      CreditCard.amount_prism()
    ])
  end

  def check_payment_prism do
    Prism.compose([
      Transaction.type_prism(),
      Charge.payment_prism(),
      Check.amount_prism()
    ])
  end

  def cc_refund_prism do
    Prism.compose([
      Transaction.type_prism(),
      Refund.payment_prism(),
      CreditCard.amount_prism()
    ])
  end

  def check_refund_prism do
    Prism.compose([
      Transaction.type_prism(),
      Refund.payment_prism(),
      Check.amount_prism()
    ])
  end
end

To sort by credit card payment, then credit card refund, then check payment, then check refund:

payment_amount_ord =
ord do
   asc Processor.cc_payment_prism
   asc Processor.cc_refund_prism
   asc Processor.check_payment_prism
   asc Processor.check_refund_prism
end

List.sort(transactions, payment_amount_ord)
# [
#   %Transaction{type: %Refund{payment: %Check{name: "Dave", amount: 1200, ...}}},
#   %Transaction{type: %Charge{payment: %Check{name: "Charles", amount: 1000, ...}}},
#   %Transaction{type: %Refund{payment: %CreditCard{name: "Eve", amount: 100, ...}}},
#   %Transaction{type: %Refund{payment: %CreditCard{name: "Frank", amount: 1200, ...}}},
#   %Transaction{type: %Charge{payment: %CreditCard{name: "Alice", amount: 100, ...}}},
#   %Transaction{type: %Charge{payment: %CreditCard{name: "Bob", amount: 400, ...}}}
# ]

Want to flip the results?

payment_amount_rev_ord =
ord do
  desc payment_amount_ord
end

List.sort(transactions, payment_amount_rev_ord)
# [
#   %Transaction{type: %Charge{payment: %CreditCard{name: "Bob", amount: 400, ...}}},
#   %Transaction{type: %Charge{payment: %CreditCard{name: "Alice", amount: 100, ...}}},
#   %Transaction{type: %Refund{payment: %CreditCard{name: "Frank", amount: 1200, ...}}},
#   %Transaction{type: %Refund{payment: %CreditCard{name: "Eve", amount: 100, ...}}},
#   %Transaction{type: %Charge{payment: %Check{name: "Charles", amount: 1000, ...}}},
#   %Transaction{type: %Refund{payment: %Check{name: "Dave", amount: 1200, ...}}}
# ]

Or flip back with Funx’s reverse/1:

List.sort(transactions, OrdUtils.reverse(payment_amount_rev_ord))
# [
#   %Transaction{type: %Refund{payment: %Check{name: "Dave", amount: 1200, ...}}},
#   %Transaction{type: %Charge{payment: %Check{name: "Charles", amount: 1000, ...}}},
#   %Transaction{type: %Refund{payment: %CreditCard{name: "Eve", amount: 100, ...}}},
#   %Transaction{type: %Refund{payment: %CreditCard{name: "Frank", amount: 1200, ...}}},
#   %Transaction{type: %Charge{payment: %CreditCard{name: "Alice", amount: 100, ...}}},
#   %Transaction{type: %Charge{payment: %CreditCard{name: "Bob", amount: 400, ...}}}
# ]

This would be a handful to implement using Enum.sort/2, but fortunately we have comparator/1:

Enum.sort(transactions, OrdUtils.comparator(payment_amount_ord))
# [
#   %Transaction{type: %Refund{payment: %Check{name: "Dave", amount: 1200, ...}}},
#   %Transaction{type: %Charge{payment: %Check{name: "Charles", amount: 1000, ...}}},
#   %Transaction{type: %Refund{payment: %CreditCard{name: "Eve", amount: 100, ...}}},
#   %Transaction{type: %Refund{payment: %CreditCard{name: "Frank", amount: 1200, ...}}},
#   %Transaction{type: %Charge{payment: %CreditCard{name: "Alice", amount: 100, ...}}},
#   %Transaction{type: %Charge{payment: %CreditCard{name: "Bob", amount: 400, ...}}}
# ]

Resources

Advanced Functional Programming with Elixir

Dive deeper into functional programming patterns and advanced Elixir techniques. Learn how to build robust, maintainable applications using functional programming principles.

Funx - Functional Programming for Elixir

A library of functional programming abstractions for Elixir, including monads, monoids, Eq, Ord, and more. Built as an ecosystem where learning is the priority from the start.