Haskell,graph,将函数放入最通用的形式 - > Eq

Question

我想把2个函数(color和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).

Answer 1

对于初学者来说,你无法概括Int为a 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