Haskell：如何将列表在索引k处分成两个部分

Question

我对Haskell还比较陌生，遇到了一些问题。我正在尝试实现一个函数，它接受一个列表和一个整数。这个整数应该是列表被分成一对列表的索引k。第一个列表包含列表的前k个元素，第二个列表包含从k+1到最后一个元素的元素。以下是我目前的代码：

split :: [a] -> Int -> ([a], [a])
split [] k = error "Empty list!"
split (x:[]) k = ([x],[])
split xs k | k >= (length xs) = error "Number out of range!"
           | k < 0 = error "Number out of range!"

我实际上无法弄清如何进行分割。希望能得到帮助。

- papercup

---

也许这会有帮助？- 在Haskell中获取子数组 - arunkumar

不要使用数组来进行列表处理！ - AndrewC

Answer 1

首先，请注意您正在尝试构建的函数已经在标准库中，它被称为 splitAt，位于 Prelude 中。现在，直接查看其定义可能会让人感到困惑，因为有两种算法，一种根本不使用标准的递归结构——splitAt n xs = (take n xs, drop n xs)——而另一种则是手动优化，使其看起来很丑陋。前者更直观，因为您只需将一个前缀和一个后缀放入一对中即可。然而，后者可以教授更多内容，其整体结构如下：

splitAt :: Int -> [a] -> ([a], [a])
splitAt 0 xs     = ([], xs)
splitAt _ []     = ([], [])
splitAt n (x:xs) = (x:xs', xs'')
  where
    (xs', xs'') = splitAt (n - 1) xs

基本思路是，如果一个列表由头和尾部组成（形如 x:xs），那么从索引 k+1 开始的列表将会与从 k 开始的列表相同，只需移除第一个元素即可 - drop (k + 1) (x : xs) == drop k xs。为了构建前缀，你可以类似地移除第一个元素，取一个较小的前缀，然后把元素放回去 - take (k + 1) (x : xs) == x : take k xs。

- gereeter

Answer 2

这个如何:

这个如何：

splitAt' = \n -> \xs -> (take n xs, drop n xs)

一些测试：

> splitAt' 3 [1..10]
> ([1,2,3],[4,5,6,7,8,9,10])

> splitAt' 0 [1..10]
> ([],[1,2,3,4,5,6,7,8,9,10])

> splitAt' 3 []
> ([],[])

> splitAt' 11 [1..10]
> ([1,2,3,4,5,6,7,8,9,10],[])

> splitAt' 2 "haskell"
> ("ha","skell")

- jimmyt

---

刚想到可以使用相同的见解。我更喜欢这种方法。或者只需使用内部函数splitAt：http://hackage.haskell.org/package/base-4.6.0.1/docs/Prelude.html#v:splitAt - hbobenicio

Answer 3

在构建列表时，消除二次行为的常见技巧是倒序构建，然后反转它，修改马克·里德的解决方案。这与IT相关。

split xs k | k < 0 = error "Number out of range!"
split xs k = (reverse a, b)
  where
    (a,b) = ssplit [] xs k

ssplit p xs 0 = (p, xs)
ssplit p (x:xs) k = ssplit (x:p) xs (k-1)
ssplit p [] k = error "Number out of range!"

ssplit 中的错误检查很好，因为除非出现实际错误，否则不会被检查（之前的某个模式将匹配）。

在实践中，您可能希望向 ssplit 添加一些严格性注释以管理堆栈增长，但这是进一步的改进。

- none

Answer 4

基本上，您需要通过某种方式在递归列表时传递部分进度。我使用了一个带有累加器参数的第二个函数；它从split调用，然后递归地调用自身。几乎肯定有更好的方法...

编辑：删除了所有长度检查，但我认为使用++仍然是O(n^2)。

split xs k | k < 0 = error "Number out of range!"
split xs k = ssplit [] xs k

ssplit p xs 0 = (p, xs)
ssplit p (x:xs) k = ssplit (p++[x]) xs (k-1)
ssplit p [] k = error "Number out of range!"

要获取原始帖子中的行为或

ssplit p [] k = (p,[])

为了获得标准的splitAt函数更宽容的行为。

- Mark Reed

---

我认为在每次递归调用中检查长度并不好。这实际上使算法的时间复杂度为O(n^2)。 - Vladimir Matveev

Answer 5

请参阅Prelude中的splitAt函数：

ghci> :t flip splitAt
flip splitAt :: [a] -> Int -> ([a], [a])
ghci> flip splitAt  ['a'..'j'] 5
("abcde","fghij")

- jkoshy