ハスケルの最大クリークファインダ -

Question

最大クリークの数を見つけるためにブロン - ケルボスアルゴリズムを実装しようとしています（最大クリークは、2つの頂点が接続されているグラフのサブセットであり、それ）

https://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm

残念ながら、私はエラーを取得： 「入力 『RES』でエラーを解析し、」そして、私はそれを解決するために見えることはできません。私は通常のものでタップスペースを変更しようとしましたが、動作しないようです。私も間違いないと思う？何か案は？

type Clique = [Vertex] 
swarming::Clique->[Vertex]->[Vertex]->[Clique] 
swarming R P X = 
    if null P && null X then [R] 
         else loop R X 
        where 
         loop::[Vertex]->[Vertex]->[Clique] 
         loop[] _ =[] 
         loop(v:R') X= 
          swarming (v:R)(P 'res' v)(X 'res' v) 
          loop P (v:X) 

type Vertex = Int 
class Graph g where 
    size   ::g->Int 
    verticies  ::g->[Vertex] 
    connected  ::g->Vertex->Vertex->Bool 

bron::Graph g=>g->[Clique] 
bron g = swarming[] (verticies g) [] 
    where 
     swarming R P X = 
       if null P && null X then [R] 
         else loop R X 
        where 
         loop::[Vertex]->[Vertex]->[Clique] 
         loop[] _ =[] 
         loop(v:R) X= 
          swarming (v:R)(P 'res' v)(X 'res' v) 
          loop P (v:X) 
         res::[Vertex]->Vertex->[Vertex] 
         res vs v = filter(connected g v) vs 

Answer 1

私はもう少し間違ってあなたのコードを持つだけ誤差よりもそこにある見ることができるようにあなたが得る：コメントがすでに'が単一の文字Charのために予約されていると言うように、すべての

• まず、あなたが探している構文は`res`です。

• 第二に、私はあなたがタブを使用している見て、GHCコンパイラの新しいバージョンは、通常、今日の人々はスペースを使用し、それについて警告を表示します（これは主に好みの問題であり、それはあなた次第です）

私はあなたのコードを少し並べ替え、コンパイルしたように修正しました。 undefinedはランタイムエラーを発生させますが、この状態は非コンパイルエラーよりも優れています。

type Clique = [Vertex] 
type Vertex = Int 

class Graph g where 
    size  :: g -> Int 
    vertices :: g -> [Vertex] 
    connected :: g -> Vertex -> Vertex -> Bool 

私は通常type/data/class宣言は私のファイルの先頭とその下の残りの部分の上にあるような方法で自分のコードを整理します。

構文次のエラーでは、変数名に大文字を使用しています。これは、haskellでは許可されていません。型は小文字の大文字変数で始まります。

bronは、微妙な機能であり、正直なところ、あなたがしたいことを理解できない場合は、これを理解するのが難しい2つのことがあります。

1. あなたが持っているには、「変数の両方群がって、ループ内rとr - pは常に同じである必要があり、一方、彼らは、同じであるべきではないと思われます。 名前シャドーイングは構文上の問題ではなく、論理的なもので、2つの異なるものが同じ名前でない場合にはより簡単になります。

2. 私は、これは無効なHaskellの構文である

   loop ... = swarming 
         loop 
   

   を参照してください - これら2つの行をステッチするlet … inを使用し、あなたがそれは、コードの以下の部分で使用されていない群がってやろうとしている一緒に

ここ

はコンパイルが、不完全な実装

bron :: Graph g => g -> [Clique] 
bron g = swarming [] (vertices g) [] 
    where res :: [Vertex] -> Vertex -> [Vertex] 
     res vs v = filter (connected g v) vs 

     swarming :: Clique -> [Vertex] -> [Vertex] -> [Clique] 
     swarming r [] [] = [r] 
     swarming r p x = loop r x 
      where loop :: [Vertex] -> [Vertex] -> [Clique] 
       loop [] _ = [] 
       loop (v:r) x = undefined 
          -- let sw = swarming (v:x) (p `res` v) (x `res` v) 
          -- in loop ?? 

でコード bronの残りの部分であります