Recursive data structure

As explained in Elixir in Action, Third Edition

A recursive data structure is a structure whose elements or parts can contain structures of the same form.

A recursive data structure contains parts with the same form. In Elixir, a nonempty list is a pair: [head | tail], where tail is another list. section 2.4.4

The list representation makes several operational properties visible:

• Reading the head or tail takes O(1), because each operation reads one part of the pair. section 2.4.4
• Prepending is efficient; appending or concatenating traverses the left list and costs O(n). section 2.4.4
• Pattern matching can bind the two parts directly with [head | tail]. section 3.1.5

Building a list from pairs

[1 | [2 | [3 | [4 | []]]]] produces [1, 2, 3, 4]. A practical match, [head | tail] = [1, 2, 3], binds head to 1 and tail to [2, 3]. section 2.4.4 section 3.1.5

Figure 2.1 Recursive structure of the list [1, 2, 3, 4]

Use the list diagram to visualize how each tail points to the next head-tail pair. section 2.4.4

How Elixir in Action, Third Edition covers it

How deep it goes

Explains internal head-tail construction, constant-time access, linear updates, and improper-list boundaries.

Examples

Uses nested cons-style expressions, head-tail matches, list updates, concatenation, and a recursive list diagram.

What you can do after

Apply Elixir head-tail syntax to construct, decompose, and reason about list access and update costs.

How it connects

Connects lists with pattern matching, tuples, list operations, and recursive definitions.

liveBookmanning.com

Read Elixir in Action, Third Edition on liveBook Get the book at manning.com

Also explained in

• 

  liveBookmanning.com
  Functional Design and Architecture: Examples in HaskellA recursive data type is a type whose definition refers to itself, allowing it to represent recursively structured values.

Compare how 2 books explain recursive data structure →

Related concepts

• Boxaddressed by · Box is a Rust owning smart pointer that provides indirection by storing a uniquely owned value in heap-allocated memory.
• listincludes · A list is an ordered collection of elements arranged in a sequence.
• recursionaddressed by · Recursion is a computational technique in which a definition or procedure refers to or invokes the same definition or procedure, directly or indirectly.
• token treeincludes · A token tree is a recursive Rust macro syntax structure consisting of tokens and nested delimited sequences of tokens.
• free monadincludes · A free monad represents computations as composable syntax over an operation set, with interpretation and execution supplied separately.
• binary search treeimplements · A binary search tree is a binary tree whose nodes follow an ordering relation placing keys in designated left and right subtrees relative to each node.

This explainer was generated by Manning's knowledge graph from the text of Elixir in Action, Third Edition. The section links point to the parts of the book it draws on.