ハスケルフィルタ（3タプル）リスト自体がリスト

Question

私はまだハスケルに新しいといくつかのことをしようとしています。私はピタゴラスのトリプルがいっぱいのリストを持っています。今私はすべての同一のトリプルを削除したい。たとえば（6,8,10）は（3,4,5）と同じ方法です。だから私は、2つの3タプルが同じかどうかをチェックする関数を書いた。同じであればTrueを返し、そうでなければFalseを返す。しかし今、私は3つのタプルのリストを持っています（そのうち3つのタプルは同じです）、すべて同じ3つのタプルを除外したいと思います。私はStackOverflowで同じ問題を探していましたが、悲しいことに私が使うことができるものは見つかりませんでした。

私の現在のコードは以下の通りです。 （。私は、現時点では非常に非効率的なことをやっていると確信しているので、効率を気にしないでください）

トリプルのリストを生成：

pyth :: Int -> [(Int, Int, Int)] 
pyth i = [(a, b, c) | a <- [1..i], b <- [1..a], c <- [1..i], (a^2) + (b^2) == (c^2)] 

一部の機能3タプルでの作業を支援するために：

first :: (Int, Int, Int) -> Int 
first (a,_,_) = a 

second :: (Int, Int, Int) -> Int 
second (_,a,_) = a 

third :: (Int, Int, Int) -> Int 
third (_,_,a) = a 

2つのトリプルが同一であるかどうチェック機能：

doubleCheck :: (Int, Int, Int) -> (Int, Int, Int) -> Bool 
    doubleCheck a b 
    | (((first b) `div` (first a)) == ((second b) `div` (second a))) && 
     ((first b) `mod` (first a) == 0) && 
     ((second b) `mod` (second a) == 0) = True 
    | otherwise = False 

今ウィットh私がHaskellについて聞いて読んだことと、高次関数の力は、2行のコードや何かのようなものになると思います。しかし、私は一日のようにこれに固執しており、この問題の解決方法を理解することはできません。

ありがとうございます！

Answer 1

私はいくつかの簡略化を提案できます。

まず、ブール値は通常の値です。彼らはifガード、または| ...ガードに降格する必要はありません。特に、

f x | condition = True 
    | otherwise = False 

があなたの特定のケースで

f x = condition 

に簡素化することができます。

doubleCheck :: (Int, Int, Int) -> (Int, Int, Int) -> Bool 
doubleCheck a b = 
    (((first b) `div` (first a)) == ((second b) `div` (second a))) 
    && ((first b) `mod` (first a) == 0) 
    && ((second b) `mod` (second a) == 0) 

第二に、のは、いくつかの冗長な括弧を削除してみましょう、そこにあまりにも多くのノイズがあります。

doubleCheck :: (Int, Int, Int) -> (Int, Int, Int) -> Bool 
doubleCheck a b = 
    (first b `div` first a) == (second b `div` second a) 
    && (first b `mod` first) == 0 
    && (second b `mod` second a) == 0 

実際には、最後の3行ですべての括弧を削除できますが、そのうちのいくつかは残しておきます。

第3に、ヘルパ関数はまったく助けません。そのようなアクセサについては忘れて、必要なときにパターンマッチングを利用してください。ところで

doubleCheck :: (Int, Int, Int) -> (Int, Int, Int) -> Bool 
doubleCheck (a1,a2,a3) (b1,b2,b3) = 
    (b1 `div` a1) == (b2 `div` a2) 
    && (b1 `mod` a1) == 0 
    && (b2 `mod` a2) == 0 

あなたがすべてでa3,b3を処理しなかったので、上記は今、間違って見えます。それを修正すべきだと私は思いますか？とにかく

、リストをフィルタリングし、各トリプルの最初のコピーを保持するために、我々はData.List.nubBy

nubBy doubleCheck myListOfTriples 

を使用することができます。これは、その素晴らしいではありませんO（N^2）複雑性を、持っていますが、それが必要行う。現時点では、私はこの特定の問題に対してより複雑な解決策を見つけることはできません。

おそらく、トリプルのgcdによって各コンポーネントをダイビングすることで、各トリプルを減らすことができます。この正規化プロセスの後、我々の等価性は明白な同一性である。したがって、O（n log n）をソートして、O（n）の重複を取り除くことができます。