Haskell вращает список списков

Я пытаюсь реализовать следующую функцию в Haskell, это рекурсивный обход, который получает Int и список списков [[Int]] и сдвигает элементы внутренних списков вправо без изменения размера списков. Мне удалось получить список с номерами в правильном порядке, но я не смог вставить их обратно в соответствующие подсписки.

shift_right::Int->[[Int]]->[[Int]]

пример №1:

shift_right 1 [[1,2,3],[4,5,6]] => [[6,1,2],[3,4,5]]

пример №2:

shift_right 3 [[],[1],[2,3],[4,5,6]] => [[],[4],[5,6],[1,2,3]]

list recursion nested-lists functional-programming haskell
person Gerardo Galan    schedule 05.05.2020    source источник
comment
Я бы сделал это, выполнив map length, чтобы получить длину всех подсписков, concat, чтобы сгладить вложенный список, сдвинув весь этот сглаженный список, а затем повторно разбив сглаженный сдвинутый список, используя длины, которые вы получили на первом шаге.   -  person bradrn    schedule 05.05.2020
comment
Можете ли вы поделиться тем, что вы сделали до сих пор?   -  person lsmor    schedule 05.05.2020

Ответы (1)


arrow_upward
1
arrow_downward

Если предположить, что пустые списки появляются только в начале и никогда не появляются в середине, то один из подходов может заключаться в том, чтобы сначала найти способ сделать одно вращение, а затем повторить одно и то же действие n раз для n вращений. Я думаю, мы можем использовать mapAccumL для этой цели.

m = [[],[1],[2,3],[4,5,6]]
s l = es ++ (rem ++ ls) : lss
      where
      (rem, (ls:lss)) = mapAccumL shifter [] fs
      shifter a bs    = ([last bs], a ++ (init bs))
      (es,fs)         = span (== []) l              -- split empties and fulls

λ> s m
[[],[6],[1,2],[3,4,5]]

λ> s [[],[6],[1,2],[3,4,5]] -- carry from previous answer
[[],[5],[6,1],[2,3,4]]

λ> s [[],[5],[6,1],[2,3,4]] -- carry from previous answer
[[],[4],[5,6],[1,2,3]]

Так что теперь... так как вы вообще не пытаетесь, ваша обязанность - придумать код, который вызывает эту функцию (или часть этой функции) n раз за n оборотов Подсказка: желательно без конкатенации тары. .

person Redu    schedule 05.05.2020
comment
предположение кажется действительно произвольным. декларативный подход может заключаться в заполнении любой заданной (древовидной) структуры из линейного набора значений, взятых (со сдвигом) из края той же структуры (т.е. сплющенного списка). (Я ответил что-то подобное один или два раза, с CPS-кодом на Scheme/псевдо-Haskell). :) Я думаю, что этот подход может быть применим и здесь. - person Will Ness; 05.05.2020
comment
@WillNess Я основывал свое предположение на том, что данные тестовые примеры сортируются по длине, но да, вы все равно можете называть это произвольным. Согласитесь, что выравнивание, вращение и реконструкция вложенной структуры путем повторения исходного вложенного списка является хорошей идеей и, скорее всего, будет гораздо более эффективной. - person Redu; 05.05.2020