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

Question

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

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

应该return

[[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

如果布尔值都是 True.

，我目前在将并发 Int 添加到同一个列表时遇到问题

Answer 1

你可以把这个问题分解成两个子问题。

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

   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)

现在您有了 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] 的列表库。希望，我很清楚，但如果您还有其他问题，请告诉我。

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

Answer 2

我会这样写：

import Data.List.NonEmpty (NonEmpty(..), (<|))
import qualified Data.List.NonEmpty as NE

test :: [(Int, Bool)] -> [[Int]]
test = NE.filter (not . null) . foldr go ([]:|[])
  where
    go :: (Int, Bool) -> NonEmpty [Int] -> NonEmpty [Int]
    go (n, True) ~(h:|t) = (n:h):|t
    go (n, False) l = []<|l

或 :

import Data.List.NonEmpty (NonEmpty(..))

test :: [(Int, Bool)] -> [[Int]]
test = removeHeadIfEmpty . foldr prependOrStartNewList ([]:|[])
  where
    prependOrStartNewList :: (Int, Bool) -> NonEmpty [Int] -> NonEmpty [Int]
    prependOrStartNewList (n, True) ~(h:|t) = (n:h):|t
    prependOrStartNewList (n, False) l = []:|removeHeadIfEmpty l
    removeHeadIfEmpty :: NonEmpty [Int] -> [[Int]]
    removeHeadIfEmpty (h:|t) = if null h then t else h:t

Answer 3

重复，放下Falses，抓住Trues。使用视图模式：

{-# LANGUAGE ViewPatterns #-}

test :: [(a, Bool)] -> [[a]]
test (span snd . dropWhile (not . snd) -> (a,b))
               | null a     =  [] 
               | otherwise  =  map fst a : test b

也尽可能使用无限列表。

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

Breaking up a list into sublists with recursion

list

haskell

recursion

sublist