缺乏理解无限列表和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)