CODEWITHSUNDEEP
listhaskellrecursionsublist
nick doig
nick doig

Reputation: 23

Breaking up a list into sublists with recursion

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

should return

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

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

Upvotes: 2

Views: 533

Answers (3)

Joseph Sible-Reinstate Monica
Joseph Sible-Reinstate Monica

Reputation: 48647

Here's how I'd write this:

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

Or with Will Ness's suggestion:

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

Upvotes: 2

Will Ness
Will Ness

Reputation: 71109

Repeatedly, drop the Falses, grab the Trues. With view patterns:

{-# LANGUAGE ViewPatterns #-}

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

Works with infinite lists as well, inasmuch as possible.

Upvotes: 2

keep_learning
keep_learning

Reputation: 1077

You can break this problem into two sub-problems.

  1. For any given list, take the head of this list and match it against the rest of list. There are two possibilities during this matching: i) You are successful i.e. you match, and if so, you collect the matched value and continue looking for more values, or ii) You fail, i.e. you don't match, and if so, you stop immediately and return the so far matched result with rest of, not-inspected, list. 
   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. Now that you have the collectF function, you can use it recursively on input list. In each call, you would get a successful list with rest of, not-inspected, list. Apply collectF again on rest of list until it is exhausted. 
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)]]

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

Upvotes: 2

Related Questions