haskell - 缺乏对无限列表和 seq 运算符的理解

Question

对于给定的整数 n，下面的代码保留列表中的前 n 项，删除后面的 n 项，保留后面的 n 项，依此类推。它适用于任何有限列表。

为了使其可用于无限列表，我使用“seq”运算符在递归步骤之前强制累加器求值，如“foldl”中所示。

我通过跟踪累加器的值进行了测试，它似乎可以根据有限列表的需要进行有效计算。

尽管如此，当应用于无限列表时它不起作用。主函数中的“take”仅在内部计算终止后才会执行，当然，对于无限列表来说，这种情况永远不会发生。

请问有人可以告诉我我的错误在哪里吗？

main :: IO ()
main = print (take 2 (foo 2 [1..100]))

foo :: Show a => Int -> [a] -> [a]
foo l lst = inFoo keepOrNot 1 l lst []

inFoo :: Show a => (Bool -> Int -> [a] -> [a] -> [a]) -> Int -> Int -> [a] -> [a] -> [a]
inFoo keepOrNot i l  [] lstOut  = lstOut
inFoo keepOrNot i l lstIn lstOut = let lstOut2 = (keepOrNot (odd i) l lstIn lstOut) in
                      stOut2 `seq` (inFoo keepOrNot (i+1) l (drop l lstIn) lstOut2)

keepOrNot :: Bool -> Int -> [a] -> [a] -> [a]
keepOrNot b n lst1 lst2 = case b of
  True -> lst2 ++ (take n lst1)
  False -> lst2

Answer 1

以下是列表串联的实现方式:

(++) :: [a] -> [a] -> [a]
(++) []     ys = ys
(++) (x:xs) ys = x : xs ++ ys

请注意

• 右侧列表结构按原样重用(即使尚未评估，所以很懒)
• 左侧列表结构被重写(复制)

这意味着如果您使用 ++要构建列表，您希望累加器位于右侧。 (对于有限列表，仅仅是出于效率原因——如果累加器位于左侧，它将被重复复制，这是低效的。对于无限列表，调用者无法查看结果的第一个元素，直到它已经被最后一次复制，并且不会有最后一次，因为总是有其他东西要连接到累加器的右侧。)

True案例keepOrNot ++ 左侧有累加器。您需要使用不同的数据结构。

在这种情况下，通常的习惯用法是使用差异列表。而不是使用类型 [a]对于您的累加器，请使用 [a] -> [a] 。您的累加器现在是一个函数，它将一个列表添加到作为输入给出的列表中。这样可以避免重复复制，并且可以延迟构建列表。

keepOrNot :: Bool -> Int -> [a] -> ([a] -> [a]) -> ([a] -> [a])
keepOrNot b n lst1 acc = case b of
  True -> acc . (take n lst1 ++)
  False -> acc

累加器的初始值应该是id 。当你想将其转换为常规列表时，用 [] 调用它(即 acc [] )。

<小时/>

seq这是一个转移注意力的事情。 seq不强制整个列表。 seq仅确定其是否为 [] 形式或x : xs .

<小时/>

你正在学习 Haskell，是吗？因此，修改代码以使用差异列表累加器作为练习是一个好主意。可能无限列表的使用会让你在代码的不同部分中感到烦恼；我不知道。

但是有更好的方法来编写 foo .

foo c xs = map snd . filter fst . zipWith f [0..] $ xs
  where f i x = (even (i `div` c), x)