haskell - 如何让这个函数懒惰地消耗它的输入比特流？

Question

我在想象一个像
takeChunkUntil :: [a] -> ([a] -> Bool) -> ([a], [a])
希望懒惰。

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

回答一些问题:
最终目标是制作出 Huffman codes 的内容。懒洋洋。所以如果你有一串位，这里表示为 Bool，bs ，你可以写take n $ decode huffmanTree bs取前 n 个编码值，同时只消耗 bs有必要的。如果您愿意，我会发布更多详细信息和我尝试的解决方案。这可能会很长:)(请注意，我是一名学生，但我没有尝试帮助他，因为这超出了我的能力，但是我现在很好奇。)

续:这就是整个事情:

霍夫曼树的定义:

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

目标:编写一个惰性解码函数，返回一对解码值和一个 bool 值，指示是否有剩余的值不够长而无法解码为一个值。注意:我们使用 Bool 来表示一点: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意味着没有符号可以被解码(即剩余的 bool 值是不够的)

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

这里有一个提示。我已经交换了参数顺序以获得更惯用的东西，并且我已经更改了结果类型以反射(reflect)您可能找不到可接受的 block 的事实。

import Data.List (inits, tails)

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