循环使用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应该"交织"两个列表,例如:

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

而shuffle则迭代列表项的拆分和翻转量.现在我需要定义一个函数重复,它输出重新获取原始列表需要多少次shuffle迭代.该函数定义如下:

repeats :: [Int] -> Int

我只是坚持你如何在shuffle上执行循环...我认为它与列表理解有关但我无法得到任何东西.我还没有尝试过lambda表达式,但我不认为这是必要的.顺便说一句,应该在具有偶数项目的列表上进行随机播放.有任何想法吗？

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列表并添加一个以获得所需的shuffle数量.

Answer 2

在许多情况下,您可以使用无限列表而不是"循环".这是其中之一.

prelude函数"iterate"重复将一个函数应用于一个值,所以(从内存中)

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

因此,如果您将"iterate shuffle"应用于起始列表,那么您将获得渐进式随机播放.然后使用takeWhile查找列表中与您的起点相等的第一个条目,然后使用"length"来查找它的长度.