Immutable List Style

This was a great example. I wanted to take some time to demonstrate an idiomatic, immutable-style list-processing approach to solving this. In FP, the most powerful general-purpose immutable list-processing functions are the fold functions. They iterate through a list one item at a time, keeping track of a 'current value' which can be anything, and apply some folding function to that current value and each list item to come up with the next 'current value'. There are different types of folding functions which work in slightly different ways, you can learn about them in functional programming books or courses.

Long story short, the appropriate fold function for your list is List.fold_left, which walks through each item of your list from left to right, applying the given function. A simple example: let result = List.fold_left (/) 36 [1, 2, 3]. Now, result = 6, which is 36 / 1 / 2 / 3.

Here's the solution to your example using List.fold_left:

type data_item = {
  symbol: string,
  next: bool,
};

/* Convenience function for making data items. */
let make_data_item = (symbol, next) => {symbol, next};

let process = (data: list(data_item)) => {
  /*
   We track the current symbol as well as the result list in the folding function.
   */
  let fold_func = ((current, result), {symbol, next}) =>
    if (next) {
      (symbol, [current, ...result]);
    } else {
      (current ++ symbol, result);
    };

  let (current, result) = List.fold_left(fold_func, ("", []), data);
  /*
   We need to reverse the result list because `[el, ...els]` above actually
   builds it up in the _opposite_ order to the original input list.
   */
  (current, List.rev(result));
};

let result =
  process([
    make_data_item("a", false),
    make_data_item("b", false),
    make_data_item("c", true),
    make_data_item("d", false),
  ]);

idkjs/yawaramin.md

idkjs commented Jul 6, 2021