jq morphisms

morph.jq

## Definitions

# Functor map
def fmap(f):
  if type == "object" then
    map_values(f)
  else
    if type == "array" then
      map(f)
    else
      .
    end
  end;

# Catamorphism (same as https://stedolan.github.io/jq/manual/#walk(f))
def cata(f): fmap(cata(f)) | f;

# Anamorphism
def ana(f): f | fmap(ana(f));

# Hylomorphism
def hylo(f; g): f | fmap(hylo(f; g)) | g;

## Examples

# Input: [1, [2, [3, 4]]]
# Output: 10
def deep_array_sum: cata(
  (numbers | .) //
  (arrays | add)
);

# Input: [1, 4, 8, 5, 3]
# Output: [[],1,[[[],3,[]],4,[[[],5,[]],8,[]]]]
def binary_search_tree: ana(
  (arrays |
    select(length > 0) |
    .[0] as $pivot |
    map(select(. < $pivot)) as $left |
    map(select(. > $pivot)) as $right |
    [$left, $pivot, $right]
  ) // .
);

# Input: [1, 4, 8, 5, 3]
# Output: [1,3,4,5,8]
def quicksort: hylo(
  (arrays |
    select(unique | length > 1) |
    .[0] as $pivot |
    map(select(. < $pivot)) as $left |
    map(select(. == $pivot)) as $pivots |
    map(select(. > $pivot)) as $right |
    {left: $left, pivots: $pivots, right: $right}
  ) // .;
  (objects |
    .left + .pivots + .right
  ) // .
);