元素在列表的前半部分，Haskell

Question

阅读《Get Programming with [=19=》一书，其中一个问题是查找给定元素是否在列表的前半部分。这可以作为

isInFirstHalf x xs = elem x firstHalf
    where firstHalf = take (length xs `div` 2) xs

但是，问题是这里length遍历了整个列表。在命令式语言中，可以通过跟踪元素索引和当前计数器来提前缩短循环。例如。如果列表有一百万个元素，并且在第三个元素上有一个匹配项，一旦你完成对第六个元素的循环，你可以立即 return true.

我的问题是是否有办法在 Haskell 中实现类似的功能。

Answer 1

当然可以。

halfAsLong (x:_:xs) = x:halfAsLong xs
halfAsLong _ = []

isInFirstHalf x xs = elem x (zipWith const xs (halfAsLong xs))

试试看：

> isInFirstHalf 3 (1:2:3:4:5:6:undefined)
True

reader 的练习：

你提出的命令式方案的元素索引和当前计数器去哪了？（它们仍然在那里，只是以一种我认为有点微妙的方式隐藏了！）
当将奇数长度分成两半时，这会向下舍入，就像 length xs `div` 2 那样。代码必须如何更改才能向上舍入，就像 (length xs + 1) `div` 2 那样？

Answer 2

Daniel Wagner 发布了一个非常好的答案，表明您毕竟不需要索引。

不过，如果您确实想使用索引，可以按如下方式制定解决方案。

我们通过将它们与它们的索引配对来枚举所有列表元素。这是通过使用 zip [0..] xs 完成的（如果您想从 1 开始计数，则使用 zip [1..] xs）。
我们查找您的 x 是否在列表中，如果存在则查找其索引 i。可以通过直接递归进行，或者使用类似 dropWhile ((/= x) . fst) ... 的东西，然后测试结果。
一旦我们知道 i，我们需要检查之后是否至少有 i 个元素。这可以通过直接递归来解决，或者通过 dropping i-1 元素并测试结果是否为非空列表来解决。

当然还有其他选择。例如，我们可以跳过 zip [0..] 的枚举元素，并通过跟踪当前索引来使用递归：foo n x (y:ys) = ... foo (n+1) x ys ....

Answer 3

这是思考任务的另一种方式。元素 x 出现在列表 xs 的前半部分，不包括中点，如果该元素第一次出现之前的元素严格少于其之后的元素。

我们可以写 break (== x) xs 使用标准函数 break :: (a -> Bool) -> [a] -> ([a], [a]) 将 xs 分成两部分：出现在 x 之前的部分（或所有 xs , 如果 x 没有找到), 和余数 (包括 x, 如果找到).

> break (== 0) []
([], [])

> break (== 0) [0, 1]
([], [0, 1])

> break (== 0) [1, 0]
([1], [0])

> break (== 0) [1, 2, 0, 3, 4]
([1, 2], [0, 3, 4])

> break (== 0) [1, 2, 3, 4]
([1, 2, 3, 4], [])

然后我们想比较这两部分的长度，而不像Int那样严格计算实际长度。为此，我们可以使用 shape = map (const ())、a.k.a 忽略其所有元素来计算每个部分的 shape。 void :: (Functor f) => f a -> f () 专用于列表。

shape :: [a] -> [()]
shape = void

列表的 Ord 实例按字典顺序对它们进行排序，并且类型 () 的所有值都相等——好吧，只有类型的值 ()——所以比较形状 [()] 是比较列表的长度，这对于我们的目的来说也足够懒惰了。（对于最大惰性，shape 可以定义为惰性自然数类型 data N = Z | S N 上的 genericLength 和适当的 Ord 实例。）

> [] < repeat ()
True

> shape [5 .. 10] >= shape [1 .. 3]
True

> shape [1 .. 3] > shape [1 ..]
False

我们还可以使用 drop 1“减少”列表的形状，如果找到元素，我们将使用它来跳过对元素本身的计数。（或者，我们可以用 (() :) 来“增加”形状。）

最后，将这些元素放在一起会得出一个相当简单的解决方案：

isInFirstHalf :: (Eq a) => a -> [a] -> Bool
isInFirstHalf x xs = shape before < shape (drop 1 after)
  where
    (before, after) = break (== x) xs

请注意，如果未找到该元素，after 将为空，因此 drop 1 将无效，但 before 的形状不可能小于空形状 []，所以比较 (<) 仍然正确 return False.

元素在列表的前半部分，Haskell

Element is in first half of the list, Haskell

haskell