Haskell实现shuffle函数：拆分列表并多次riffle洗牌

Hey there! Let's break this down since you're new to Haskell—splitting the list is totally manageable once you know the right tools, and we'll tie it to your existing riffle function easily.

Step 1: Splitting the Even-Length List #

Since your input list is guaranteed to be even-length, we can split it into two equal halves. Haskell has a built-in function splitAt that does exactly what we need: it takes an index and a list, then returns a tuple of the elements before the index and the elements from the index onward.

To get the midpoint of your list, just calculate half its length with length xs div 2 (since the length is even, division gives an integer with no remainder). For example:

splitAt (length [1,2,3,4,5,6] `div` 2) [1,2,3,4,5,6]
-- Returns ([1,2,3], [4,5,6])

Step 2: Building the shuffle Function #

Now that we can split the list, we need to apply the riffle operation n times. There are two straightforward ways to do this:

Option 1: Recursive Approach (Great for Learning)

Recursion is core to Haskell, so let's start here. The base case is when n=0—we just return the original list. For n>0, we split the list, apply riffle to the two halves, then recursively shuffle the result n-1 more times:

shuffle :: Int -> [a] -> [a]
shuffle 0 xs = xs  -- Base case: 0 shuffles = original list
shuffle n xs = shuffle (n-1) (riffle firstHalf secondHalf)
  where
    halfLength = length xs `div` 2
    (firstHalf, secondHalf) = splitAt halfLength xs

Option 2: Using iterate (More Concise)

Haskell's iterate function creates an infinite list of repeated applications of a function. We can use it to generate all versions of the list after 0, 1, 2, ... shuffles, then pick the n-th element:

shuffle :: Int -> [a] -> [a]
shuffle n xs = iterate riffleOnce xs !! n
  where
    riffleOnce ys = let (f, s) = splitAt (length ys `div` 2) ys in riffle f s

Verifying with Your Example #

Let's test this with your sample input shuffle 2 [1,2,3,4,5,6]:

1. First shuffle (n=1): Split [1,2,3,4,5,6] into [1,2,3] and [4,5,6]. Applying riffle gives [1,4,2,5,3,6].
2. Second shuffle (n=2): Split [1,4,2,5,3,6] into [1,4,2] and [5,3,6]. Applying riffle gives [1,5,4,3,2,6]—which matches your expected result!

A Quick Note on Performance #

Using length is simple, but it's an O(n) operation (it has to traverse the whole list to count elements). For very large lists, you could use a "two-pointer" approach to split the list in a single pass, but for most beginner use cases, splitAt and length work perfectly fine.

内容的提问来源于stack exchange，提问作者Alowishious