リスト要素とインデックスを一緒に使用する

Question

Haskellでは、リスト（または配列）の値とインデックスを使用する必要がある関数または式を使用するのが難しいと私は常に気付いていました。

私は... Nクイーン問題 hereで実験しながら、下に

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

をvalidQueensを書いた私は、それはずさんな感じなど、インデックスを使用するためのすべてのプラスとマイナスを気にしませんでした。私は、次のを思い付いた：

Pythonの enumerate（不可欠な概念を借用することは必ずしも素晴らしいアイデアではないこと）に触発されて

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 

。コンセプトは良く見えますが、sndとfstはまあまあです。それはまた、一見したところでは、時間と空間の両方においてコストがかかります。私はそれがもっと好きかどうか分からない。だから、要するに

、私は既製のものによると補数

索引要素のタプル

、長さ、またはさらに悪いことに囲まれたインデックスでスルーのどちらか

1. 反復処理には本当に満足していません

   誰かが上記のいずれよりもエレガントなパターンを見つけましたか？そうでない場合は、上記の方法のいずれかが優れている理由がありますか？

Answer 1

借入enumerateは罰金および奨励です。しかし、それはその引数の長さを計算するために拒否することによって、ビットlazierを行うことができます。

enumerate = zip [0..] 

（実際には、それはそれenumerate名前を付けずにzip [0..]を使用するのが一般的です。）あなたが考える理由は私にははっきりしていません2番目の例は時間と空間のどちらかでコストがかかるはずです。注意：インデックスは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] 

は、この関数を作った、あなたの関数を適応するにはあまりにも難しいことではありません。

validQueens' = all validSingleQueen . pairs . zip [0..] 

：あなたはポイントなしの表記を好む場合は、

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

をまたは：独自の関数に述語を引き出すと、我々はandの代わりにallを使用することができます

Answer 2

インデックス要素のタプルは、ハスケルではよくあることです。最初のリストが停止したときにzipが停止するので（それがフロントアップlength xを計算しないように）、あなたはよりエレガントでより効率的でもある

enumerate x = zip [0..] x 

としてそれらを書くことができます。実際には、zip [0..]は非常に短いので、名前を付けても構いません。

!!は、リストがリンクリストであるため第2引数で線形であるため、リストのインデックスを反復するよりもはるかに効率的です。あなたはあなたのプログラムがよりエレガントにすることができます

もう一つの方法は、代わりに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