I did not formally study Computer Science, so please bear with me if I am missing something obvious. I am studying the inner workings of functional programming concepts and wrote this simplistic map function:

defmodule EnumMap do
  def map(proc, [head | []]) do
    proc.(head)
  end

  def map(proc, [head | tail]) do
    [proc.(head)] ++ map(proc, tail)
  end
end

EnumMap.map(fn x -> x + 1 end, [1, 2, 3, 4])

This produced: [2, 3, 4 | 5].

I thought “that’s weird, why is 5 being explicitly called with a list constructor?”

Aha, then I caught my mistake:

defmodule EnumMap do
  def map(proc, [head | []]) do
    [proc.(head)] # I needed to wrap this result in a list
  end

  def map(proc, [head | tail]) do
    [proc.(head)] ++ map(proc, tail)
  end
end

EnumMap.map(fn x -> x + 1 end, [1, 2, 3, 4])

Producing: [2, 3, 4, 5]

Hooray! However, that then made me wonder!

If Elixir lists are linked lists, why is [2, 3, 4 | 5] allowed? Isn’t that explicitly saying “this is a linked list, except for the final element which is just an integer.”? Is there a benefit to having linked lists where the final element is not in fact a list? Are there certain data structures or algorithms that use these sort of odd linked lists?