如何在 Haskell 中的特定条件下拆分列表？

Question

作为一个编程练习，我正在尝试在 Haskell 中构建一个函数，其中给定一个列表，只要重复一个元素，它就会拆分列表。例如，[1,2,3,3,4,5] 会拆分为 [[1,2,3],[3,4,5]]。我的第一个想法是将列表拆分为具有单个元素的列表列表，其中 [1,2,3,3,4,5] 将变为 [[1],[2],[3],[3]， [4],[5]] 然后仅当被比较的元素不相等时才合并列表，但是实现这个对我来说很头疼，因为我对 Haskell 很陌生，递归总是给我带来麻烦.我认为我用来组合列表的函数有问题，它只会 return 一个列表，其中所有被分解的元素组合在一起，其中 [1,2,3,3,4 ,5] 变为 [[1],[2],[3],[3],[4],[5]] 但我的 split_help 函数会将其转换为 [[1,2,3,3 ,4,5]] 而不是 [[1,2,3],[3,4,5]]

我在下面粘贴了我不完整的代码，它现在不能工作，但它应该给出我正在尝试完成的事情的总体思路。也欢迎任何关于一般 Haskell 代码礼仪的反馈。

split_breaker 将列表分成列表列表，split_help 是我试图用来组合不相等元素的内容。

split_help x y
     | x /= y = x ++ y
     | otherwise = []

split_breaker :: Eq a => [a] -> [[a]]
split_breaker [] = []
split_breaker [x] = [[x]]
split_breaker (x:xs) = [x]:split_breaker xs

split_at_duplicate :: Eq a => [a] -> [[a]]
split_at_duplicate [x] = [[x]]
split_at_duplicate (x:xs) = foldl1 (split_help) (split_breaker [xs])

Answer 1

你想像这样工作吗？

splitAtDup [1,2,3,3,3,4,4,5,5,5,5,6]
[[1,2,3],[3],[3,4],[4,5],[5],[5],[5,6]]

我说得对吗？

那就简单点：

splitAtDup :: Eq a => [a] -> [[a]]
splitAtDup (x : y : xs) | x == y = [x] : splitAtDup (y : xs)
splitAtDup (x : xs) =
  case splitAtDup xs of
    x' : xs' -> (x : x') : xs'
    _ -> [[x]]
splitAtDup [] = []

Answer 2

这是一个最懒惰的方法：

splitWhen :: (a -> a -> Bool) -> [a] -> [[a]]
splitWhen f = foldr go [[]] where
  go x acc = (x:xs):xss where
    xs:xss = case acc of
      (z:_):_ | f x z -> []:acc
      _ -> acc

splitAtDup :: Eq a => [a] -> [[a]]
splitAtDup = splitWhen (==)

要验证懒惰，试试这个：

take 2 $ take 4 <$> splitAtDup (1:2:3:3:4:5:6:undefined)

它可以完全评估为范式[[1,2,3],[3,4,5,6]]。

如何在 Haskell 中的特定条件下拆分列表？

How do I split a list on certain conditions in Haskell?

algorithm

recursion

haskell

list