Exercism - List Ops | Stevinator

Preparation

Before we click on our next exercise, let’s see what concepts of DART we need to consider

So we need to use the following concepts.

Extension Methods on List

Extension methods allow you to add new functionality to existing types without modifying their source code. You can add methods to built-in types like List using extensions.

extension ListOps on List {
  // Add custom methods to List
  int count() {
    var c = 0;
    for (final _ in this) {
      c++;
    }
    return c;
  }
}

void main() {
  List<int> numbers = [1, 2, 3, 4, 5];
  
  // Use extension method
  int length = numbers.count();
  print(length); // 5
  
  // Works on any list
  List<String> words = ['a', 'b', 'c'];
  print(words.count()); // 3
}

Generics

Generics allow you to write code that works with different types. The <T> syntax creates a type parameter that can be replaced with any type.

extension ListOps on List {
  // Generic method - works with any type
  List<T> filter<T>(bool Function(T elem) predicate) {
    List<T> result = [];
    for (final elem in this) {
      if (predicate(elem as T)) {
        result.add(elem as T);
      }
    }
    return result;
  }
}

void main() {
  // Works with integers
  List<int> numbers = [1, 2, 3, 4, 5];
  List<int> evens = numbers.filter((x) => x % 2 == 0);
  
  // Works with strings
  List<String> words = ["apple", "banana", "cherry"];
  List<String> longWords = words.filter((w) => w.length > 5);
}

Generator Functions (sync* and yield)

Generator functions use sync* and yield to create iterables lazily. They’re perfect for building lists without creating intermediate collections.

Iterable<int> countNumbers() sync* {
  for (int i = 1; i <= 5; i++) {
    yield i; // Yield each value
  }
}

Iterable<int> filterNumbers(List<int> list, bool Function(int) predicate) sync* {
  for (final elem in list) {
    if (predicate(elem)) {
      yield elem; // Yield matching elements
    }
  }
}

void main() {
  // Convert generator to list
  List<int> numbers = countNumbers().toList();
  print(numbers); // [1, 2, 3, 4, 5]
  
  // Use generator directly
  List<int> evens = filterNumbers([1, 2, 3, 4, 5], (x) => x % 2 == 0).toList();
  print(evens); // [2, 4]
}

Yield* (Yield All)

The yield* operator yields all values from another iterable. It’s useful for flattening nested structures.

Iterable<int> flatten(List<dynamic> list) sync* {
  for (final item in list) {
    if (item is List) {
      yield* item.cast<int>(); // Yield all items from nested list
    } else {
      yield item as int; // Yield single item
    }
  }
}

void main() {
  List<dynamic> nested = [1, [2, 3], 4, [5, 6]];
  List<int> flat = flatten(nested).toList();
  print(flat); // [1, 2, 3, 4, 5, 6]
}

Function Types

Function types specify the signature of functions that can be passed as parameters. They’re essential for higher-order functions like map, filter, and fold.

void main() {
  // Function type: bool Function(T)
  bool Function(int) isEven = (x) => x % 2 == 0;
  
  // Function type: T Function(T)
  int Function(int) double = (x) => x * 2;
  
  // Function type: U Function(U acc, T elem)
  int Function(int, int) add = (acc, x) => acc + x;
  
  // Use in methods
  List<int> numbers = [1, 2, 3];
  List<int> doubled = numbers.map(double).toList();
  List<int> evens = numbers.where(isEven).toList();
}

Type Casting (as T)

Type casting with as T tells Dart to treat a value as a specific type. It’s necessary when working with generic lists that contain dynamic types.

void main() {
  List<dynamic> mixed = [1, 'hello', 3.14];
  
  // Cast to specific type
  int number = mixed[0] as int;
  String text = mixed[1] as String;
  
  // Cast list elements
  List<int> numbers = [1, 2, 3];
  for (final elem in numbers) {
    int value = elem as int; // Safe cast
    print(value);
  }
  
  // Cast nested lists
  List<dynamic> nested = [[1, 2], [3, 4]];
  for (final item in nested) {
    if (item is List) {
      List<int> numbers = item.cast<int>();
      print(numbers);
    }
  }
}

