3

对于给定的整数 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
4

3 回答 3

6

以下是列表连接的实现方式：

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

注意

  • 右手列表结构按原样重用（即使它还没有被评估，所以很懒惰）
  • 左侧列表结构被重写（复制）

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

的True情况下，keepOrNot累加器位于 的左侧++。您需要使用不同的数据结构。

在这种情况下，通常的习惯用法是使用差异列表。不要使用 type[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。当您想将其转换为常规列表时，请使用[](ie, 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)
于 2012-10-23T08:49:25.813 回答
3

因此，您希望将列表分组为n元素组，并删除所有其他组。我们可以直接写下来：

import Data.List (unfoldr)

groups n xs = takeWhile (not.null) $ unfoldr (Just . splitAt n) xs

foo c xs = concatMap head . groups 2 . groups c $ xs

dave4420 已经解释了您的代码有什么问题，但我想评论一下您是如何到达那里的，IMO。你的keepOrNot :: Bool -> Int -> [a] -> [a] -> [a]功能太笼统了。它根据收到Bool的任何内容 Bool工作；但你知道你会喂它一连串的交替值True和False值。使用函数编程就像将管道插入漏斗 - 一个函数的输出用作下一个函数的输入 - 而这里的漏斗太宽，所以接触松动。

沿着这些行对代码进行最小程度的重写可能是

foo n lst = go lst
  where
    go lst = let (a,b) = splitAt n lst
                 (c,d) = splitAt n b
             in
                 a ++ go d

联系“紧密”，这里没有“信息泄露”。我们自己只做两次 (*)工作，并在这段代码中明确地“连接管道”，获取一个结果 ( a) 并丢弃另一个结果 ( c)。

--
(*) 两次，反映两个布尔值，True并且False，以一种简单的方式一个接一个地交替。因此，这被冻结在代码结构中，而不是作为能够容纳任意布尔值的参数而松散。

于 2012-10-23T10:05:14.267 回答
1

就像 dava4420 说的，你不应该使用(++)从左边累积。但也许你根本不应该积累！在 Haskell 中，惰性使得直截了当的“头部构造”通常比在 Lisp 中需要使用的尾递归更有效。例如：

foo :: Int -> [a] -> [a]     -- why would you give this a Show constraint?
foo ℓ = foo' True
  where foo' _ [] = []
        foo' keep lst
          | keep       = firstℓ ++ foo' False other
          | otherwise  =           foo' True other
         where (firstℓ, other) = splitAt ℓ lst
于 2012-10-23T10:16:20.663 回答