Traversal of trees

[hath995]

Hey, I'm trying to figure out how to apply shades to a tree structure. It seems a bit tricky. Here is the setup. Do you know if this is something feasible or just counter to the concepts of this library? Thanks

interface tree[] {
  val: string;
  children: tree[]
}
let treeTraversal = {
  get: node => [node].concat(node.children.flatMap(treeTraversal.get)),
  set: (x) => {},
  traversal: true
}
let example = {val:"testaa", children: [{val:"a", children:[]},{val:"testbb",children:[]}]}
//I'd like to be able to do something like the following, but I keep getting an array of empty objects or undefined
get(treeTraversal, matching(x => /^test/.test(x.val) ), 'val')(example)

mod(treeTraversal, 'val')(val => val + "abc")(example)

[hath995]

This is what I've figured out so far. I realized I needed to make the traversal generator to do the right thing for the tree structure. It seems to mostly work. It doesn't fully comply with the traversal type signature, and it feels odd that get returns a different type than mod.

It also doesn't quite work for reducer generators...

function treeTraversalGen(traversal = all) {
  let treeTraversal = {
    get: (node) => {
      let result = get(traversal)([node])
      result = result.concat(...node.children.flatMap(treeTraversal.get))
      return result;
    },
    mod: (fn) => (node) => {
      let result = mod(traversal)(fn)([{...node}])
      result[0].children = mod(traversal)(treeTraversal.mod(fn))(result[0].children)
      return result[0]
    },
    traversal: true
  }
  return treeTraversal;
}
get(treeTraversalGen(matching(x => /^test/.test(x.val) ) ), 'val')(example)
mod(treeTraversalGen(matching(x => /^test/.test(x.val) ) ), 'val')(val => val + "abc")(example)

 mod(treeTraversalGen( minBy(x => x.val.length)), 'val')(val => val + "abc")(example)

[hath995]

I misunderstood the reducer generators and keep thinking the lenses are applied to the whole result and not their individual focus. Might mention that in the docs as a gotcha.

Also set() and mod() are mentioned in the docs but not listed in the docs api.

[jamesmcnamara]

Yes and no. You ask a very good question.

First the yes. In your first example, your get function flattened the tree into an array, and then you used the built-in matching later (It's important to note that matching only works for linear collections, like Arrays, Maps or Sets. This might be why you're having difficulty getting it to work). The limitation of this is that you lose the tree structure turning it into a flat array; I suspect you recognized that by the difficulty you had writing the mod function, because there's no way to faithfully reconstruct the tree from the resulting array.

But if you're ok with these compromises, the easiest thing is to just flatten the tree in the first place, and then use all the built in traversals that work for arrays.

import { get, matching } from 'shades';

interface Tree<A> {
  val: A;
  children: Tree<A>[];
}

const flatten = <A>(tree: Tree<A>): A[] =>
  [tree.val].concat(tree.children.flatMap(flatten));

const example = {
  val: 'testaa',
  children: [{ val: 'a', children: [] }, { val: 'testbb', children: [] }]
};

get(matching((val: string) => /test/.test(val)))(flatten(example));

However, if you want to maintain the tree structure, and apply transformations, etc. over it or write custom Traversal types, we're out of luck, because TS doesn't support a type feature called Higher Kinded Types. Because of this, shades doesn't know how to transform a Tree<A> into a Tree<B> when the type Tree isn't known to shades. (Actually there is a way we might be able to do this with fp-ts but the implementation for users would be complex)

However, if we drop the TS and just ask if we can do it with the JS library, the answer is again, yes! But we gotta be pretty crafty. The key (as hinted at above) is that we need a way to map a Tree. If your structure has a map function, shades will use that automatically, so let's instead try writing a class for our tree:

class Tree {
  constructor(val, children = []) {
    this.val = val;
    this.children = children || [];
  }

  map(f) {
    return new Tree(
      f(this.val),
      this.children.map(child => child.map(f))
    );
  }
}

const john = { name: 'john', age: 12 };
const liz = { name: 'liz', age: 10 };
const james = { name: 'james', age: 3 };

const example = new Tree(john, [new Tree(liz), new Tree(james)]);

Now we can't use any of the built in Traversals, because they are only for linear collections, and not trees. So let's create our own Traversal called tall (tree all) that will allow us to focus on all the nodes in our tree.

const tall = {
  get: tree => tree,
  mod: f => t => t.map(f),
  traversal: true
};

get(tall, 'name')(example)

And your result is:

Tree { val: 12, children: [ 
    Tree { val: 3, children: [] }, 
    Tree { val: 3, children: [] } 
] }

Or to get their names:

get(tall, 'name')(example)

produces

Tree { val: 'john', children: [ 
    Tree { val: 'liz', children: [] }, 
    Tree { val: 'james', children: [] } 
] }

Finally, to do something like matching, we again can't use the built-in matching because it's only for collections, so we'll write our own tmatching. That first requires us to write a few classic functional programming functions: a tfilter function that filters out the nodes of a tree that don't satisfy some predicate function, and a tmapfilter which maps a function f over all nodes that satisfy some predicate pred:

const tfilter = pred => tree => {
  if (pred(tree.val)) {
    return new Tree(tree.val, tree.children.map(tfilter(pred)));
  } else {
    const [fst, ...rest] = tree.children.map(tfilter(pred));
    return new Tree(fst.val, fst.children.concat(rest));
  }
};

const tfiltermap = pred => f => tree =>
  new Tree(
    pred(tree.val) ? f(tree.val) : tree.val,
    tree.children.map(tfiltermap(pred)(f))
  );

And then we can use that to write tmatching:

const tmatching = pred => ({
  get: tfilter(pred),
  mod: tfiltermap(pred),
  traversal: true
});

So now putting it all together, filtering down your tree to just those users who have an age greater than 6 and adding 'abc' to their name looks like:

mod(tmatching(user => user.age > 6), 'name')(name => name + 'abc')(example)

and produces

Tree {
  val: { name: 'johnabc', age: 12 },
  children:
   [ Tree { val: { name: 'lizabc', age: 10 }, children: [] },
     Tree { val: { name: 'james', age: 3 }, children: [] } ] }

Hope this was helpful, and I'll look into whether I can add fp-ts so that we could get TS support if you tried to do this.

[hath995]

Definitely very interesting. Thanks for the help!

I haven't tried to add fp-ts but I've had my eye on it. I haven't jumped in because it feels a bit too heavy to incorporate in projects at work, but I found shades a very approachable and pragmatic solution that I do want to use in a professional setting. However, my use case involves an awful lot of trees...