Flattening a nested Lazy List that may or not have children with FP-TS or Ramda?

Question

I just learned about lift and applicatives and on my quest to trying to understand these structures I am trying to implement a real use case.

I have a List (array) that is lazy, meaning that I can't get the count of items or their children until I load it. getting the nodes and loading it is async, same for its nested children (if any).

so if I would have the structure below:

[{title:"test1",children:[]},{title:"test2",children:[{title:"test2_1",children:[]}]}]

For each one of the children I don't know if they have children until I load the node and check the children count.

How could I check the entire list with FP (regardless of how nested it can go) either:

-By loading and checking each node at the time. and stop when we find a match or run out of nodes.

or

-By loading all nodes then (probably nesting it into Rights() and Lefts()), flattening into a single list, then foldmapping for a item by title with a predicate just like in the example below.

This is what I know works for the first match of a element in a non nested array:

[{title:"test1"},{title:"test2"},{title:"test3"}] //structure we are loading

const find= (l,f)=>l.foldMap(x=>First(f(x)?Right(x):Left()),First.empty())

const nodes = await getNodes() //not gonna even put in a type just to illustrate that getting and loading the nodes is async. 
const list = List(await load(nodes)) //not gonna even put in a type just to illustrate that getting and loading the nodes is async. 

console.log(find(list,x=>x.title==='test3').fold(x=>x).fold(console.error,x=>x)) 

Edit: current imperative working code:

This is a sharepoint code that will get all nested navigation nodes from the globalNav. The important thing is I want to understand how I can turn this into a FP implementation preferable using applicatives.

GetNavigationNodeChildren = node => node.get_children();
GetNavigationNodeRoot = spCtx => spCtx.get_web()
  .get_navigation().get_topNavigationBar();
ExecQuery = spCtx => resource => {
  return new Promise((res, rej) => spCtx.executeQueryAsync(
    () => res(resource),
    (s, a) => rej({ s, a }),
  ));
};
LoadResource = spCtx => resource => (spCtx.load(resource) ? resource : resource);
LoadAndExec = spCtx => async resource => {
    LoadResource(spCtx)(resource )
    await ExecQuery(spCtx)(resource )
    return resource
}
getAll = spCtx=> async resource=> {
    return {node:await LoadAndExec(spCtx)(resource),children:await hasChildren(c)(resource.get_children())}
}
hasChildren = spCtx => async resource => {
    LoadResource(spCtx)(resource )
    await ExecQuery(spCtx)(resource )
    return Promise.all(resource.get_count()>0?resource.get_objectData().$1G_0.map(await getAll(spCtx)):[])
}

c=new SP.ClientContext()
root=GetNavigationNodeRoot(c)
await LoadAndExec(c)(root)
all=await hasChildren(c)(root)

PS: Look... The idea is to learn and understand FP, please if all you have to say is that I don't need to change the code/I am making it complicated... That is really not the point of the question.

Answer 1

It seems like you want to retrieve all the children of a nested root navigation node:

import * as T from 'fp-ts/Task'

// Something like this

interface NavigationNode {
  readonly title: string
}

declare const getNavChildren: (node: NavigationNode) => T.Task<NavigationNode[]>

const flattenNavNode = (node: NavigationNode): T.Task<readonly NavigationNode[]> => {
  // ... do something with getNavChildren to flatten the node
}

A Task<A> is simply () => Promise<A>, that is, a function that returns a Promise. This represents an asynchronous side effect.

---

One way you could implement flattenNavNode is like this:

import * as RA from 'fp-ts/ReadonlyArray'
import {flow, pipe} from 'fp-ts/function'

const flattenNavNode = (node: NavigationNode): T.Task<readonly NavigationNode[]> =>
  pipe(
    getNavChildren(node),                     // 1
    T.chain(T.traverseArray(flattenNavNode)), // 2
    T.map(flow(RA.flatten, RA.prepend(node))) // 3
  )

pipe pipes a value through multiple functions (pipe(a, ab, bc) is equivalent to bc(ab(a))). Let’s go through this function pipeline (I’ve omitted some readonlys for brevity):

1. Get the children of the navigation node. We now have a Task<NavigationNode[]>.

2. This is the recursive part. We want to get all the children at all depths, so we must flatten out each one of the children from the original node.

   Getting the children of the children is going be asynchronous and return some Task, but the array of children is wrapped up in a Task already from step 1, so we use chain:

   declare const chain: <A, B>(f: (a: A) => Task<B>) => (ma: Task<A>) => Task<B>
   

   This is analogous to using flatMap on an array.

   Inside the T.chain we have a NavigationNode[]. You might think of using RA.map(flattenNavNode) to get the children of each node, but that would result in a Task<NavigationNode[]>[] (Array<Task<...>>) and we need to return a Task directly from chain.

   T.traverseArray allows us to return a Task<NavigationNode[][]> (Task<Array<...>>) instead:

   declare const traverseArray: <A, B>(f: (a: A) => Task<B>) => (as: readonly A[]) => Task<readonly B[]>
   

   This executes the Tasks in parallel (T.traverseArray(f)(xs) is analogous to Promise.all(xs.map(f))), which is the default in fp-ts. T.traverseSeqArray will traverse the array sequentially, which is probably not what you want.

   This is a specialised and more efficient variant of traverse, which comes from Traversable.

3. It looks like we’re almost done — we need a Task<NavigationNode[]>, and we have a Task<NavigationNode[][]>. However, we haven’t included the original node in this array, and we also need to flatten the result.

   First, we use T.map to work on the NavigationNode[][] inside the Task. Using flow, which is left-to-right function composition, we first RA.flatten the array of arrays, and then RA.prepend the original node to the flattened array.

---

A different way of going about it is to use a (rose) Tree.

type Forest<A> = Array<Tree<A>>

interface Tree<A> {
  readonly value: A
  readonly forest: Forest<A>
}

fp-ts even comes with unfoldTreeM that allows you to build a tree in the context of a monad:

import {pipe} from 'fp-ts/function'
import type {Tree} from 'fp-ts/Tree'

const navNodeToTree = (node: NavigationNode): T.Task<Tree<NavigationNode>> =>
  unfoldTreeM(
    T.Monad // use the Task monad
  )(
    node, // root node
    // Type annotations not necessary but I added them for clarity
    (node: NavigationNode): T.Task<[value: A, forest: A[]]> =>
      pipe(
        getChildren(node),
        T.map(children => [node, children])
      )
  )

Then you could flatten the tree:

import * as A from 'fp-ts/Array'
import * as RA from 'fp-ts/ReadonlyArray'
import {flow} from 'fp-ts/function'
import type {Forest} from 'fp-ts/Tree'

const flattenForest: <A>(forest: Forest<A>) => readonly A[] = RA.chain(
  ({value, forest}) => [value, ...flattenForest(forest)]
)

// (node: NavigationNode) => T.Task<readonly NavigationNode[]>
const flattenNavNode = flow(
  // make the tree
  navNodeToTree,
  T.map(
    flow(
      // make a forest out of the tree
      // equivalent to x => [x]
      // I’m using the Array instead of the ReadonlyArray module because
      // Forest is defined as a mutable, not readonly, array for some reason
      A.of,
      // flatten the forest
      flattenForest
    )
  )
)