DNA Encoding should require tail call recursion

[angelikatyborska]

A big chunk of highly rated community solutions to DNA Encoding doesn't even use the concept that is taught, tail call recursion. Instead they use regular recursion. See at the end of the issue for examples.

It would be great if we found a way to detect that both encode and decode functions use tail call recursion. We would need to find all functions called from either function encode and decode, and check their definitions. At least one of the called functions has a function clause whose last call is itself, it's tail-call recursion.

Example 1

defmodule DNA do
  @nucleotide_encode_table %{
    ?\s => 0b0000,
    ?\A => 0b0001,
    ?\C => 0b0010,
    ?\G => 0b0100,
    ?\T => 0b1000
  }

  @nucleotide_decode_table Enum.map(@nucleotide_encode_table, fn {k, v} -> {v, k} end)
                           |> Map.new()

  def encode_nucleotide(code_point) do
    Map.fetch!(@nucleotide_encode_table, code_point)
  end

  def decode_nucleotide(encoded_code) do
    Map.fetch!(@nucleotide_decode_table, encoded_code)
  end

  def encode(dna)
  def encode([]), do: <<>>
  def encode([head | tail]) do
    <<encode_nucleotide(head)::4, encode(tail)::bitstring>>
  end

  def decode(dna)
  def decode(<<>>), do: []
  def decode(<<head::4, tail::bitstring>>) do
    [decode_nucleotide(head) | decode(tail)]
  end
end

Example 2

defmodule DNA do
  @moduledoc false

  @type nucleotide_char :: ?\s | ?A | ?C | ?G | ?T
  @type nucleotide_bitstring :: 0 | 1 | 2 | 4 | 8
  @type dna_charlist :: [nucleotide_char()]
  @type dna_bitstring :: <<_::_*4>>

  @spec encode_nucleotide(nucleotide_char()) :: nucleotide_bitstring()
  def encode_nucleotide(?\s), do: 0b0000
  def encode_nucleotide(?A), do: 0b0001
  def encode_nucleotide(?C), do: 0b0010
  def encode_nucleotide(?G), do: 0b0100
  def encode_nucleotide(?T), do: 0b1000

  @spec decode_nucleotide(nucleotide_bitstring()) :: nucleotide_char()
  def decode_nucleotide(0b0000), do: ?\s
  def decode_nucleotide(0b0001), do: ?A
  def decode_nucleotide(0b0010), do: ?C
  def decode_nucleotide(0b0100), do: ?G
  def decode_nucleotide(0b1000), do: ?T

  @spec encode(dna_charlist()) :: dna_bitstring()
  def encode([]), do: <<>>
  def encode([head | tail]), do: <<encode_nucleotide(head)::4, encode(tail)::bitstring>>

  @spec decode(bitstring) :: dna_charlist()
  def decode(<<>>), do: []
  def decode(<<head::4, rest::bitstring>>), do: [decode_nucleotide(head) | decode(rest)]
end

Example 2

defmodule DNA do
  @moduledoc false

  @type nucleotide_char :: ?\s | ?A | ?C | ?G | ?T
  @type nucleotide_bitstring :: 0 | 1 | 2 | 4 | 8
  @type dna_charlist :: [nucleotide_char()]
  @type dna_bitstring :: <<_::_*4>>

  @spec encode_nucleotide(nucleotide_char()) :: nucleotide_bitstring()
  def encode_nucleotide(?\s), do: 0b0000
  def encode_nucleotide(?A), do: 0b0001
  def encode_nucleotide(?C), do: 0b0010
  def encode_nucleotide(?G), do: 0b0100
  def encode_nucleotide(?T), do: 0b1000

  @spec decode_nucleotide(nucleotide_bitstring()) :: nucleotide_char()
  def decode_nucleotide(0b0000), do: ?\s
  def decode_nucleotide(0b0001), do: ?A
  def decode_nucleotide(0b0010), do: ?C
  def decode_nucleotide(0b0100), do: ?G
  def decode_nucleotide(0b1000), do: ?T

  @spec encode(dna_charlist()) :: dna_bitstring()
  def encode([]), do: <<>>
  def encode([head | tail]), do: <<encode_nucleotide(head)::4, encode(tail)::bitstring>>

  @spec decode(bitstring) :: dna_charlist()
  def decode(<<>>), do: []
  def decode(<<head::4, rest::bitstring>>), do: [decode_nucleotide(head) | decode(rest)]
end

Example 3

defmodule DNA do
  @nucleic_space 0b0000
  @nucleic_acid_a 0b0001
  @nucleic_acid_c 0b0010
  @nucleic_acid_g 0b0100
  @nucleic_acid_t 0b1000

  @spec encode_nucleotide(char()) :: integer()
  def encode_nucleotide(?\s), do: @nucleic_space
  def encode_nucleotide(?A), do: @nucleic_acid_a
  def encode_nucleotide(?C), do: @nucleic_acid_c
  def encode_nucleotide(?G), do: @nucleic_acid_g
  def encode_nucleotide(?T), do: @nucleic_acid_t

  @spec decode_nucleotide(integer()) :: char()
  def decode_nucleotide(@nucleic_space), do: ?\s
  def decode_nucleotide(@nucleic_acid_a), do: ?A
  def decode_nucleotide(@nucleic_acid_c), do: ?C
  def decode_nucleotide(@nucleic_acid_g), do: ?G
  def decode_nucleotide(@nucleic_acid_t), do: ?T

  @spec encode(charlist()) :: bitstring()
  def encode([]), do: <<>>
  def encode([?\s | rest]), do: <<@nucleic_space::size(4), encode(rest)::bitstring>>
  def encode([?A | rest]), do: <<@nucleic_acid_a::size(4), encode(rest)::bitstring>>
  def encode([?C | rest]), do: <<@nucleic_acid_c::size(4), encode(rest)::bitstring>>
  def encode([?G | rest]), do: <<@nucleic_acid_g::size(4), encode(rest)::bitstring>>
  def encode([?T | rest]), do: <<@nucleic_acid_t::size(4), encode(rest)::bitstring>>

  @spec decode(bitstring()) :: charlist()
  def decode(<<>>), do: []
  def decode(<<@nucleic_space::size(4), rest::bitstring>>), do: [?\s | decode(rest)]
  def decode(<<@nucleic_acid_a::size(4), rest::bitstring>>), do: [?A | decode(rest)]
  def decode(<<@nucleic_acid_c::size(4), rest::bitstring>>), do: [?C | decode(rest)]
  def decode(<<@nucleic_acid_g::size(4), rest::bitstring>>), do: [?G | decode(rest)]
  def decode(<<@nucleic_acid_t::size(4), rest::bitstring>>), do: [?T | decode(rest)]
end