一起使用列表元素和索引

Question

我总是觉得有一个函数或表达式需要在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. 索引元素元组

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

Answer 1

借款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..]

Answer 2

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

enumerate x = zip [0..] x

这更优雅,更高效(因为它不预先计算length x).事实上,我甚至不打算命名它,因为zip [0..]它太短了.

这肯定比按列表索引迭代更有效,因为!!由于列表是链接列表,因此在第二个参数中是线性的.

另一种使程序更优雅的方法是使用模式匹配而不是fst和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