Зацикливание на функции в Haskell

Question

Я просто озадачен этим, это петля типа Haskell, которую я не могу понять, как писать. В принципе, я определил три функции: split, riffle и shuffle.

split :: [a] -> ([a],[a]) 
split xs = splitAt (length xs `div` 2) xs 

riffle :: [a] -> [a] -> [a] 
riffle xs [] = xs 
riffle [] ys = ys 
riffle (x:xs) (y:ys) = x:y:riffle xs ys 

shuffle :: Int -> [a] -> [a] 
shuffle 0 xs = xs 
shuffle n xs = shuffle (n-1) (riffle a b) 
    where (a, b) = split xs 

В основном расколоть просто разбивает список пополам, желобок должен «чередование» два списков, так, например:

riffle [1,2,3] [4,5,6] = [1,4,2,5,3,6] 

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

repeats :: [Int] -> Int 

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

Answer 1

Одним из способов решения этой проблемы является использование лени и использование iterate для создания бесконечного списка повторных перетасовки ввода.

> iterate (uncurry riffle . split) "ABCDEF" 
["ABCDEF","ADBECF","AEDCBF","ACEBDF","ABCDEF","ADBECF","AEDCBF","ACEBDF", ...] 

Первый элемент списка является оригинальным один, поэтому мы опускаем, что с tail, а затем использовать takeWhile, чтобы получить те, которые отличаются от оригинала.

> takeWhile (/= "ABCDEF") . tail $ iterate (uncurry riffle . split) "ABCDEF" 
["ADBECF","AEDCBF","ACEBDF"] 

Теперь вам просто нужно взять length из этого списка и добавьте, чтобы получить необходимое количество перетасовки.

Answer 2

Во многих случаях вы можете использовать бесконечный список, а не «цикл». Это одна из них.

Функция прелюдия «перебирать» неоднократно применяет функцию к значению, так (из памяти)

iterate f x = [x, f x, f (f x), f (f (f x)) ....] 

Итак, если применить «итерационный перетасовать» в стартовом списке, то вы получите прогрессивный перетасовать. Затем используйте takeWhile, чтобы найти первую запись в списке, которая равна вашей начальной точке, а затем «length», чтобы узнать, как долго это происходит.

Answer 3

В Haskell итерация чаще всего выражается с использованием рекурсии, а не сквозной.

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

Возможно, вы можете заполнить пробелы в следующем коде?

repeats xs = iter 1 (...) where 
    iter n ys = if ys == xs 
     then n 
     else iter (...) (...) 

Альтернативный подход заключается в использовании лень Haskell и сделать это с бесконечным списком, с помощью функции высшего порядка iterate, который многократно применяет функцию к исходному аргументу:

repeats xs = (...) $ takeWhile (...) $ iterate (shuffle 1) (...) 

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