---

Mastering Crystal Arrays: Build Every Core List Operation from Scratch

Implementing core list operations like map, filter, and reduce in Crystal from scratch is a foundational exercise for truly understanding data manipulation, functional programming paradigms, and the language's powerful type system. This guide provides a complete walkthrough of building these functions from first principles.

Have you ever used a method like .map or .filter on an array and just... trusted it? It's a black box that magically transforms your data. But what if you were asked in an interview how it actually works under the hood? Or what if you needed to implement a slightly custom version? That moment of uncertainty is a common pain point for many developers. This guide is your solution. We will pry open that black box, demystify the magic, and empower you by building every essential list operation from the ground up in Crystal, turning you from a user of tools into a master of them.

---

What Are Core List Operations in Functional Programming?

At the heart of many modern programming languages, especially those with a functional flavor like Crystal, lies a set of fundamental operations for manipulating collections of data. In Crystal, the most common collection is the Array. These operations allow you to transform, query, and aggregate data in a declarative, predictable, and elegant way, without resorting to manual loops and state management for every task.

These core operations, often called higher-order functions, form the bedrock of data processing. They include:

• Mapping: Creating a new list by applying a function to each element of an existing list.
• Filtering: Creating a new list containing only the elements that satisfy a specific condition.
• Folding/Reducing: Combining all elements of a list into a single value by repeatedly applying a function.
• Concatenating: Merging multiple lists into one.
• Reversing: Creating a new list with the elements in the opposite order.

Understanding these concepts is not just academic; it's a practical skill that leads to cleaner, more maintainable, and often more efficient code. By implementing them ourselves, we gain a profound appreciation for the elegance of Crystal's standard library and the computer science principles they are built upon.

---

Why Bother Implementing List Operations Manually?

Crystal's standard library already provides a rich, highly-optimized set of methods for Array manipulation. So, why would we reinvent the wheel? The goal here isn't to replace the standard library in production code—you should almost always use the built-in methods for performance and reliability. Instead, this exercise from the exclusive kodikra.com learning curriculum is about a deeper form of learning.

The key benefits are:

• Deep Algorithmic Understanding: You move from being a user to being a creator. You'll understand the time and space complexity of these operations because you'll be the one allocating memory and defining the loops.
• Mastery of Crystal's Type System: This exercise is a fantastic playground for understanding and using Crystal's powerful generics. You'll learn how to write flexible, type-safe functions that can operate on arrays of any type (Array(T), Array(U), etc.).
• Demystifying Higher-Order Functions: You'll see exactly how functions that accept other functions (or blocks, in Crystal's case) as arguments work. This is the essence of functional programming.
• Interview Preparation: "Implement `map` from scratch" is a classic technical interview question. Walking through this process prepares you to answer it with confidence and depth.
• Appreciation for Abstraction: Once you've built them manually, you'll have a newfound respect for the concise and powerful abstractions provided by the language's core team.

In short, this is a rite of passage. It solidifies your understanding of iteration, data transformation, and functional principles in a very tangible way.

---

How to Build a Custom List Operations Module in Crystal

We will structure our implementation within a Crystal module named ListOps. This encapsulates our functions, preventing name clashes with Crystal's built-in methods and promoting organized code. Our goal is to create a suite of functions that operate on Array instances without using the very methods we are trying to build.

The Complete `ListOps` Module Solution

Here is the full, commented source code for our custom module. We will break down each function in detail in the following sections.

