简单的Haskell分割列表

Question

我有一个函数，它接收一个列表并返回以给定元素n为分界点的两个子列表。但是，我只需要将其平均分成两份，长度为奇数的列表具有更大的第一个子列表。

splitlist :: [a] -> Int -> ([a],[a])
splitlist [] = ([],[])
splitlist l@(x : xs) n | n > 0     = (x : ys, zs)
               | otherwise = (l, [])
    where (ys,zs) = splitlist xs (n - 1)

我知道我需要将签名更改为[a] -> ([a],[a])，但是在代码中我应该在哪里放置类似于length(xs)这样的内容，以便我不会破坏递归？

- kqualters

---

请参见https://dev59.com/eYXca4cB1Zd3GeqPIHDW。 - dfeuer

Answer 1

在实际程序中，您应该使用：

splitlist :: [a] -> ([a], [a])
splitlist xs = splitAt ((length xs + 1) `div` 2) xs

(例如类似dreamcrash的答案。) 但是如果出于学习目的，您正在寻找明确的递归解决方案，请研究以下内容：

splitlist :: [a] -> ([a], [a])
splitlist xs = f xs xs where
    f (y : ys) (_ : _ : zs) =
        let (as, bs) = f ys zs
        in (y : as, bs)
    f (y : ys) (_ : []) = (y : [], ys)
    f ys [] = ([], ys)

- dave4420

---

顺便说一下，我不知道是不是因为我在 codepad 上编译的缘故，但是需要将 length xs + 1 'div' 2 改成 length (xs + 1) 'div' 2。 - dreamcrash

不是的，因为我没有测试我的代码。感谢你发现了它。 - dave4420

如果列表很长，龟兔赛跑算法比基于splitAt的算法要好得多。它只需要一次遍历，而且可以懒惰地生成第一个组件。我不确定为什么你推荐另一种实现方式。 - dfeuer

@dreamcrash 把 (length xs + 1) `div` 2 改成这样 (你可以在列表上加1哦 :-). - undefined

Answer 2

你可以使用 take 和 drop 来完成：

splitlist :: [a] -> ([a],[a])
splitlist [] = ([],[])
splitlist l  = let half = (length(l) +1)`div` 2
               in (take half l, drop half l)

或者你可以利用splitAt函数：

（注：此处为IT技术相关内容，若需翻译其他内容请重新提问并给出相关文本）

splitlist list = splitAt ((length (list) + 1) `div` 2) list

- dreamcrash

Answer 3

您可以使用 take 和 drop 内置函数来实现此操作。但是，如果您想使用所有自编写的函数来完成此操作，请尝试以下方法：

dropList :: Int -> [Int] -> [Int]
dropList 0 [] = []
dropList 0 (x:xs) = x:xs
dropList y [] = []
dropList y (x:xs) = dropList (y-1) xs

takeList :: Int -> [Int] -> [Int]
takeList 0 [] = []
takeList 0 (x:xs) = []
takeList y [] = []
takeList y (x:xs) 
  | y <= length (x:xs) =  x : takeList (y-1) xs
  | otherwise = []

split :: Int -> [Int] -> ([Int],[Int])
split 0 [] = ([],[])
split y [] = ([],[])
split y (x:xs) = (takeList y (x:xs), dropList y (x:xs))

main = do
  print (split 4 [1,2,3,4,5,6])

- Rhys Broughton