使用 converge 生成列表的所有旋转时出现意外结果

Question

我正在尝试获取列表的所有轮换 v。因此，在 rotations 的定义中，我使用 rotateLeft 的翻转版本作为第一个分支函数（以便首先接受列表），然后是 return 列表的函数[0, 1, 2, ..., v.length-1]，收敛函数为map。

const {curry,mathMod,pipe,splitAt,reverse,unnest,converge,map,flip,length,times,identity} = require("ramda");

const v = [1,2,3,4];

const rotateLeft = curry((n,vet) => {
    const i = mathMod(n,vet.length);
    return pipe(
        splitAt(i),
        reverse,
        unnest
    )(vet);
});

const rotations = converge(map,[
    flip(rotateLeft),
    pipe(length,times(identity))
]);

rotations(v);

但是，return 这并不是我所期望的。相反，如果我按如下方式重写它，它就可以正常工作：

map(flip(rotateLeft)(v),
    pipe(length,times(identity))(v));

// gives [[1,2,3,4],[2,3,4,1],[3,4,1,2],[4,1,2,3]]

据我了解，converge 将两个分支函数应用于 v，然后将结果作为参数提供给 map。那正确吗？那为什么 rotations(v) return 不一样呢？

Code

更简洁的版本使用reduce

受你在 vanilla JS 版本的启发，我想出了以下 reduceRotations 函数，它不使用 [=18] 的索引参数=] 或以明显的方式递归。然后，当然，我以完全无意义的方式将其翻译成 vanilla Ramda。 :)

const {converge,reduce,always,append,pipe,last,head,tail,identity,unapply} = require("ramda");

const reduceRotations = (v) => {
    const rotate = (v) => append(head(v),tail(v));
    return reduce(
        (acc,_) => append(rotate(last(acc)),acc),
        [v],
        tail(v)
    );
};

const pointFreeRotations = 
    converge(reduce,[
        always(converge(append,[
            pipe(last,converge(append,[head,tail])),
            identity
        ])),
        unapply(identity),
        tail
    ]);

Code

又一个

以下等效函数使用 scan 而不是 reduce。

const {converge,scan,always,append,head,tail,identity} = require("ramda");

const scanRotations = (v) => {
    const rotate = (v) => append(head(v),tail(v));
    return scan(rotate,v,tail(v));
};

const scanPointFreeRotations =
    converge(scan,[
        always(converge(append,[head,tail])),
        identity,
        tail
    ]);

Code

Answer 1

这是因为 converge 将提供给它的最长函数的元数作为其元数。

因此，由于 flip(rotateLeft).length //=> 2 和 pipe(length,times(identity)) //=> 1，旋转的长度为 2。但您显然需要一个一元函数。最简单的修复方法是简单地将 flip(rotateLeft) 包裹在 unary:

中

const rotateLeft = curry((n,vet) => {
    const i = mathMod(n,vet.length);
    return pipe(
        splitAt(i),
        reverse,
        unnest
    )(vet);
});

const rotations = converge (map, [
  unary ( flip (rotateLeft) ),
  pipe ( length, times(identity) )
])

const v = [1,2,3,4];

console .log (
  rotations (v)
)

<script src="//cdnjs.cloudflare.com/ajax/libs/ramda/0.26.1/ramda.js"></script><script>
const {curry, mathMod, pipe, splitAt, reverse, unnest, converge, map, unary, flip, length, times, identity} = R   </script>

另请注意，这并不真的需要 Ramda 的所有机器。在 vanilla JS 中很容易做到这一点：

const rotations = v => v .map ( (_, i) => v .slice (i) .concat ( v .slice(0, i) ) )

Answer 2

作为 rotations 的这种简单递归实现的证明，有时 point-free 由大量微小函数组成的代码不值得额外的头痛 -

const rotations = ([ x, ...xs ], count = 0) =>
  count > xs.length
    ? []
    : [ [ x, ...xs ], ...rotations ([ ...xs, x ], count + 1) ]

console.log(rotations([1,2,3]))
// [ [ 1, 2, 3 ], [ 2, 3, 1 ], [ 3, 1, 2 ] ]

console.log(rotations([1,2,3,4]))
// [ [ 1, 2, 3, 4 ], [ 2, 3, 4, 1 ], [ 3, 4, 1, 2 ], [ 4, 1, 2, 3 ] ]

上面，解构赋值创建了许多中间值，但我们可以使用稍微不同的算法来解决这个问题 -

const rotations = (xs = [], i = 0) =>
  i >= xs.length
    ? []
    : [ xs.slice(i).concat(xs.slice(0, i)) ].concat(rotations(xs, i + 1))

console.log(rotations([1,2,3]))
// [ [ 1, 2, 3 ], [ 2, 3, 1 ], [ 3, 1, 2 ] ]

console.log(rotations([1,2,3,4]))
// [ [ 1, 2, 3, 4 ], [ 2, 3, 4, 1 ], [ 3, 4, 1, 2 ], [ 4, 1, 2, 3 ] ]

像您一样定义一个辅助函数是很好的卫生习惯。它还使我们的其他功能更具可读性 -

const rotate = (xs = []) =>
  xs.slice(1).concat(xs.slice(0, 1))

const rotations = (xs = [], i = 0) =>
  i >= xs.length
    ? []
    : [ xs ].concat(rotations(rotate(xs), i + 1))

console.log(rotations([1,2,3]))
// [ [ 1, 2, 3 ], [ 2, 3, 1 ], [ 3, 1, 2 ] ]

console.log(rotations([1,2,3,4]))
// [ [ 1, 2, 3, 4 ], [ 2, 3, 4, 1 ], [ 3, 4, 1, 2 ], [ 4, 1, 2, 3 ] ]

使用 converge 生成列表的所有旋转时出现意外结果

Unexpected result when using converge to generate all rotations of a list

javascript

functional-programming

ramda.js