list - 使用递归将列表分解为子列表

Question

我正在尝试使用类型声明 [(Int, Bool)] -> [[Int]] 编写一个函数。我希望函数仅在 bool 值为 True 时将 Int 添加到相同的嵌套子列表。但是，如果 bool 值是 False，我希望将与下一个 True bool 值关联的 Int 添加到 new 子列表。例如:输入

[(1,True),(2,True),(3,False),(4,True),(5,False),(6,False),(7,True)]

应该返回

[[1,2],[4],[7]]. 

到目前为止我的代码:

test:: [(Int, Bool)] -> [[Int]]
test xs = case xs of
    []->[]
    x:xs
        | snd x == True -> [(fst x)] : test xs
        | snd x == False -> test xs

如果它们的 bool 值都是 True，我目前在将并发 Int 添加到同一个列表时遇到问题。

Answer 1

您可以将此问题分解为两个子问题。

1. 对于任何给定的列表，取该列表的头部并将其与列表的其余部分进行匹配。在这个匹配过程中有两种可能:i)你成功了，即你匹配到了，如果是，你收集匹配到的值并继续寻找更多的值，或者 ii)你失败了，即你没有匹配到，如果是，您立即停止并返回到目前为止匹配的结果以及其余未检查的列表。

   collectF :: (Eq a) => (a -> Bool) -> [a] -> ([a], [a])
   collectF f [] = ([], [])
   collectF f (x : xs) 
    | f x = let (ys, zs) = collectF f xs in (x : ys, zs)
    | otherwise = ([], x : xs)

1. 现在您有了 collectF 函数，您可以在输入列表上递归使用它。在每次调用中，您将获得一个成功的列表，其中包含其余未检查的列表。再次对列表的其余部分应用 collectF，直到用完。

groupBy :: (Eq a) => (a -> a -> Bool) -> [a] -> [[a]]
groupBy _ [] = []
groupBy f (x : xs) = 
    let (ys, zs) = collectF (f x) xs in 
    (x : ys) : groupBy f zs

*Main> groupBy (\x y -> snd x == snd y) [(1,True),(2,True),(3,False),(4,True),(5,False),(6,False),(7,True)]
[[(1,True),(2,True)],[(3,False)],[(4,True)],[(5,False),(6,False)],[(7,True)]]

我将把它留给您从 List 中删除 True 和 False 值。另外，看看 Haskell [1] 的 List 库。希望，我很清楚，但如果您还有其他问题，请告诉我。

[1] http://hackage.haskell.org/package/base-4.12.0.0/docs/src/Data.OldList.html#groupBy