List `add()` Method

The add() method adds a single element to the end of a list. It mutates the list in place.

void main() {
  List<int> numbers = [1, 2, 3];
  
  // Add single element
  numbers.add(4);
  print(numbers); // [1, 2, 3, 4]
  
  // Add in loop
  List<int> result = [];
  for (int i = 1; i <= 3; i++) {
    result.add(i);
  }
  print(result); // [1, 2, 3]
}

For-In Loops

For-in loops iterate through each element in a collection. They’re perfect for processing all items in a list.

void main() {
  List<int> numbers = [1, 2, 3, 4, 5];
  
  // Iterate through elements
  for (final elem in numbers) {
    print(elem); // 1, 2, 3, 4, 5
  }
  
  // Count elements
  int count = 0;
  for (final _ in numbers) {
    count++;
  }
  print(count); // 5
  
  // Filter elements
  List<int> evens = [];
  for (final elem in numbers) {
    if (elem % 2 == 0) {
      evens.add(elem);
    }
  }
  print(evens); // [2, 4]
}

Index-Based Iteration

Index-based iteration uses a for loop with an index variable to access elements by position. It’s necessary for reverse iteration.

void main() {
  List<int> numbers = [1, 2, 3, 4, 5];
  
  // Forward iteration
  for (int i = 0; i < numbers.length; i++) {
    print(numbers[i]); // 1, 2, 3, 4, 5
  }
  
  // Reverse iteration
  for (int i = numbers.length - 1; i >= 0; i--) {
    print(numbers[i]); // 5, 4, 3, 2, 1
  }
  
  // Access by index
  int first = numbers[0]; // 1
  int last = numbers[numbers.length - 1]; // 5
}

List `toList()` Method

The toList() method converts an iterable (like a generator) into a concrete list. It’s used to materialize lazy iterables.

Iterable<int> generateNumbers() sync* {
  for (int i = 1; i <= 3; i++) {
    yield i;
  }
}

void main() {
  // Convert iterable to list
  List<int> numbers = generateNumbers().toList();
  print(numbers); // [1, 2, 3]
  
  // Use with generators
  Iterable<int> evens = [1, 2, 3, 4, 5].where((x) => x % 2 == 0);
  List<int> evenList = evens.toList();
  print(evenList); // [2, 4]
}

List `cast<T>()` Method

The cast<T>() method creates a view of a list with elements cast to type T. It’s useful for working with nested lists of unknown types.

void main() {
  List<dynamic> mixed = [1, 2, 3];
  
  // Cast to specific type
  List<int> numbers = mixed.cast<int>();
  print(numbers); // [1, 2, 3]
  
  // Use with nested lists
  List<dynamic> nested = [[1, 2], [3, 4]];
  for (final item in nested) {
    if (item is List) {
      List<int> numbers = item.cast<int>();
      print(numbers); // [1, 2], then [3, 4]
    }
  }
}

Type Checking (is)

The is operator checks if a value is of a specific type. It’s useful for handling mixed-type collections.

void main() {
  dynamic value = [1, 2, 3];
  
  // Check if value is a List
  if (value is List) {
    print('It is a list');
    // Dart knows value is List here
    print(value.length);
  }
  
  // Use in processing
  List<dynamic> mixed = [1, [2, 3], 4];
  for (final item in mixed) {
    if (item is List) {
      print('Found nested list: $item');
    } else {
      print('Found single item: $item');
    }
  }
}

Mutating vs Non-Mutating Methods

Some methods modify the original list (mutating), while others return a new list (non-mutating). Understanding this distinction is crucial.