# A module to encapsulate our custom list operations
module ListOps
  # Counts the number of elements in a list.
  # Generic type T allows this to work with an array of any type.
  def self.count(list : Array(T)) : Int32 forall T
    counter = 0
    list.each { |_| counter += 1 }
    counter
  end

  # Reverses a list, returning a new list with elements in opposite order.
  def self.reverse(list : Array(T)) : Array(T) forall T
    reversed_list = [] of T
    # Iterate through the original list and prepend each element
    # to the new list. Prepending is key to the reversal.
    list.each do |element|
      reversed_list.unshift(element)
    end
    reversed_list
  end

  # Creates a new list by applying a block to each element.
  # T is the input type, U is the output type, allowing transformations
  # like Array(Int32) to Array(String).
  def self.map(list : Array(T), &block : T -> U) : Array(U) forall T, U
    mapped_list = [] of U
    list.each do |element|
      # Yield the element to the block and push the result
      mapped_list << yield element
    end
    mapped_list
  end

  # Creates a new list with only the elements for which the block returns true.
  def self.filter(list : Array(T), &block : T -> Bool) : Array(T) forall T
    filtered_list = [] of T
    list.each do in |element|
      # If the block evaluates to true, add the element to our new list
      if yield element
        filtered_list << element
      end
    end
    filtered_list
  end

  # Reduces a list to a single value from left to right.
  # A is the accumulator type, T is the element type.
  def self.foldl(list : Array(T), initial : A, &block : (A, T) -> A) : A forall T, A
    accumulator = initial
    list.each do |element|
      # The new accumulator value is the result of the block
      accumulator = yield accumulator, element
    end
    accumulator
  end

  # Reduces a list to a single value from right to left.
  # This can be implemented by reversing the list and using foldl.
  def self.foldr(list : Array(T), initial : A, &block : (T, A) -> A) : A forall T, A
    accumulator = initial
    # We use our own reverse method to avoid built-ins
    reversed_list = self.reverse(list)
    reversed_list.each do |element|
      # Note the argument order is swapped compared to foldl's block
      accumulator = yield element, accumulator
    end
    accumulator
  end

  # Appends one list to another, returning a new, combined list.
  def self.append(list1 : Array(T), list2 : Array(T)) : Array(T) forall T
    # Start with a copy of the first list to avoid mutation
    new_list = list1.clone
    list2.each do |element|
      new_list << element
    end
    new_list
  end

  # Flattens a list of lists into a single list.
  def self.concat(lists : Array(Array(T))) : Array(T) forall T
    concatenated_list = [] of T
    lists.each do |sub_list|
      sub_list.each do |element|
        concatenated_list << element
      end
    end
    concatenated_list
  end
end

Code Walkthrough: A Deep Dive into Each Function

1. `count(list)`

This is the simplest operation. Its job is to return the number of elements in an array.

• Logic: We initialize a counter to 0. We then iterate over each element in the input list using the basic .each iterator. For every element we encounter, we increment the counter. Finally, we return the total count.
• Generics: The forall T declaration makes this function generic. It can count elements in an Array(Int32), Array(String), or an array of any other type T without any changes.

2. `reverse(list)`

This function creates a new array with the elements of the original in reverse order.

• Logic: We start by creating a new, empty array called reversed_list, explicitly typed as [] of T to match the input type. We iterate through the original list from beginning to end. For each element, instead of appending it (<<), we use .unshift to add it to the beginning of reversed_list. This effectively reverses the order.
• Example: If the input is [1, 2, 3], the first element 1 is unshifted, making `reversed_list` [1]. Then 2 is unshifted, making it [2, 1]. Finally, 3 is unshifted, resulting in the final [3, 2, 1].

3. `map(list, &block)`

The map function is a cornerstone of functional programming. It transforms each element of a list and returns a new list of the transformed elements.

● Start with Input List [a, b, c]
│
▼
┌───────────────────┐
│ Create Empty Result │
│ List []           │
└─────────┬─────────┘
          │
          ▼
    ┌─────────────┐
    │ Take elem 'a' │
    └──────┬──────┘
           │
           ▼
      ╭──────────╮
      │ Apply fn() │
      ╰────┬─────╯
           │
           ▼
┌─────────────────────────┐
│ Push fn(a) to Result    │
│ List [fn(a)]            │
└─────────┬───────────────┘
          │
          ▼
    ◆ More elements? ────────── Yes ┐
          │                         │
          No                        │
          │                         ▼
          ▼                   (Loop for 'b', 'c')
┌───────────────────┐               │
│ Return Result     │◄──────────────┘
│ [fn(a),fn(b),fn(c)] │
└───────────────────┘

• Logic: We create an empty mapped_list. The type of this list is U, which might be different from the input type T. We iterate over the input list. In each iteration, we yield element to the provided block. The block executes its logic and returns a value. This return value is then appended (<<) to our mapped_list.
• Generics: This is a great example of using two generic types. forall T, U means the function takes an Array(T) and a block that transforms a T into a U, ultimately returning an Array(U). For example, you can map an Array(Int32) to an Array(String).

# Example usage of our custom map
numbers = [1, 2, 3]
strings = ListOps.map(numbers) do |n|
  "Number: #{n}"
end
# strings is now ["Number: 1", "Number: 2", "Number: 3"]

4. `filter(list, &block)`

Filter, as the name suggests, creates a new list containing only the elements from the original list that pass a certain test (i.e., for which the block returns true).

