如何使此函数延迟使用其输入位流？

Question

我在想一个像

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

希望偷懒。

它从第一个列表中取出元素，直到它们中的一组满足谓词，然后返回该子列表以及其余元素。

解答一些问题：
最终目标是使某些东西可以懒惰地读取Huffman代码。因此，如果您有一串字符串（在此表示为Bool，）bs，则可以编写代码take n $ decode huffmanTree bs以获取前n个编码值，同时仅消耗bs必要的数量。如果您愿意，我会发布更多详细信息和尝试的解决方案。这可能会很长：)（请注意，我是一位学生给这个问题的辅导老师，但我没有试图帮助他，因为这超出了我，但是我现在很好奇。）

续：整个过程在这里：

霍夫曼树的定义：

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

目标：编写一个懒惰的解码函数，该函数返回一对解码后的值和一个布尔值，指示是否有剩余的值不够长而无法解码为一个值。注意：我们使用布尔来表示：True = 1，False = 0。

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

这就是本质：我编写的第一个函数是对一个值进行解码的函数。如果输入列表为空，则返回Nothing，否则返回解码值和剩余的“位”。

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

首先，我认为我需要某种尾部递归来使它变得懒惰。这里是不工作的。无论如何，我认为事实并非如此。请注意它是如何递归的，但是我要传递“到目前为止已解码的符号”列表并附加新的符号。低效，也许（如果我的理解是正确的）不会导致尾递归。

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

所以我想，如何编写一种更好的递归来解码符号并将其附加到下一个调用中？关键是返回[Maybe a]的列表，其中Just a是成功解码的符号，Nothing表示无法解码任何符号（即，剩余的布尔值不足）

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 

但这显然不是问题所要从结果中得到的。我如何将所有这些[Maybe a]变成一个([a], Bool)？我的第一个想法是申请scanl

这是扫描功能。累积Maybe a成([a], Bool)

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

那你可以写

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

我验证了这项工作，而且很懒：

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

但这不是期望的结果。救命，我被卡住了！

Answer 1

这是一个提示。我交换了参数顺序以获得更惯用的内容，并且更改了结果类型以反映您可能找不到可接受的块的事实。

import Data.List (inits, tails)

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