void main() {
  List<int> original = [1, 2, 3];
  
  // Mutating method - modifies original
  original.add(4);
  print(original); // [1, 2, 3, 4] - original changed
  
  // Non-mutating method - returns new list
  List<int> doubled = original.map((x) => x * 2).toList();
  print(original); // [1, 2, 3, 4] - original unchanged
  print(doubled); // [2, 4, 6, 8] - new list
}

Introduction

Implement basic list operations.

In functional languages list operations like length, map, and reduce are very common. Implement a series of basic list operations, without using existing functions.

The precise number and names of the operations to be implemented will be track dependent to avoid conflicts with existing names, but the general operations you will implement include:

append (given two lists, add all items in the second list to the end of the first list);
concatenate (given a series of lists, combine all items in all lists into one flattened list);
filter (given a predicate and a list, return the list of all items for which predicate(item) is True);
length (given a list, return the total number of items within it);
map (given a function and a list, return the list of the results of applying function(item) on all items);
foldl (given a function, a list, and initial accumulator, fold (reduce) each item into the accumulator from the left);
foldr (given a function, a list, and an initial accumulator, fold (reduce) each item into the accumulator from the right);
reverse (given a list, return a list with all the original items, but in reversed order).

Note, the ordering in which arguments are passed to the fold functions (foldl, foldr) is significant.

Dart-specific instructions

The append method mutates the receiver. All other methods return a new List.

We can’t override builtin methods and properties: instead of length, implement count; instead of map, implement myMap.

You will be adding Extension methods to the List class. Try not to rely too much on the builtin methods and properties of List and Iterable, implement the functionality yourself as much as you can.

You’ll notice that the provided stub file uses Generics.

How do we implement list operations?

To implement basic list operations:

append: Iterate through the other list and add each element to the current list (mutates)
concat: Flatten nested lists by recursively processing items (yield lists, yield* nested lists)
filter: Iterate through list and yield only elements that pass the predicate
count: Iterate through list and count elements
myMap: Iterate through list and yield transformed elements
foldl: Start with accumulator, iterate left to right, apply function to accumulator and each element
foldr: Start with accumulator, iterate right to left, apply function to each element and accumulator
reverse: Iterate from last index to first, yield elements in reverse order

The key insight is using generator functions (sync* and yield) to create lazy iterables that can be converted to lists, avoiding intermediate collections and making the code more efficient.

Solution

extension ListOps on List {
  void append<T>(List<T> other) {
    for (final elem in other) {
      add(elem);
    }
  }

  List<T> concat<T>() {
    return _concatGen<T>().toList();
  }

  Iterable<T> _concatGen<T>() sync* {
    for (final item in this) {
      if (item is List) {
        yield* item.cast<T>();
      } else {
        yield item as T;
      }
    }
  }

  List<T> filter<T>(bool Function(T elem) predicate) {
    return _filterGen<T>(predicate).toList();
  }

  Iterable<T> _filterGen<T>(bool Function(T elem) predicate) sync* {
    for (final elem in this) {
      final typed = elem as T;
      if (predicate(typed)) yield typed;
    }
  }

  int count() {
    var c = 0;
    for (final _ in this) {
      c++;
    }
    return c;
  }

  List<T> myMap<T>(T Function(T elem) fn) {
    return _mapGen<T>(fn).toList();
  }

  Iterable<T> _mapGen<T>(T Function(T elem) fn) sync* {
    for (final elem in this) {
      yield fn(elem as T);
    }
  }

  U foldl<T, U>(U initial, U Function(U acc, T elem) fn) {
    var acc = initial;
    for (final elem in this) {
      acc = fn(acc, elem as T);
    }
    return acc;
  }

  U foldr<T, U>(U initial, U Function(T elem, U acc) fn) {
    var acc = initial;
    for (var i = length - 1; i >= 0; i--) {
      acc = fn(this[i] as T, acc);
    }
    return acc;
  }

  List<T> reverse<T>() {
    return _reverseGen<T>().toList();
  }