• Logic: Similar to map, we start with an empty filtered_list. We iterate through each element. This time, we execute the block by yielding the element to it and check if the result is truthy (if yield element). If it is, we append the original element to filtered_list. If not, we do nothing and move to the next element.

# Example usage of our custom filter
numbers = [1, 2, 3, 4, 5, 6]
evens = ListOps.filter(numbers) do |n|
  n % 2 == 0
end
# evens is now [2, 4, 6]

5. `foldl(list, initial, &block)` (Fold Left / Reduce)

Fold (or reduce) is arguably the most powerful of the list operations. It reduces an entire list down to a single value. foldl does this from left to right.

• Logic: We start with an accumulator variable, initialized with the initial value provided. We then iterate through the list from the first element to the last. In each step, we call the block with the current accumulator and the current element. The result of the block becomes the new value of the accumulator. After iterating through all elements, the final value of the accumulator is returned.
• Generics: forall T, A allows the accumulator (type A) to be different from the list elements (type T). For example, you can sum an Array(Int32) (T=Int32) into a single Int32 (A=Int32), or you could count even numbers, where T=Int32 but A is also Int32 (the count).

6. `foldr(list, initial, &block)` (Fold Right)

foldr is the sibling of foldl. It also reduces a list to a single value, but conceptually, it processes the list from right to left.

  ● Start `foldl` [1, 2, 3], initial: 0, op: +
  │
  ▼
┌───────────────────┐
│ acc = 0           │
└─────────┬─────────┘
          │
          ▼
╭───────────────────╮
│ acc = acc + 1 (1) │
╰─────────┬─────────╯
          │
          ▼
╭───────────────────╮
│ acc = acc + 2 (3) │
╰─────────┬─────────╯
          │
          ▼
╭───────────────────╮
│ acc = acc + 3 (6) │
╰─────────┬─────────╯
          │
          ▼
    ● Result: 6

----------------------------------

  ● Start `foldr` [1, 2, 3], initial: 0, op: +
  │
  ▼
┌───────────────────┐
│ (Conceptually)    │
│ process rightmost │
└─────────┬─────────┘
          │
          ▼
╭───────────────────╮
│ acc = 3 + 0 (3)   │
╰─────────┬─────────╯
          │
          ▼
╭───────────────────╮
│ acc = 2 + acc (5) │
╰─────────┬─────────╯
          │
          ▼
╭───────────────────╮
│ acc = 1 + acc (6) │
╰─────────┬─────────╯
          │
          ▼
    ● Result: 6

• Logic: A simple way to implement foldr without complex recursion is to first reverse the list and then apply a left fold. Our implementation does exactly this, calling self.reverse(list). It then iterates through the reversed list, applying the block. Note the order of arguments in the block for foldr is typically (element, accumulator), whereas for foldl it's (accumulator, element). Our code reflects this by calling yield element, accumulator.
• When it matters: For associative operations like addition (1 + (2 + 3) == (1 + 2) + 3), the result is the same. But for non-associative operations like subtraction, the order is critical. foldl(-) on [1, 2, 3] with initial 0 would be ((0 - 1) - 2) - 3 = -6. foldr(-) would be 1 - (2 - (3 - 0)) = 2.

7. `append(list1, list2)`

This function combines two lists into a new, single list.

• Logic: To avoid mutating the original list1 (a good practice for functional-style methods), we first .clone it into a new_list. Then, we simply iterate through list2 and append each of its elements to the end of new_list.

8. `concat(lists)`

This function takes a list of lists and flattens it into a single list.

• Logic: We initialize an empty concatenated_list. We then have a nested loop. The outer loop iterates through the main lists array (e.g., [[1, 2], [3], [4, 5]]). The inner loop iterates through each sub_list (e.g., [1, 2]) and appends each individual element to our final concatenated_list.

---

Where to Use Custom Implementations vs. The Standard Library

It's crucial to know when to use these hand-rolled functions and when to stick with Crystal's built-in methods. The answer is simple: always prefer the standard library for production applications.

Use your custom ListOps module for:

• Learning & Education: The primary purpose is to deepen your understanding.
• Technical Interviews: To demonstrate your core programming knowledge.
• Prototyping Custom Behavior: If you need a variant of `map` or `filter` with a very specific, non-standard behavior, building it yourself might be a valid starting point before optimizing.

The standard library methods are written by core language developers, are battle-tested, and are often implemented in C or with low-level optimizations that will be significantly faster than a pure Crystal implementation like ours.

Pros & Cons: Custom vs. Standard Library

