CODEWITHSUNDEEP
haskell
user4933255
user4933255

Reputation:

Checking for consecutive True in list Haskell using fold

I'm new to Haskell.

For a Project Euler problem, I've generated a list of bools.

[True, False, False, True, False. . .True]

What I'd like is to write a function find the first four consecutive True's, then return their indices in the list.

Intuitively, I know I should be doing this with a fold and somehow pattern matching. Could you help me? Something like this with a fold? (I have no idea how to retrieve the index of an element.)

consecutiveFourTrues (w:x:y:z):xs = if (w && x && y && z) then w else consecutiveFourTrues (x:y:z):xs

Thank you for your help!

Upvotes: 2

Views: 1095

Answers (5)

obadz
obadz

Reputation: 909

Maybe we should simply count the consecutive Trues rather than make sublists of them?

consec :: Int -> [Bool] -> [Int]
consec m = map (subtract m) . findIndices (>= m) . scanl (\ c x -> if x then c + 1 else 0) 0

ghci> consec 4 [False, True, True, True, True, True, False, True, True, True, True]
[1,2,7]

Upvotes: 0

dfeuer
dfeuer

Reputation: 48591

The simplest way to do this is to zip and then use a specialty fold. First look at each set of four consecutive elements and see if they're all true:

import Data.List (zipWith4, findIndex)

consec4 :: [Bool] -> [Bool]
consec4 xs = zipWith4 (\x y z w -> x && y && z && w) xs (drop 1 xs) (drop 2 xs) (drop 3 xs)

Now you just need

fstConsec4 :: [Bool] -> Maybe Int
fstConsec4 = findIndex id . consec4

Now this is not likely to be the very fastest you can do, and it doesn't generalize well to larger windows.

We can instead jump more directly into folds, taking a different approach. Note that this particular version is likely to behave better in GHC 7.10 or later than in earlier versions. I used bang patterns for clarity, but you could use seq or $! for portability if you like.

Let's start by defining a function conspicuously missing from Data.List:

{-# INLINE foldrWithIndex #-}
foldrWithIndex :: (Int -> a -> b -> b) -> b -> [a] -> b
foldrWithIndex c n xs = foldr go (`seq` n) xs 0
  where
    go x r !i = c i x (r $ i + 1)

Using this function, we can easily define a function that finds the index of the beginning of the first group of n consecutive True values.

consec :: Int -> [Bool] -> Maybe Int
consec n xs = foldrWithIndex go (`seq` Nothing) xs n
  where
    go _ix False r !_ = r n
    go ix True _r 1 = Just (ix - n + 1)
    go _ix True r need = r (need - 1)

A quick look at the GHC core this produces suggests it will likely be quite efficient (this was produced using ghc -O2 -ddump-simpl -dsuppress-all -dno-suppress-type-signatures):

$wconsec :: Int# -> [Bool] -> Maybe Int
$wconsec =
  \ (ww_s1BQ :: Int#) (w_s1BN :: [Bool]) ->
    letrec {
      $wgo_s1BL :: [Bool] -> Int# -> Int# -> Maybe Int
      $wgo_s1BL =
        \ (w1_s1BA :: [Bool]) (ww1_s1BF :: Int#) (ww2_s1BJ :: Int#) ->
          case w1_s1BA of _ {
            [] -> Nothing;
            : y_a1y5 ys_a1y6 ->
              case y_a1y5 of _ {
                False -> $wgo_s1BL ys_a1y6 (+# ww1_s1BF 1) ww_s1BQ;
                True ->
                  case ww2_s1BJ of ds_X16V {
                    __DEFAULT -> $wgo_s1BL ys_a1y6 (+# ww1_s1BF 1) (-# ds_X16V 1);
                    1 -> Just (I# (+# (-# ww1_s1BF ww_s1BQ) 1))
                  }
              }
          }; } in
    $wgo_s1BL w_s1BN 0 ww_s1BQ

consec :: Int -> [Bool] -> Maybe Int
consec =
  \ (w_s1BM :: Int) (w1_s1BN :: [Bool]) ->
    case w_s1BM of _ { I# ww1_s1BQ -> $wconsec ww1_s1BQ w1_s1BN }

Extreme performance hacking

In theory, it should be possible to do better, especially when looking in long lists. In particular, branching on the Bool values may lead to many mis-predicted branches if True and False values are both frequent. In this case, it's probably better to shove the values into a small bit vector, then play some bitty tricks on it. Unfortunately, it can be tough to convince GHC to do this sort of thing, but I may try later.

Upvotes: 3

Ed'ka
Ed'ka

Reputation: 7138

Is using fold a requirement? Because otherwise it can be straightforwardly expressed with standard functions from Data.List:

consec :: Int -> [Bool] -> [Int]
consec n = findIndices (isPrefixOf (replicate n True)) . tails

Just read it as English: findIndices of all tails of the list for which replicate-ed n times True isPrefixOf.

Upvotes: 2

effectfully
effectfully

Reputation: 12715

Here is another solution:

consec :: Int -> [Bool] -> [Int]
consec n = findIndices and . foldr (zipWith (:)) (repeat []) . take n . tails

It's based on ideas from other answers. take n . tails returns a matrix, which has lists of consecutive elements of length <= n as columns. foldr (zipWith (:)) (repeat []) transposes the matrix and throws away lists of length < n. findIndices finds indices.

Upvotes: 1

Brian
Brian

Reputation: 20285

tldr

findIndices (\x -> (x == True)) $ map (\x -> all (== True) x) $ sliding 2 bs

Define a sliding function similar to the one found in Scala.

sliding :: Int -> [a] -> [[a]]
sliding size [] = []
sliding size ls@(x:xs) = if length ls >= size then (take size ls) : sliding size xs else sliding size xs

Using sliding 2 with [True, False, False, True, True, False, True, False, True, True] gives

[[True,False],[False,False],[False,True],[True,True],[True,False],[False,True],[True,False],[False,True],[True,True]]

Then we can map to see if each sub list is contains all True values and get the indices of those that do with findIndices.

findIndices (\x -> (x == True)) $ map (\x -> all (== True) x) $ sliding 2 bs

[3,8]

Upvotes: 4

Related Questions