0

color2 つの関数 (とcheck) を最も一般的な形 にまとめたいと思いEq a => ...ます。しかし、私はそれを行う方法がわかりません。

これは非常に単純なグラフです。各ノードには 2 つの隣接ノードがあり、隣接するノードには異なる色が必要です。

color ::  [(Int, Int)] -> [(Int, Int)] -> Bool
color x [] = True
color a ((x,y):rest) =
    if check a x == check a y
    then False
    else color a rest

check :: [(Int, Int)] -> Int -> Int
check [] x = 999
check ((x,y):rest) p =
    if x == p
    then y
    else check rest p

最後にcolors、TrueまたはFalse

Main> colors [('a',"purple"),('b',"green"),('c',"blue")] [('a','b'),('b','c'),('c','a')]
True

Main> colors [('a',"purple"),('b',"green"),('c',"purple")] [('a','b'),('b','c'),('c','a')]
False

Main> colors [('1',"purple"),('2',"green"),('3',"blue")] [('1','2'),('2','3'),('3','1')]
True

Main> colors [('1',"4"),('2',"5"),('3',"6")] [('1','2'),('2','3'),('3','1')]
True

Main> colors [('1',"4"),('2',"4"),('3',"5")] [('1','2'),('2','3'),('3','1')]
False

どんな助けでも大歓迎です (+ x = 999 を False に修正できる場合)。

4

1 に答える 1

8

Intまず、を に一般化できない理由Eq aは、 に 999 がハードコードされているためですcheck。そこにランダムな値をそのままにしておくと、その型を知っている必要があるため、それを超えて関数を一般化することはできません (この特定のケースでは、一般化できますがEq a, Num a、それ以上はできません)。

したがって、答えは任意の値を使用するのではなく、代わりに の戻り値をcheck「失敗」ケースを持つ型、つまりにラップすることMaybeです。

Haskell の規則に従って変数の名前を変更し、関数にもう少しわかりやすい名前を付けると、次のようになります。

canColor ::  Eq a => [(a, a)] -> [(a, a)] -> Bool
canColor _ [] = True
canColor xs ((x,y):rest) =
    if findNeighbour xs x == findNeighbour xs y
    then False
    else canColor xs rest

findNeighbour :: Eq a => [(a, a)] -> a -> Maybe a
findNeighbour [] _ = Nothing
findNeighbour ((x,y):rest) z =
    if x == z
    then Just y
    else findNeighbour rest z

ここでの考え方は、何も見つからない場合、または 23 (または見つかったもの) が見つかった場合にfindNeighbour戻るというものです。NothingJust 23

たまたま、findNeighbourは既に定義されています: と呼ばれていlookupます。したがって、コードを次のように書き換えることができます。

canColor ::  Eq a => [(a, a)] -> [(a, a)] -> Bool
canColor _ [] = True
canColor xs ((x,y):rest) =
    if lookup x xs == lookup y xs
    then False
    else canColor xs rest

ここで、基本的にリスト内のすべての項目に対して述語をチェックしていることに注意してください。これには関数があります: all. したがって、コードを次のように短縮できます。

canColor ::  Eq a => [(a, a)] -> Bool
canColor xs = all (\(x, y) -> lookup x xs /= lookup y xs) xs
于 2012-11-23T00:37:59.927 に答える