Aspect	Custom `ListOps` Module	Crystal Standard Library (`Array` methods)
Performance	Slower. Pure Crystal implementation with potential for extra memory allocations.	Highly optimized. Often implemented in C for maximum speed and efficiency.
Learning Value	Extremely high. Teaches algorithms, generics, and functional concepts from the ground up.	Low. Hides the implementation details behind a simple API call.
Readability & Conciseness	More verbose. Requires calling the module, e.g., `ListOps.map(my_array)`.	Very high. Concise and idiomatic, e.g., `my_array.map`.
Reliability & Bug-Free	Depends on your implementation. Potential for edge-case bugs.	Extremely reliable. Vigorously tested by the community and core team.
Flexibility	Fully customizable. You can change the implementation to suit any specific need.	Fixed implementation. You get the behavior provided and cannot change it.

---

Frequently Asked Questions (FAQ)

1. Why not just use Crystal's built-in `Array` methods like `.map` and `.select`?

For production code, you absolutely should use the built-in methods. They are faster, more reliable, and idiomatic. The purpose of this exercise, which is part of the kodikra.com learning path, is purely educational. It forces you to understand the underlying algorithms, memory allocation (creating new arrays), and how to work with higher-order functions and generics, which is invaluable knowledge.

2. What is the practical difference between `foldl` and `foldr`?

The difference is the order of association. foldl (left-associative) groups operations from the left, while foldr (right-associative) groups from the right. For operations like addition, the result is the same (e.g., `(1+2)+3` is the same as `1+(2+3)`). For non-associative operations like subtraction, the result is different. foldr is also theoretically more powerful with lazy evaluation, as it can sometimes produce a result without processing the entire list, though this benefit is less pronounced in an eager language like Crystal.

3. How does Crystal's type system with generics (`forall T, U`) work here?

Generics allow us to write functions that are type-safe without being tied to a specific type. forall T means "for any given type T". When you call ListOps.count([1, 2]), the compiler infers that T is Int32. In map, forall T, U allows the input and output types to differ. For example, in ListOps.map([1, 2]) { |n| n.to_s }, the compiler infers T as Int32 and U as String, ensuring the function correctly returns an Array(String).

4. Is it efficient to create new arrays for every operation like `map` and `filter`?

In terms of memory, creating new arrays does have a cost. This approach favors immutability, which prevents side effects and makes code easier to reason about. Modifying an array in-place can be faster but can also lead to bugs if other parts of your code hold a reference to that same array. For most applications, the clarity and safety of immutability are worth the small performance trade-off. High-performance algorithms may opt for in-place mutation where necessary.

5. Can these functions handle arrays with mixed types?

No, not directly. Crystal's Array is homogeneous, meaning all its elements must be of the same type (or share a common ancestor type). If you need a collection of different types, you would typically use a union type, like Array(Int32 | String). Our generic functions would work perfectly with this, as the compiler would infer T to be (Int32 | String).

6. How can I test these custom functions?

You should use Crystal's built-in testing framework, Spec. You can write a test file (e.g., spec/list_ops_spec.cr) and create tests for each function, asserting that your implementation's output matches the expected output for various inputs, including empty arrays and arrays with one element.

7. What are the future trends for these kinds of operations?

The trend is towards more powerful and expressive abstractions. Languages like Rust, Scala, and Haskell are pushing concepts like lazy evaluation, parallel collections (e.g., mapping/filtering across multiple CPU cores automatically), and more advanced functional constructs like transducers. As Crystal evolves, we can expect its standard library to continue incorporating these modern, high-performance ideas, making declarative data processing even more efficient.

---

Conclusion: From Theory to Mastery

By meticulously building each core list operation from scratch, you have transformed abstract concepts into concrete, working code. You now understand not just what map, filter, and fold do, but how they do it. You've navigated Crystal's generic type system, handled block yields, and reasoned about immutability and algorithmic logic. This foundational knowledge is what separates a good programmer from a great one.

While you'll return to using Crystal's fast and reliable standard library for your day-to-day work, the insights gained here are permanent. You are now better equipped to debug complex data transformations, excel in technical discussions, and write more thoughtful, efficient code.

Disclaimer: The code in this article is for educational purposes. All examples are based on Crystal 1.12+ and may require adjustments for future versions. Always prefer the standard library for production code.

Ready to continue your journey? Explore our complete Crystal programming guide or advance to the next set of challenges in the Kodikra Crystal Learning Roadmap.

---

Published by Kodikra — Your trusted Crystal learning resource.