DEV Community

loading...

Handling Folds that require non-empty data structures

iquardt profile image Iven Marquardt ・1 min read

Some folds (aka reduce) don't include an accumulator or initial value and thus require a non-empty foldable data structure, a variadic maxn fold for instance. Such folds come along with two issues though.

The first issue concerns the type. With reduce we can express asymetric types, because the accumulator can have a different type than the elements of the Foldable, e.g. we can reduce [Number,Number,Number] to String. Without an accumulator we can only express symetric types.

The second issue concerns the case when we pass an empty data structure. Without an accumulator there is nothing to return. We can through an error what would render the function partial.

Here is a fold for non-empty Foldable types that solves both issues in a clean functional way:

const arrFold1 = f => g => xs => {
//                    ^ A
  let acc;

  if (xs.length === 0)
    return None;
//         ^^^^ B

  acc = g(xs[0]);

  for (let i = 1; i < xs.length; i++)
    acc = f(acc) (xs[i], i);

  return Some(acc);
//       ^^^^^^^^^ B
};

const maxn = ({fold1, max}) => tx =>
  fold1(x => y =>
    max(x) (y)) (x => x) (tx);

const numMax = m => n =>
  n > m ? n : m;

maxn({fold1: arrFold1, max: numMax})
  ([1,2,30,4,5,6]); // Some(30)

maxn({fold1: arrFold1, max: numMax})
  ([]); // None
Enter fullscreen mode Exit fullscreen mode

run code

Instead of an accumulator arrFold1 expects an unary function (A) that may or may not transform the first element's type. If an empty structure is provided, it returns None and Some(a) (B) otherwise.

This mimplementation is part of the scriptum FP lib

Discussion

pic
Editor guide