Credence.Pattern.NoListConcatWithRecursiveResult (credence v0.7.1)

Copy Markdown

Detects a list-literal prefix concatenated onto a recursive call with ++ in the return expression of a recursive function, and rewrites the ++ to a cons:

[a, b] ++ recursive_call(...)   ==>   [a, b | recursive_call(...)]

[a, b] ++ X is, by the definition of ++, exactly [a, b | X] for every X (proper list, improper tail, or non-list — ++ never constrains its right operand). The rewrite is byte-for-byte behaviour-preserving: same elements, same evaluation order, each operand evaluated exactly once. It drops the intermediate list construction and the ++ traversal of the prefix.

Scope (and what is deliberately not flagged)

This rule fires only when the left operand is a non-empty list literal whose last element is not itself a cons. The genuinely O(n²) shapes the prefix-cons rewrite cannot safely repair are left alone, because their only fix is a non-local accumulator restructuring that changes arity and call sites:

  • computed_var ++ recursive_result — the left list is an arbitrary bound value, not a literal; there is no local cons form.
  • recursive_result ++ [x] — recursion on the left; cons only prepends, so there is no equivalent.

Those are the province of no_list_append_in_recursion (accumulator in a tail call) or a manual rewrite.

Bad

def build([]), do: []
def build([h | t]), do: [h] ++ build(t)

Good

def build([]), do: []
def build([h | t]), do: [h | build(t)]