Как определить функцию вращения

Ответ 1

Следующие

shift :: [a] -> Int -> [a]
shift l n = drop n l  ++ take n l

allRotations :: [a] -> [[a]]
allRotations l = [ shift l i | i <- [0 .. (length l) -1]]

дает

> ghci
Prelude> :l test.hs
[1 of 1] Compiling Main             ( test.hs, interpreted )
Ok, modules loaded: Main.
*Main> allRotations [1,2,3,4]
[[1,2,3,4],[2,3,4,1],[3,4,1,2],[4,1,2,3]]

который, как вы ожидаете.

Я думаю, что это достаточно читаемо, хотя и не особенно эффективно (никаких воспоминаний о предыдущих сдвигах не происходит).

Если вы заботитесь об эффективности, то

shift :: [a] -> [a]
shift [] = []
shift (x:xs) = xs ++ [x]

allRotations :: [a] -> [[a]]
allRotations l = take (length l) (iterate shift l)

позволит вам повторно использовать результаты предыдущих смен и избежать их пересчета.

Обратите внимание, что iterate возвращает бесконечный список, и из-за ленивой оценки мы всегда оцениваем его до length l в списке.

Обратите внимание, что в первой части я расширил вашу функцию сдвига, чтобы спросить, сколько сдвигается, и затем я понимаю список для allRotations.

Ответ 2

Другим способом расчета всех поворотов списка является использование предопределенных функций tails и inits. Функция tails дает список всех конечных сегментов списка, а inits выводит список всех начальных сегментов. Например,

tails [1,2,3] = [[1,2,3], [2,3], [3],   []]

inits [1,2,3] = [[],      [1],   [1,2], [1,2,3]]

То есть, если мы соединим эти списки поточечно, как указано в отступе, мы получим все вращения. Мы получаем только исходный список дважды, а именно: один раз добавляем пустой начальный сегмент в конце исходного списка и один раз, добавляя пустой конечный сегмент в начало исходного списка. Поэтому мы используем функцию init, чтобы удалить последний элемент результата применения zipWith к хвостам и именам списка. Функция zipWith применяет свой первый аргумент точечно к предоставленным спискам.

allRotations :: [a] -> [[a]]
allRotations l = init (zipWith (++) (tails l) (inits l))

Это решение имеет преимущество перед другими решениями, поскольку оно не использует length. Функция length является довольно строгой в том смысле, что она не дает результата до того, как она полностью оценит структуру списка его аргумента. Например, если мы оцениваем приложение

allRotations [1..]

то есть мы вычисляем все вращения бесконечного списка натуральных чисел, ghci с радостью начинает печатать бесконечный список в качестве первого результата. Напротив, реализация, основанная на length, как предлагается здесь, не заканчивается, поскольку она вычисляет длину бесконечного списка.

Ответ 3

shift (x:xs)  =  xs ++ [x]
rotates xs    =  take (length xs) $ iterate shift xs

iterate f x возвращает поток ( "бесконечный список" ) [x, f x, f (f x), ...]. Есть n вращения списка n -элементов, поэтому мы take первый n из них.

Ответ 4

Ответы, полученные до сих пор, отлично подходят для конечных списков, но в конечном итоге будут выходить из строя, когда будут предоставлены бесконечные списки. (Все они называют length в списке.)

shift :: [a] -> [a]
shift xs = drop 1 xs ++ take 1 xs

rotations :: [a] -> [[a]]
rotations xs = zipWith const (iterate shift xs) xs

В моем решении вместо этого используется zipWith const. zipWith const foos bars может показаться на первый взгляд идентичным foos (напомним, что const x y = x). Но список, возвращаемый из zipWith, завершается, когда заканчивается любой из входных списков.

Поэтому, когда xs является конечным, возвращаемый список имеет ту же длину, что и xs, как мы хотим; и когда xs бесконечно, возвращаемый список не будет усечен, поэтому будет бесконечным, снова, как мы хотим.

(В вашем конкретном приложении может не иметь смысла пытаться повернуть бесконечный список. С другой стороны, он может. Я отправлю этот ответ только для полноты.)

Ответ 5

Я бы предпочел следующие решения, используя встроенные функции cycle и tails:

rotations xs = take len $ map (take len) $ tails $ cycle xs where
    len = length xs 

Для вашего примера [1,2,3,4] функция cycle создает бесконечный список [1,2,3,4,1,2,3,4,1,2...]. Функция tails генерирует все возможные хвосты из данного списка, здесь [[1,2,3,4,1,2...],[2,3,4,1,2,3...],[3,4,1,2,3,4...],...]. Теперь все, что нам нужно сделать, - это сократить "хвосты" -листов до длины 4 и сократить общий список до длины 4, который выполняется с помощью take. Был введен псевдоним len, чтобы избежать повторного пересчета length xs несколько раз.

Ответ 6

Я думаю, что это будет что-то вроде этого (у меня сейчас нет ghc, поэтому я не мог попробовать)

shift (x:xs) = xs ++ [x]

rotateHelper xs 0 = []
rotateHelper xs n = xs : (rotateHelper (shift xs) (n - 1))

rotate xs = rotateHelper xs  (length xs)

Ответ 7

myRotate lst = lst : myRotateiter lst lst
  where myRotateiter (x:xs) orig
          |temp == orig = []
          |otherwise = temp : myRotateiter temp  orig               
          where temp = xs ++ [x]

Ответ 8

Я предлагаю:

rotate l = l : rotate (drop 1 l ++ take 1 l)

distinctRotations l = take (length l) (rotate l)