Haskell:在索引k处将列表拆分为2

Question

我对Haskell很新,我遇到了一些麻烦.我正在尝试实现一个带有列表和int的函数.int应该是索引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!"

我实际上无法弄清楚如何进行拆分.任何帮助,将不胜感激.

Answer 1

首先,请注意,您尝试构建的函数已经在标准库中,在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.

Answer 2

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