FP:树-地图，折叠，每一个。多么?

Question

我有一个工作OOP代码，它将图形元素的组合递归地呈现到画布上。有相当多的不喜欢它，我正在试着看看一个功能版本会是什么样子。

当然，我们可以编写一个专门的递归纯函数，但是由于框架涉及类似的算法，我想：

• 利用函数组合的能力。
• 看看FP和它的数据管道范式(通过纯函数转换数据)是如何将自己转换成比列表(树/图)更复杂的结构和更少的琐碎算法(比如，通过顺序迭代列表来查找所有奇数)。

在Lazy.js的启发下，我开始编写代码，并取得了以下成绩：

LazyTree.from( drawing )
    .keepNodes( visible )
    .keepChildrenOf( nonClipping )
    .traverse( log );

但是关于地图，和折叠-我有许多未回答的问题。

目标

下面是我试图解决的问题的简化版本：

数据

矩形的组成(层次结构)。每个边界以相对坐标(与其父坐标)为单位：

const drawing = {
    name: 'Face',
    bounds: { x: 10, y: 10, w: 100, h: 100 },
    children: [{
        name: 'Left eye',
        bounds: { x: 10, y: 10, w: 20, h: 20 }, // Abs: (20, 20, 20, 20)
        children: [{
            name: 'Left pupil',
            bounds: { x: 5, y: 5, w: 10, h: 10 } // Abs: (25, 25, 10, 10)
        }]
    },{
        name: 'Right eye',
        bounds: { x: 70, y: 10, w: 20, h: 20 }, // Abs: (80, 20, 20, 20)
        children: [{
            name: 'Right pupil',
            bounds: { x: 5, y: 5, w: 10, h: 10 } // Abs: (85, 25, 10, 10)
        }]
    }]
};

任务- getAbsoluteBounds

任务是将此组合转换为具有绝对坐标的组合(如注释中所示)。

问题与思考

折叠？

一个子的绝对坐标是它的相对坐标被它的父绝对坐标转换。因此，折叠及其累加器可能会这样做。

但是折叠是与catamorphism和动词相关联的，比如组合，并且通常返回一个值。

所讨论的转换使用一棵树，并返回一个相同的结构，但具有不同的值--因此听起来更像是一个accumulator.映射，但是一个需要一个的转换。

就累加器而言，值得注意的是，特定节点的所有子节点都应该得到相同的累加器。对于上面的数据，Left eye和Right eye都应该得到Face的绝对坐标(与Right eye获得Left eye的返回累加器的深度第一次遍历相反)。

还有一件事我不清楚，那就是谁应该负责构建输出树。它应该是高阶函数(折叠、映射或其他函数)，还是应该是聚合器？

停止条件

与上一节相关的是，考虑所有矩形来裁剪它们的子部分，以及以下组合：

const drawing = {
    name: 'Parent',
    bounds: { x: 10, y: 10, w: 10, h: 10 },
    children: [{
        name: 'Child',
        bounds: { x: 1000000, y: 1000000, w: 10, h: 10 }, 
        children: [{
            name: 'Grandchild',
            bounds: { x: 5, y: 5, w: 5, h: 5 }
        }]
    }]
};

Child边界与其父(Parent)无关，所以当遍历到Child (没有点遍历到Grandchild)时，分支遍历应该停止。

问题是:如何用折叠功能实现这一点？一种解决方案是当累加器返回一个约定的值(例如undefined)时停止分支遍历。但这在某种程度上背离了lists的折叠API。

探视前后

绘制算法包括：

fill( shape );
renderChildren( shape );
stroke( shape );

我想知道如何用像traverse()或each()这样的东西来实现这一点。这些应该进行2次回调(前，后)？

遍历策略

树遍历可以是：

• 深度或宽度优先。
• 自顶向下的或自下而上的(对于后者，使用参见一个转换AST的专门示例 )。

有了列表，我们就有了像reverse()这样的函数。Lazy.js允许将添加自定义迭代器链接起来。

因此，FP处理遍历策略的方法似乎是一种转换函数。还有别的事吗？

摘要

我已经谈到了在使用数据管道模型为树结构实现呈现算法时遇到的一些挑战。

我怀疑这里是否还有其他FP方法更合适？也许数据管道模型不适合这类问题。或者，我应该简单地忘记您在FP库中看到的API(它几乎只处理列表)，并创建一个适合当前任务的API(例如，具有一个也涉及累加器的map函数)。

我找不到任何专门用于树的FP库，那里的信息通常仅限于非常简单的问题。

因此，希望有人能用“这就是该怎么做”这样的方式来回答。

Answer 1

据我所知，你可以这样做。

它将继续遍历那些保留在父边界内的项目，将它们的坐标转换为绝对坐标，然后再将它们呈现出来。但是，如果孩子的边界与父母的边界重叠，那么孩子及其后代就会被跳过。没有转换为绝对坐标和渲染为这些。

​

function render(bounds){
  console.log("Rendered:", bounds);
}

function relToAbs(o, b = {x: 0, y:0, w:Infinity, h:Infinity}, go = true){
  go = o.bounds.x < b.w && o.bounds.y < b.h ? (o.bounds.x += b.x, o.bounds.y += b.y, render(o.bounds), go) : !go;
  o.children && go && (o.children = o.children.map(p => relToAbs(p,o.bounds,go)));
  return o;
}

var drawing = {    name: 'Face',
                 bounds: { x: 10, y: 10, w: 100, h: 100 },
               children: [{    name: 'Left eye',
                             bounds: { x: 200, y: 10, w: 20, h: 20 },          // Abs: (20, 20, 20, 20)
                           children: [{    name: 'Left pupil',
                                         bounds: { x: 5, y: 5, w: 10, h: 10 } // Abs: (25, 25, 10, 10)
                                      }]
                          },
                          {    name: 'Right eye',
                             bounds: { x: 70, y: 10, w: 20, h: 20 },          // Abs: (80, 20, 20, 20)
                           children: [{    name: 'Right pupil',
                                         bounds: { x: 5, y: 5, w: 10, h: 10 } // Abs: (85, 25, 10, 10)
                                      }]
                          }]
              };
console.log(JSON.stringify(relToAbs(drawing),null,2));

​