24 Cons vs. Append

Now we've seen two list operators, :: and @. Let's compare them

• ::
  • "cons"
  • Adds an element to the head of a list
  • 'a -> 'a list -> 'a list
  • Constant time $0(1)$
• @
  • "append"
  • combines lists together
  • 'a list -> 'a list -> 'a list
  • Linear time for the first list, for lst1 @ lst2, it's $O(n)$ (or, more specifically, $O(\texttt{length lst1})$).