For finite even lists, these definitions take at most linear time:The length calculation and the prefix split each take time. The second operation consumes two constructors per step and emits one pair. Under the stated even-length precondition, neither definition encounters an unmatched final element.
halve :: [a] -> ([a],[a])
halve xs = splitAt (length xs `div` 2) xs
pairs :: [a] -> [(a,a)]
pairs [] = []
pairs (x:y:xs) = (x,y) : pairs xs
pairs [_] = error "pairs: odd length"Join either two halves or successive pairs:By the defining property of
unhalve :: ([a],[a]) -> [a]
unhalve (xs,ys) = xs ++ ys
unpairs :: [(a,a)] -> [a]
unpairs = foldr (\(x,y) zs -> x:y:zs) []splitAt, concatenating the two halves restores the original list. For unpairs, structural induction on the even input proves that its first pair restores its first two elements and the recursive result restores the rest. Thus both requested function compositions are the identity. Fully consuming either result takes at most linear time; list concatenation only copies the left half once.Interleave equal halves, or collect the first and second components of adjacent pairs:For halves
riffle :: [a] -> [a]
riffle = unpairs . uncurry zip . halve
unriffle :: [a] -> [a]
unriffle = unhalve . unzip . pairsas and bs of equal length, pairs (riffle xs) = zip as bs, and unzip (zip as bs) = (as,bs). Therefore unriffle (riffle xs) = xs. Conversely, starting from the adjacent pairs of any even list, separating the components, halving their concatenation and zipping them restores those same pairs. Hence riffle (unriffle xs) = xs too. Every stage takes linear time. This perfect out-shuffle leaves the first and last positions fixed.For the defined shuffle, Here the identity's period means the least positive number of applications, so the empty and two-element lists have period one. Since is odd, is invertible modulo , ensuring termination. Using
count 52 = 8. The printed assertion about seven shuffles is inconsistent with the actual permutation. Number positions from zero. On an even length , a position moves to , while the last position stays fixed. Indeed, positions in the first half move to , and positions in the second half move to . Consequently the number sought is the multiplicative order of modulo :count :: Int -> Int
count n
| n < 0 || odd n = error "count: nonnegative even length required"
| n <= 2 = 1
| otherwise = go 1 (2 `mod` m)
where
m = toInteger n - 1
go k r
| r == 1 = k
| otherwise = go (k+1) ((2*r) `mod` m)Integer for residues avoids overflow in doubling; the mathematical correctness assumes the returned period fits Int. The algorithm uses one modular update per shuffle in the period, rather than constructing each shuffled deck.For , , whereas , and are not congruent to one, ruling out every proper divisor of eight. After seven shuffles, the original position is at position , not back at .
An eight-step position cycle under the 52-card perfect out-shuffle
. Details. 
This single position already disproves a seven-step return; the modular calculation proves that the whole permutation returns after eight.
Apply the supplied bitonic-merging fact directly:For length ,
merge :: Ord a => [a] -> [a]
merge xs = rounds (levels (length xs)) xs
where
levels n
| n <= 1 = 0
| otherwise = 1 + levels (n `div` 2)
order (x,y)
| x <= y = (x,y)
| otherwise = (y,x)
pass = unpairs . map order . pairs . riffle
rounds 0 ys = ys
rounds r ys = rounds (r-1) (pass ys)levels n = k. Each pass performs exactly the required shuffle and adjacent compare-exchange operations. The supplied fact therefore proves that rounds k yields ascending order from a bitonic sequence. Each pass preserves the multiset of entries and costs , giving time for . Length one needs no pass. The definition also harmlessly returns [] on empty input.Sort the two halves ascending, reverse the second, and concatenate to form a bitonic sequence:For a power-of-two length greater than one, both halves are smaller powers of two. By induction, the recursive calls return ascending permutations of their respective inputs. Reversal makes the second half descending, so part (e)'s precondition holds and
sort :: Ord a => [a] -> [a]
sort [] = []
sort [x] = [x]
sort xs = merge (sort as ++ reverse (sort bs))
where (as,bs) = halve xsmerge sorts their concatenation without losing entries. This proves both sortedness and sorting permutation preservation. Its recurrence relation is , so summing the levels gives time. Equal keys cause no difficulty; ascending and descending here permit equality. This is a bitonic sorting algorithm. Articles by others on the same topic
There are currently no matching articles.