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

Breaking up a list into sublists with recursion

我正在尝试使用类型声明 [(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 添加到同一个列表时遇到问题

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

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

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

我会这样写:

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

重复,放下Falses,抓住Trues。使用视图模式:

{-# LANGUAGE ViewPatterns #-}

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

也尽可能使用无限列表。