Closure.cs

using System;
using System.Collections.Generic;

// For clarity. In haskell, standard Dictionary is called "Map".
//
using Set1 = System.Collections.Generic.HashSet<int>;
using Map1 = System.Collections.Generic.Dictionary<int, System.Collections.Generic.HashSet<int>>;

class Closure {

  // Set to false to remove debug output.
  //
  public static bool enableDebug = true;

  // This is in interface for an accumulator of `Close`.
  //
  // It can't be a real interface, because we cannot add implementations
  // for exising types, such as `Set1` and `Map1`.
  //
  // However, `Close` requires these functions, so we pack'em in a struct
  // and pass as a parameter there.
  //
  // Remember that `Accumulator<A>` is not `A`, but a pack of methods.
  //
  // Note: the functions ARE NOT expected to change their arguments!
  //       They must return new values, leaving arguments intact!
  //
  // I did it like that, because I started imperatively, but found that I'm
  //  unable to track the changes, and made it pure functional, so it won't
  //  blow up in my face.
  //
  public struct Accumulator<A>
  {
      public Func<A, A, A>    Add     { get; set; } // `A` can be added.
      public Func<A, A, A>    Remove  { get; set; } // `A` can be subtracted.
      public Func<A, Boolean> IsEmpty { get; set; } // `A` can be empty.

      public Func<A, String>  Show    { get; set; } // `A` can be pretty-printed

      public A                Empty   { get; set; } // There must exist an empty `A`.
  }


  // So, this is our function - "the transitive closure", or "call f until it
  //  stops changing the answer".
  //
  public static A Close<A>
    ( Accumulator<A> helper  // a pack of methods to help is
    , Func<A, A>     f       // a function we are finding a closure for
    , A              start   // seed or initial value
    )
  {
    A accum      = start;
    A workingSet = start;
    while (true) {
      if (enableDebug) {
        Console.WriteLine($"workingSet = {helper.Show(workingSet)} --- accum = {helper.Show(accum)}");
      }
      workingSet = f(workingSet);                    // call `f`
      workingSet = helper.Remove(workingSet, accum); // remove already visited points

      if (helper.IsEmpty(workingSet)) { // nothing new?
        return accum;                   // yes, exit
      } else {
        accum = helper.Add(workingSet, accum); // no, continue with new points only
      }
    }
    // that's all!
  }

  // But, uhm, I can't let you go with just two things above.
  //
  // Here is an implementation of accumulator for `Set1` (aka `HashSet<int>`).
  //
  public static Accumulator<HashSet<T>> set<T>() => new Accumulator<HashSet<T>> {

    // add two sets together
    //
    Add = (x, y) => {
      var res = new HashSet<T>();

      // yes, we copy `x` over
      //
      // that is because C# still has mutable collections only in its stdlib
      // in 2021
      //
      // we can't be sure that changes in x will not shoot is in leg
      //
      foreach (var item in x) res.Add(item);
      foreach (var item in y) res.Add(item);
      return res;
    },

    // remove elements of `y` from `x`
    //
    // since `y` will be VERY BIG, and `x` kept small, we go over `x` here
    //
    Remove = (x, y) => {
      var res = new HashSet<T>();
      foreach (var item in x) {
        if (!y.Contains(item)) res.Add(item);
      }
      return res;
    },

    // I really dunno what to write here.
    //
    IsEmpty = x => x.Count == 0,

    // Debug toString(), because default ToString() is ABSO-FUCKING-LITELY USELESS.
    //
    Show = x => {
      var acc = "{ ";
      foreach (var item in x) {
        acc += item.ToString() + " ";
      }
      return acc + "}";
    },

    Empty = new HashSet<T>(),
  };


  // Return a value at key, or an empty value if there is no such key.
  //
  // I will utilize the fact we have `Empty` field in `Accumulator` here.
  //
  static V atKey<K, V> (Accumulator<V> helper, K k, Dictionary<K, V> dict) =>
    dict.ContainsKey(k)? dict[k] : helper.Empty;

