通过递归将列表分成子列表 [英] Breaking up a list into sublists with recursion

问题描述

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

I'm trying to write a function with the type declaration [(Int, Bool)] -> [[Int]]. I want the function to only add Ints to the same nested sublist if the Boolean is True. However if the Boolean is False, I want the Int associated with the next True bool to be added to a new sublist. For example: An input of

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

应该返回

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

到目前为止，我的代码:

My code so far:

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

如果它们的布尔值均为True，则我目前在将并发Ints添加到同一列表时遇到问题.

I'm currently having issues on adding concurrent Ints to the same list if their bools are both True.

推荐答案

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

You can break this problem into two sub-problems.

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)]]

我留给您从列表中删除True和False值.另外，请查看Haskell [1]的列表库.希望我已经足够清楚了，但是如果您还有其他问题，请告诉我.

I am leaving it to you to remove the True and False values from List. Also, have a look at List library of Haskell [1]. Hope, I am clear enough, but let me know if you have any other question.

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

这篇关于通过递归将列表分成子列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！