19

我一直觉得在 Haskell 中拥有一个需要使用列表（或数组，同样适用）的值和索引的函数或表达式很尴尬。

我在这里validQueens尝试 N 皇后问题时在下面写...

validQueens x = 
     and [abs (x!!i - x!!j) /= j-i | i<-[0..length x - 2], j<-[i+1..length x - 1]]

我不关心索引的使用，所有的优点和缺点等等。感觉很草率。我想出了以下内容：

enumerate x = zip [0..length x - 1] x

validQueens' :: [Int] -> Bool
validQueens' x = and [abs (snd j - snd i) /= fst j - fst i | i<-l, j<-l, fst j > fst i]
                   where l = enumerate x

受到 Python 的启发enumerate（并不是说借用命令式概念一定是个好主意）。在概念上似乎更好，但snd整个fst地方有点糟糕。至少乍一看，它在时间和空间上的成本都更高。我不确定我是否更喜欢它。

所以简而言之，我对任何一个都不满意

  1. 通过以长度为界的索引进行迭代，或者更糟糕的是，逐个和两个
  2. 索引元素元组

有没有人发现比上述任何一种都更优雅的模式？如果不是，是否有任何令人信服的理由上述方法之一优越？

4

2 回答 2

38

借贷enumerate是好的和鼓励的。但是，可以通过拒绝计算其参数的长度来使其更懒惰：

enumerate = zip [0..]

（事实上​​，zip [0..]不命名就直接使用是很常见的enumerate。）我不清楚为什么你认为你的第二个例子在时间或空间上应该更昂贵。请记住：索引是 O(n)，其中 n 是索引。fst您对和的笨拙的抱怨snd是有道理的，并且可以通过模式匹配来解决：

validQueens' xs = and [abs (y - x) /= j - i | (i, x) <- l, (j, y) <- l, i < j]
    where l = zip [0..] xs

现在，您可能有点担心这个双循环的效率，因为该子句(j, y) <- l将沿着 的整个脊椎运行l，而实际上我们只是希望它从我们离开的地方开始(i, x) <- l。因此，让我们编写一个实现该想法的函数：

pairs :: [a] -> [(a, a)]
pairs xs = [(x, y) | x:ys <- tails xs, y <- ys]

有了这个功能，你的功能就不太难适应了。将谓词提取到它自己的函数中，我们可以使用all代替and：

validSingleQueen ((i, x), (j, y)) = abs (y - x) /= j - i
validQueens' xs = all validSingleQueen (pairs (zip [0..] xs))

或者，如果您更喜欢无点表示法：

validQueens' = all validSingleQueen . pairs . zip [0..]
于 2011-06-24T20:00:01.030 回答
18

索引元素元组在 Haskell 中是很常见的事情。因为zip当第一个列表停止时停止，您可以将它们写为

enumerate x = zip [0..] x

这既更优雅也更高效（因为它不会预先计算length x）。事实上，我什至都懒得命名它，因为zip [0..]它太短了。

这绝对比通过索引迭代列表更有效，因为!!由于列表是链表，所以在第二个参数中是线性的。

使程序更优雅的另一种方法是使用模式匹配而不是fstand snd：

validQueens' :: [Int] -> Bool
validQueens' x = and [abs (j2 - i2) /= j1 - i1 | (i1, i2) <-l, (j1, j2) <-l, j1 > i1]
                   where l = zip [0..] x
于 2011-06-24T19:47:18.907 回答