8

I'm pretty new to Haskell, and I'm having a little trouble. I'm trying to implement a function that takes a list, and an int. the int is supposed to be the index k at which the list is split into a pair of lists. The first one containing the first k elements of the list, and the second from k+1 to the last element. Here's what I have so far:

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!"

I can't actually figure out how to do the split. Any help would be appreciated.

4

5 回答 5

19

首先，请注意您尝试构建的函数已经在标准库中，在Prelude- 它被称为splitAt. 现在，直接看它的定义是令人困惑的，因为有两种算法，一种根本不使用标准递归结构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。

于 2012-09-22T02:26:43.697 回答
3

那这个呢：

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")
于 2012-09-24T23:30:06.467 回答
1

在构建列表时摆脱二次行为的一个常见技巧是向后构建它，然后反转它，修改 Mark Reed 的解决方案：

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 添加一些严格性注释以管理堆栈增长，但这是进一步的改进。

于 2012-09-24T10:51:11.323 回答
1

基本上，您需要某种方式在递归列表时传递部分进度。我使用了第二个接受累加器参数的函数；它从 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函数的更宽容的行为。

于 2012-09-22T02:21:12.233 回答
0

见splitAt前奏：

ghci> :t flip splitAt
flip splitAt :: [a] -> Int -> ([a], [a])
ghci> flip splitAt  ['a'..'j'] 5
("abcde","fghij")
于 2012-09-22T02:29:59.737 回答