将列表拆分为多个部分,然后将这些部分混洗:Haskell

Question

问题是:定义一个shuffle :: Int -> [a] -> [a]采用自然数n和偶数列表的函数,然后拆分然后将列表重复n次.例如,shuffle 2 [1,2,3,4,5,6] = [1,5,4,3,2,6].我有一个相应的函数riffle,但我不知道如何拆分列表.

我的浅滩功能是:

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

我开始洗牌,我想,这就是我所拥有的:

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

我试图列出一个列表并分成指定为"a"的部分.我是Haskell的新手,我仍然不确定它是如何工作的:所有的帮助都表示赞赏.

Answer 1

要将列表分成两半,按顺序将两半分开,通常应使用乌龟和野兔算法.

-- 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)

这通常比计算列表的长度并除以2更有效.即使列表是无限的,它也会起作用.

但是,在这种情况下,您不需要延迟版本; 你将立即使用下半场.因此,如果您愿意,可以使用更多Lisp/Scheme/ML风格的版本:

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)

我不确定哪个会更快,但split2'不太容易受到编译器转换引入的空间泄漏的影响.