CODEWITHSUNDEEP
listhaskellrecursion
Alowishious
Alowishious

Reputation: 83

Splitting a list into parts then shuffling those parts: Haskell

The question is: Define a function shuffle :: Int -> [a] -> [a] that takes a natural number n and an even-lengthed list, and splits and then riffles the list n times. For example, shuffle 2 [1,2,3,4,5,6] = [1,5,4,3,2,6]. I have a function riffle that works accordingly, but I don't know how to split a list.

My riffle function is:

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

I started shuffle, I think, here is what I have:

shuffle :: Int -> [a] -> [a]
shuffle [] = []
shuffle a xs = (length xs) 'div' a

I was attempting to take a list and divide into parts specified "a". I'm new to Haskell and am still not certain how it all works: All help is appreciated.

Upvotes: 0

Views: 703

Answers (2)

dfeuer
dfeuer

Reputation: 48611

To split a list in half, with both halves in order, you should generally use a tortoise and hare algorithm.

-- split2 xs = splitAt (length xs `quot` 2) xs
split2 :: [a] -> ([a], [a])
split2 xs0 = go xs0 xs0
  where
    go (_:_:hs) (t:ts) =
      let (front, rear) = go hs ts
      in (t:front, rear)
    go _ ts = ([], ts)

This should generally be more efficient than calculating the length of the list and dividing by two. It will also work even if the list is infinite.

In this case, however, you don't need a lazy version; you're going to use the second half pretty much immediately. So you can use this more Lisp/Scheme/ML-style version if you prefer:

split2' :: [a] -> ([a], [a])
split2' xs0 = go [] xs0 xs0
  where
    go front (_:_:hs) (t:ts) = go (t:front) hs ts
    go front _ ts = (reverse front, ts)

I'm not sure which will be faster, but split2' is less susceptible to space leaks introduced by compiler transformations.

Upvotes: 5

karakfa
karakfa

Reputation: 67527

not a good shuffle, your first and last elements never move.

something like this?

> let shuffle 0 x = x
      shuffle n x = shuffle (n-1) $ uncurry riffle $ splitAt (length x `div` 2) x

or with iterate

Upvotes: 1

Related Questions