Fiddling with improper snoc lists

Chat / Discussions
1

I came across this yesterday while thinking during a boat trip, and I wanted to share it because there might be some smart use cases for it.

In Lisp, Erlang and Elixir, we’re allowed to make a so-called improper list, a list whose last element is not [] but something else.

For instance in IO-lists this is already used to speed up the concatenation, because appending and prepending to such an improper list is both O(1), with the drawback that many of the recursive algorithms that expect a normal list do not work anymore on them.
But, after finishing the prepending/appending, it is possible to transform the IO-list back into a normal list by traversing it once.

An ‘improper snoc’ list as I have been thinking about is similar, but only works on addition. That is, where a normal list is [head | tail], this one does [tail | head].

An improper snoc list with many elements thus looks like [[[[[] | 1] | 2] | 3] | 4]. (A normal list like [1 | [ 2 | [ 3 | [4 | []]]]])

The interesting thing about this, is that turning this snoc list back to a normal list not only takes a single linear traversal, but also:

  • It is possible to reverse-prepend the snoc-list to a normal list without an extra traversal that using ++ would need.
  • this traversal is tail-recursive and thus has constant memory usage because no intermediate lists need to be stored while building the result (which is what e.g. :lists.reverse does need as it is not tail-recursive).

It looks like follows:

def reverse_snoc_list(snoc_list), do: reverse_snoc_list(snoc_list, [])

# Call this version directly to reverse-concatenate the snoclist:
def reverse_snoc_list([], acc), do: acc
def reverse_snoc_list([tail | head], acc), do: reverse_snoc_list(tail, [head | acc])

I think this improper snoclist might be used in places where we now traverse any datastructure, building a list of results, and finally call :lists.reverse on this result because it is in the opposite order than we expect.

I think that using an improper snoc list for this is faster and uses less memory, but I haven’t benchmarked it yet.

1 Like
2

Actually, I think it does not matter at all. Consing backwards or consing normally does not change how a list can be reversed at all. :slight_smile:

1 Like
3

Slight correction:

defmodule Lists do
  def reverse(list), do: reverse_with_acc(list, [])
  def reverse_with_acc([], acc), do: acc
  def reverse_with_acc([tail | head], acc), do: reverse_with_acc(head, [tail | acc])
end

At least that’s how I did it for an exercise.