  Iterable<T> _reverseGen<T>() sync* {
    for (var i = length - 1; i >= 0; i--) {
      yield this[i] as T;
    }
  }
}

Let’s break down the solution:

extension ListOps on List - Extension on List type:
- Adds custom methods to all List instances
- Allows calling methods like list.count(), list.filter(...), etc.
void append<T>(List<T> other) - Append method (mutating):
- Takes another list and adds all its elements to the current list
- Mutates the receiver list
- Uses generic <T> to work with any type
for (final elem in other) - Iterate through other list:
- Loops through each element in the other list
- Processes elements one by one
add(elem) - Add element:
- Adds each element from other list to current list
- Modifies the list in place
List<T> concat<T>() - Concatenate method:
- Flattens nested lists into a single list
- Returns a new list (non-mutating)
- Delegates to generator function
Iterable<T> _concatGen<T>() sync* - Concatenate generator:
- Generator function that yields flattened elements
- Uses sync* to create a lazy iterable
if (item is List) - Check if nested list:
- Determines if current item is itself a list
- Handles nested structures
yield* item.cast<T>() - Yield all from nested list:
- Yields all elements from the nested list
- yield* recursively processes nested structures
- cast<T>() ensures correct type
yield item as T - Yield single item:
- Yields non-list items directly
- Casts to type T
List<T> filter<T>(bool Function(T elem) predicate) - Filter method:
- Returns elements that pass the predicate function
- Takes a function that returns bool
- Returns a new list
Iterable<T> _filterGen<T>(...) sync* - Filter generator:
- Generator that yields only matching elements
- Checks predicate for each element
if (predicate(typed)) yield typed - Conditional yield:
- Only yields elements that pass the predicate
- Filters elements based on condition
int count() - Count method:
- Returns the number of elements in the list
- Implements length without using built-in property
for (final _ in this) - Iterate and count:
- Loops through all elements
- Uses _ to ignore element values
- Increments counter for each element
List<T> myMap<T>(T Function(T elem) fn) - Map method:
- Transforms each element using a function
- Returns a new list with transformed elements
- Named myMap to avoid conflict with built-in map
Iterable<T> _mapGen<T>(...) sync* - Map generator:
- Generator that yields transformed elements
- Applies function to each element
yield fn(elem as T) - Yield transformed element:
- Applies the function to the element
- Yields the result
U foldl<T, U>(U initial, U Function(U acc, T elem) fn) - Fold left:
- Folds elements from left to right
- Takes initial accumulator value
- Function signature: (accumulator, element) => new accumulator
var acc = initial - Initialize accumulator:
- Starts with the initial value
- Will be updated as we process elements
acc = fn(acc, elem as T) - Update accumulator:
- Applies function to current accumulator and element
- Updates accumulator with result
- Processes left to right
U foldr<T, U>(U initial, U Function(T elem, U acc) fn) - Fold right:
- Folds elements from right to left
- Function signature: (element, accumulator) => new accumulator
- Note: parameter order is reversed from foldl
for (var i = length - 1; i >= 0; i--) - Reverse iteration:
- Starts from last index
- Decrements to first index
- Processes elements right to left
acc = fn(this[i] as T, acc) - Update accumulator (right to left):
- Applies function with element first, then accumulator
- Processes right to left
List<T> reverse<T>() - Reverse method:
- Returns a new list with elements in reverse order
- Does not mutate the original list
Iterable<T> _reverseGen<T>() sync* - Reverse generator:
- Generator that yields elements in reverse order
- Iterates from last to first index
yield this[i] as T - Yield element at index:
- Yields element at current index
- Accesses elements by position

The solution efficiently implements all basic list operations using generator functions for non-mutating operations and direct iteration for mutating operations. The use of generics makes the code work with any type, and generator functions provide lazy evaluation and avoid intermediate collections.

A video tutorial for this exercise is coming soon! In the meantime, check out my YouTube channel for more Dart and Flutter tutorials. 😉

Visit My YouTube Channel