ndac_todoroki
How to implement complexed custom sort?
Thinking of implementing a Chess game in Elixir, I created a module which will represent a chess piece as a struct.
defmodule Piece do
alias __MODULE__, as: Piece
@piece_types ~w(King Queen Rook Bishop Knight Pawn)a
@type type :: :King | :Queen | :Rook | :Bishop | :Knight | :Pawn
defstruct [:type]
@type t :: %Piece{ type: type() }
defguard is_type(piece_type) when piece_type in @piece_types
def new(type) when is_type(type), do: %Piece{type: type}
end
then there is a struct that represents an active piece:
defmodule Fighter do
alias __MODULE__, as: Fighter
@type owner :: :player | :opponent
defstruct [ :owner, :piece, :position ]
@type t :: %Fighter{ owner: owner(), piece: Piece.t(), position: BoardCoordinate.t }
end
So I have a List of Fighters when the game starts. I came to a circumstance where I want to sort the Fighters.
The result should be sorted first by fighter.owner, then by fighter.piece.type, and then by fighter.position, so it will be
- my king
- my queen
… - my most left-top pawn
- my secondly left-top pawn
… - opponent’s king
- opponent’s queen
…
and so on. Can I perform this on a single custom sort? (Like performing fighters |> Fighter.sort())?
For that I thought setting a default sort algorism for each struct type could be a simple way, but I couldn’t have sorted(!) this out.
Any help and thoughts are welcomed!
Marked As Solved
Qqwy
Elixir’s sorting function is stable. This means that you can first sort the whole list of fighters on the least-important condition, then on the second-least important condition , etc. and finally on the most important condtion, and they will end up in the order you’d expect.
So in your case
fighters
|> Enum.sort_by(fn fighter -> fighter.position end)
|> Enum.sort_by(fn fighter -> fighter.piece.type end)
|> Enum.sort_by(fn fighter -> fighter.owner end)
And, by taking advantage of the fact that tuples are ordered elementwise (we look at the next element only if the current element is equal), we could write it like this instead as well:
fighters
|> Enum.sort_by(fn fighter -> {fighter.owner, fighter.piece.type, fighter.position} end)
However, this will not give the answer you’d like yet, because many things are represented by symbols, which by default are sorted alphabetically (whereas you’d like the given order King > Queen > Bishop > ... and player > opponent. The translation functions you wrote for your custom sorter would indeed be a solution to this.
It is possible to automate that a little, by creating a map of the numerically ordered equivalents (like piece_type_ordering = piece_types |> Enum.with_index |> Enum.into(%{})), which you’d want to generate at compile time, so you can just write a function then that will turn a given thing into their ordering.
I think a protocol like the following might make sense:
defprotocol Orderable
@doc """
Turns the given structure into something that can be compared and sorted in the desired order.
"""
@spec orderable(any) :: any
orderable(_)
end
whose implementation for e.g. %Piece would simply return the number that is stored for the given type’s symbol key.
And for %Fighter, it would return e.g.
def orderable(fighter)
import Orderable
{orderable(fighter.owner), orderable(fighter.piece), fighter.position}
end
Also Liked
kokolegorille
Not that it helps with your sorting question, but I have done two chess libs in Elixir…
The second is a translated from Erlang and generates all possible moves. Maybe it helps
japplegame
My AVLTree implementation with custom sorting function: https://github.com/japplegame/avl_tree
Qqwy
ndac_todoroki
Wow, this is amazing how minimum the code could be. It was a whole new study for me. Thanks for the information!!
japplegame
With Orderable protocol you also can use AVLTree like this:
AVLTree.new(fn a, b -> Orderable.orderable(a) < Orderable.orderable(b))
All inserted elements will be automatically sorted.








