[raleigh.rb] The Ruby shuffle

Brian Adkins info at lojic.com
Wed Dec 17 15:28:57 EST 2008


A friend of mine mentioned a little algorithm for shuffling a deck of
cards by splitting it in half and interleaving cards from each half. In
Ruby, I came up with the following:

def shuffle xs
   n = xs.length / 2
   xs[0...n].zip(xs[n..-1]).flatten
end

then shortened a bit to compare with various Haskell versions below:

shuffle = lambda {|xs| n = xs.length / 2; xs[0...n].zip(xs[n..-1]).flatten }

I know this is a Ruby list, but I thought I'd share the Haskell versions
I collected (mostly from others except for the 1st two) while
experimenting.

I think Ruby compares favorably to Haskell (except for speed) on this
exercise even though Haskell shines on this type of problem.

-- My first Haskell attempt
shuffle1 xs = concat [[fst x, snd x] | x <- uncurry zip (splitAt (length
xs `div` 2) xs)]

-- My second attempt. Create a flatten_tup2 function: [(a,b),(c,d)] =>
[a,b,c,d]
shuffle2 xs = flatten_tup2 (uncurry zip (splitAt (length xs `div` 2) xs))
     where
       flatten_tup2 [] = []
       flatten_tup2 ((a,b):xs) = a : b : flatten_tup2 xs

-- #haskell help
-- Implement flatten_tup2 with foldr
shuffle3 xs = flatten_tup2 (uncurry zip (splitAt (length xs `div` 2) xs))
     where
       flatten_tup2 = foldr (\(a,b) c -> a:b:c) []

-- #haskell help
shuffle4 xs = do (x,y) <- uncurry zip (splitAt (length xs `div` 2) xs);
[x,y]

-- #haskell help
shuffle5 xs = [z | (x,y) <- uncurry zip (splitAt (length xs `div` 2)
xs), z <- [x,y]]

-- discovered parallel comprehensions. requires: ghci -XParallelListComp
-- using | instead of , causes the generators to operate in parallel
shuffle6 xs = concat [[x,y] | x <- left | y <- right]
     where
       (left, right) = splitAt (length xs `div` 2) xs

-- comp.lang.haskel, Dirk Thierbach
-- compare to shuffle1 - remove fst, snd by pattern matching
shuffle7 xs = concat [[x,y] | (x,y) <- uncurry zip (splitAt (length xs
`div` 2) xs)]

-- comp.lang.haskel, Dirk Thierbach
-- interleave operator "AFAIK by Mark Jones"
(/\/) :: [a] -> [a] -> [a]
[]     /\/ ys = ys
(x:xs) /\/ ys = x : (ys /\/ xs)
shuffle8 xs = uncurry (/\/) $ splitAt (length xs `div` 2) $ xs

-- comp.lang.haskell Lauri Alanko
-- using parallel list comprehensions (same as mine above)
shuffle9 xs = concat [[a, b] | a <- l1 | b <- l2]
     where (l1, l2) = splitAt (length xs `div` 2) xs

-- comp.lang.haskell Lauri Alanko
-- w/o list comprehensions
shuffle10 xs = concat (zipWith (\a b -> [a, b]) l1 l2)
     where (l1, l2) = splitAt (length xs `div` 2) xs

-- comp.lang.haskel, Dirk Thierbach
-- different algorithm, but interesting
everySnd []  = []
everySnd [x] = [x]
everySnd (x:_:xs) = x : everySnd xs
shuffle9 xs = everySnd xs ++ everySnd (tail xs)



-- 
Brian Adkins
Lojic Technologies, LLC
http://lojic.com/
919-946-7547 (mobile)




More information about the raleigh-rb-members mailing list