  // Given and `Accumulator` for `V`, make an `Accumulator` for `Dictionary<K, V>`.
  //
  public static Accumulator<Dictionary<K, V>> mapOf<K, V>
    (Accumulator<V> set) =>
      new Accumulator<Dictionary<K, V>> {

        // merge 2 dictionaries togeter
        //
        Add = (x, y) => {
          var res = new Dictionary<K, V>();

          foreach (var pair in x) {
            res.Add(pair.Key, pair.Value);
          }

          // Sadly, we must traverse the whole `y` here.
          //
          // in haskell/F# we'd have to pay only log(len(y)) cost, not len(y)
          // but since our Dict is not a binary tree, here we are :(
          //
          // We technically could make it so the `y` is mutated, but that
          //  is an excercise left to reader ;)
          //
          foreach (var pair in y) {
            var was = atKey<K, V>(set, pair.Key, x);
            var neue = set.Add(was, pair.Value);
            res.Remove(pair.Key); // Throwing an exception if Add(k, ...) finds k? Orly?
            res.Add(pair.Key, neue);
          }

          return res;
        },

        // subtract y from x
        //
        Remove = (x, y) => {
          var res = new Dictionary<K, V>();

          // again, we only traversing `x`
          //
          foreach (var pair in x) {
            var val  = atKey(set, pair.Key, y);
            var neue = set.Remove(pair.Value, val);

            if (!set.IsEmpty(neue))
              res.Add(pair.Key, neue);
          }

          return res;
        },

        IsEmpty = x => x.Count == 0,

        Show = x => {
          var acc = "{ ";
          foreach (var item in x) {
            acc += item.Key.ToString() + ": " + set.Show(item.Value) + ", ";
          }
          return acc + "}";
        },

        Empty = new Dictionary<K, V>(),
      };

  // An analogue of `foldMap` from haskell: map `f` to an container, then `Accumulate`
  // that container into a single value using fields of `helper`.
  //
  // We can emulate it with a.ConvertAll(k).Accumulate(helper.Add, helper.Empty)
  // but mmm, eeh, VSCode doesn't show me those methods after I type "."
  //
  public static C FoldMap<A, B, C>(Accumulator<C> helper, A a, Func<B, C> k) where A : IEnumerable<B> {
    var res = helper.Empty;
    foreach (var item in a) {
      res = helper.Add(res, k(item));
    }
    return res;
  }

  // Memoise a function into a Dict, given a set of possible inputs.
  //
  public static Dictionary<A, HashSet<B>> Memoise<A, B>(HashSet<A> inputs, Func<A, HashSet<B>> f) {
    var res = new Dictionary<A, HashSet<B>>();
    foreach (var input in inputs) {
      res.Add(input, f(input));
    }
    return res;
  }

  // Turn a Dict into a function.
  //
  public static Func<A, HashSet<B>> Use<A, B>(Dictionary<A, HashSet<B>> memo) =>
    input => atKey<A, HashSet<B>>(set<B>(), input, memo);

  // Okay, so we have the machinery we need to run stuff now.
  //
  // This function finds and prints a closure of `nextItem` with a set of { 1 }
  //  as an initial value.
  //
  static void WithSet(Accumulator<Set1> set, Func<int, Set1> nextItem) {
    var start = new Set1 { 1 };

    // We call `nextItem` for all elements of the set, and then merge results
    // into another set. That's why this foldmap is here - otherwise it would
    // be a fucking 7-line lambda. But we have generalised it as `FoldMap`.
    //
    var end = Close(set, items => FoldMap(set, items, nextItem), start);

    Console.WriteLine("Result: " + set.Show(end));
  }

  // More complex example: a closure that works with map - or rather makes a map
  //  off a function.
  //
  static void WithMap(Accumulator<Map1> map, Func<int, Set1> next) {

    // I fucking hate Java, C# and other languages where type inference is
    //  _that_ shitty.
    //
    // I even had to annotate generic types for `FoldMap`! Like seriously!
    //
    // So, um, this function takes a (key, set), produces a new map
    //  for each element of the set and then merges them all into one map.
    //
    // Key is ignored.
    //
    Func<KeyValuePair<int, Set1>, Map1>
      nextItem = pair =>
        FoldMap<Set1, int, Map1>(map, pair.Value, x =>
          new Map1 { { x, next(x) } });

    var start = new Map1 { {1, next(1) } };
    var end   = Close(map, x => FoldMap(map, x, nextItem), start);

    Console.WriteLine("Result: " + map.Show(end));
  }

  public static void Main(string[] args) {

    // This is the function we are working with.
    //
    // We can think of it as a "neighbour" relation in graph.
    //
    Func<int, Set1> nextItem = item => new Set1 { (item + 1) % 10, (item + 2) % 10};

    var helper  = set<int>();
    var helper1 = mapOf<int, Set1>(helper);

    // Collect all reachable points of the graph, using the function as single-stepper.
    //
    WithSet(helper, nextItem);

    // Generate the whole graph using the function as single-stepper.
    //
    WithMap(helper1, nextItem);
  }
}