从列表中获取偶数位置的元素

Question

问题：使用fold，从列表中取出偶数位置的元素：

GHCi> evenOnly [1..10]
 [2,4,6,8,10]
GHCi> evenOnly ['a'..'z']
 "bdfhjlnprtvxz"

evenOnly :: [a] -> [a]
evenOnly = undefined

我一开始决定获取交替 0-es 和 1-s 的列表：[0,1,0,1..]

Prelude> let g = iterate (\x -> (x + 1) `mod` 2) 0
Prelude> take 10 $ g
[0,1,0,1,0,1,0,1,0,1]

然后zip它与原始列表，得到一对列表：[(x1, 0), (x2,1), (x3,0) .. (xn, ?)]:

Prelude> zip g [1,2,3,4,5]
[(0,1),(1,2),(0,3),(1,4),(0,5)]

之后，foldr具有过滤功能的pair列表和一个空列表作为初始化值。

所以我认为这可行：

evenOnly :: [a] -> [a]
evenOnly xs = let g = iterate (\x -> (x + 1) `mod` 2) 0
  in
  foldr (\ (x, n) s -> if n == 1 then x : s else s) [] . (zip g xs)

但是它给出了一个错误，我不明白：

foldr.hs:44:59: error:
    • Couldn't match expected type ‘a0 -> t0 (a1, Integer)’
                  with actual type ‘[(Integer, a)]’
    • Possible cause: ‘zip’ is applied to too many arguments
      In the second argument of ‘(.)’, namely ‘(zip g xs)’
      In the expression:
        foldr (\ (x, n) s -> if n == 1 then x : s else s) [] . (zip g xs)
      In the expression:
        let g = iterate (\ x -> (x + 1) `mod` 2) 0
        in
          foldr (\ (x, n) s -> if n == 1 then x : s else s) [] . (zip g xs)
    • Relevant bindings include
        xs :: [a] (bound at foldr.hs:42:10)
        evenOnly :: [a] -> [a] (bound at foldr.hs:42:1)

我认为我的想法是正确的，我只是在语法上做错了。

Answer 1

(.) 是函数组合，但 zip g xs 是列表而不是函数。您可以直接将结果列表作为 foldr 的参数应用。请注意，参数 g 和 xs 的顺序错误：

evenOnly :: [a] -> [a]
evenOnly xs = let g = iterate (\x -> (x + 1) `mod` 2) 0
  in
  foldr (\ (x, n) s -> if n == 1 then x : s else s) [] (zip xs g)

Answer 2

您可以 zip 以上内容加上一串数字，例如：

evenOnly :: [a] -> [a]
evenOnly = foldr (\(c, x) -> if c then (x:) else id) [] . zip (cycle [False, True])

这里cycle [False, True]因此生成一个无限列表[False, True, False, True, …]。在 foldr 中，我们检查源自 cycle [False, True] 的相应值 c。如果它是 True，那么我们在列表前加上 x，否则我们只是将递归调用的结果传递给 id。

或者我们可以省略这个，使用：

evenOnly :: [a] -> [a]
evenOnly = foldr (uncurry ($)) [] . zip (cycle [const id, (:)])

Answer 3

模式匹配是一种非常合理的方法：

evenOnly :: [a] -> [a]
evenOnly (_ : a : as) = a : evenOnly as
evenOnly _ = []

另一种选择是使用列表理解：

evenOnly as = [a | (a, True) <- zip as (cycle [False, True])]

如果与其他列表处理函数融合，列表理解版本可能会更高效。

Answer 4

不需要计算的东西不应该计算。选择是位置性的，它是事先已知的。计算模数，与布尔运算相比，都是多余的工作。

相反，执行this，然后执行that，然后继续这样切换； 使用 foldr，如所问：

evenly :: [t] -> [t]
evenly xs = foldr c z xs f g
   where
   c x r f g = f x (r g f)

接下来我们根据每个定义的使用方式完成定义：

   z _ _  = []
   f _ xs = xs
   g x xs = x : xs

从列表中获取偶数位置的元素

Take elements on even positions from the list

list

haskell

syntax

fold

type-mismatch