How do I make this function consume its input bit stream lazily?

Question

I'm imagining a function like

takeChunkUntil :: [a] -> ([a] -> Bool) -> ([a], [a])

Hopefully lazy.

It takes elements from the first list until the group of them satisfies the predicate, then returns that sublist as well as the remaining elements.

TO ANSWER SOME QUESTIONS:
The ultimate goal is to make something that reads Huffman codes lazily. So if you have a string of bits, here represented as Bool, bs, you can write take n $ decode huffmanTree bs to take the first n coded values while consuming only as much of bs as necessary. If you would like I'll post more details and my attempted solutions. This could get long :) (Note I'm a tutor who was given this problem by a student, but I didn't try to help him as it was beyond me, however I'm very curious now.)

CONTINUED: Here goes the whole thing:

Definition of Huffman tree:

data BTree a = Leaf a | Fork (BTree a) (BTree a) deriving (Show, Eq)

Goal: write a lazy decode function that returns a pair of the decoded values and a Boolean indicating if there were any values left over that were not fully long enough to be decoded into a value. Note: we are using Bool to represent a bit: True =1, False = 0.

decode :: BTree a -> [Bool] -> ([a], Bool)

Here's the essence: The first function I wrote was a function that decodes one value. Returns Nothing if the input list was empty, otherwise returns the decoded value and the remaining "bit".

decode1 :: BTree a -> [Bool] -> Maybe (a, [Bool])
decode1 (Leaf v) bs = Just (v, bs)
decode1 _ [] = Nothing
decode1 (Fork left right) (b:bs) 
  | b         = decode1 right bs
  | otherwise = decode1 left bs

First, I figured that I needed some kind of tail recursion to make this lazy. Here's what doesn't work. I think it doesn't, anyway. Notice how it's recursive, but I'm passing a list of "symbols decoded so far" and appending the new one. Inefficient and maybe (if my understanding is right) won't lead to tail recursion.

decodeHelp :: BTree a -> [a] -> [Bool] -> ([a],Bool)
decodeHelp t symSoFar bs = case decode1 t bs of
    Nothing -> (symSoFar,False)
    Just (s,remain) -> decodeHelp t (symSoFar ++ [s]) remain

So I thought, how can I write a better kind of recursion in which I decode a symbol and append it to the next call? The key is to return a list of [Maybe a], in which Just a is a successfully decoded symbol and Nothing means no symbol could be decoded (i.e. remaining booleans were not sufficient)

decodeHelp2 :: BTree a -> [Bool] -> [Maybe a]
decodeHelp2 t bs = case decode1 t bs of
    Nothing -> [Nothing]
    Just (s, remain) -> case remain of
        [] -> []
        -- in the following line I can just cons Just s onto the
        -- recursive call. My understand is that's what make tail
        -- recursion work and lazy.
        _  -> Just s : decodeHelp2 t remain 

But obviously this is not what the problem set wants out of the result. How can I turn all these [Maybe a] into a ([a], Bool)? My first thought was to apply scanl

Here's the scanning function. It accumulates Maybe a into ([a], Bool)

sFunc :: ([a], Bool) -> Maybe a -> ([a], Bool)
sFunc (xs, _) Nothing = (xs, False)
sFunc (xs, _) (Just x) = (xs ++ [x], True)

Then you can write

decodeSortOf :: BTree a -> [Bool] -> [([a], Bool)]
decodeSortOf t bs = scanl sFunc ([],True) (decodeHelp2 t bs)

I verified this works and is lazy:

take 3 $ decodeSortOf xyz_code [True,False,True,True,False,False,False,error "foo"] gives [("",True),("y",True),("yz",True)]

But this is not the desired result. Help, I'm stuck!

Answer 1

Here's a hint. I've swapped the argument order to get something more idiomatic, and I've changed the result type to reflect the fact that you may not find an acceptable chunk.

import Data.List (inits, tails)

takeChunkUntil :: ([a] -> Bool) -> [a] -> Maybe ([a], [a])
takeChunkUntil p as = _ $ zip (inits as) (tails as)