List contains another list in the same order

Interesting problem. I also couldn't find a good function in the standard library that does this. It seems like a similar problem to finding a substring, so I thought it might be useful to look at how Elixir implements finding a substring. It turns out that it uses the Erlang implementation written in C, which uses the Boyer-Moore string-search algorithm.

So, without an existing implementation this is a complex computer-science question. I managed to write a version that passes your tests, but I'm sure there are much better implementations! I think you should also answer your own question with your implementation. It sounds like something that would be worth adding to the standard library. Maybe this kind of algorithm is difficult to implement efficiently in immutable languages?

Anyway, here's what I got:

1. Build up a match variable, which we will use to check if we found the sublist.
2. Iterate through the input list, pushing each new element onto the match variable.
3. Once the length of match is the same as the target sublist, remove an element from the end every time we push an element to the beginning.
4. If at any time match equals the target sublist, we found a match.
5. When we exhaust all the elements, we know that there was no match.

defmodule Lists do
  def contains_sublist?(list, sublist) do
    contains_sublist?(list, Enum.reverse(sublist), [])
  end

  defp contains_sublist?(_, sublist, sublist), do: true
  defp contains_sublist?([], _, _), do: false

  defp contains_sublist?([current | rest], sublist, match)
       when length(sublist) == length(match) do
    contains_sublist?(rest, sublist, [current | Enum.take(match, length(match) - 1)])
  end

  defp contains_sublist?([current | rest], sublist, match) do
    contains_sublist?(rest, sublist, [current | match])
  end

  def test do
    contains_sublist?([1, 2, 3], [1, 2]) &&
      contains_sublist?([3, 1, 2], [1, 2]) &&
      contains_sublist?([1, 2, 3], [2, 3]) &&
      !contains_sublist?([1, 3, 2], [1, 2]) &&
      !contains_sublist?([1, 2, 3], [1, 2, 4])
  end
end

Test:

iex(1)> Lists.test                                                                                            
true

It passes all your tests, but since it traverses the match list every iteration, I suspect the performance will degrade for large sublists or large input lists, since it is O(m·n).

In the end this is the implementation I used:

  @spec list_contains_in_order(List.t(), List.t()) :: boolean
  def list_contains_in_order([], _), do: false

  def list_contains_in_order(container, contained) do
    if List.starts_with?(container, contained) do
      true
    else
      list_contains_in_order(tl(container), contained)
    end
  end

One possible performance optimization would be to keep track of the length of the container (not by checking the length in every iteration, but by calculating the initial one and decreasing it on every iteration) and compare to the length of the contained, so we can stop once container is smaller.

For the purposes of my code (we don't expect very big lists), I left it like this.