Неожиданный результат при использовании сходятся для генерации всех вращений списка - PullRequest
Новая
       6

Неожиданный результат при использовании сходятся для генерации всех вращений списка

4 голосов
/ 23 мая 2019

Я пытаюсь получить все повороты списка v.Итак, в определении rotations я использую перевернутую версию rotateLeft в качестве первой функции ветвления (для того, чтобы сначала принять список), а затем функцию, которая возвращает список [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);

Однако, это не возвращает того, что я ожидал.Вместо этого он работает нормально, если я переписываю это следующим образом: 

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) не возвращает то же самое?

Код

Более краткая версия с использованием reduce

Вдохновленный вашими версиями в vanilla JS , я придумал следующую reduceRotations функцию, которая не использует параметр индекса map или рекурсию очевидным образом.Затем, конечно, я перевел это в 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
    ]);

Код

Еще один

В следующих эквивалентных функциях вместо * используется scan1045 *. 

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
    ]);

Код

Ответы [ 2 ]

4 голосов
/ 23 мая 2019

Это потому, что 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>

Также обратите внимание, что на самом деле это не требует всей техники Рамды.Это довольно легко сделать в ванильном JS: 

const rotations = v => v .map ( (_, i) => v .slice (i) .concat ( v .slice(0, i) ) )
3 голосов
/ 23 мая 2019

Как доказательство этой простой рекурсивной реализации rotations, иногда бессмысленный код, состоящий из множества мелких функций, просто не стоит дополнительной головной боли - 

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 ] ]
...