CODEWITHSUNDEEP
haskell
Dieter
Dieter

Reputation: 2659

Haskell, graph, put function into most general form -> Eq

I would like to put the 2 functions (color and check) into the most general form Eq a => .... But I don't know how to do that.

This is a very simple graph: each node has 2 neighbours, and any adjacent nodes must have different colors

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

At the end, colors gives you True or 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

Any help is welcome (+ if you can fix x = 999 into False).

Upvotes: 0

Views: 150

Answers (1)

scvalex
scvalex

Reputation: 15335

For starters, the reason you can't generalize the Int to an Eq a is because of the 999 hard-coded in check. If you just leave some random value in there, you must know its type, so you cannot generalize the function beyond that (well, in this particular case, you can generalize to Eq a, Num a, but not more).

So, the answer is to not use some arbitrary value, but instead wrap the return of check into a type that has a "failure" case, namely Maybe.

Renaming the variables to follow Haskell conventions, and giving the functions a bit more elucidating names, we get:

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

The idea here is that findNeighbour returns Nothing if it can't find anything, or Just 23 if it finds 23 (or whatever it finds).

As it happens, findNeighbour is already defined: it's called lookup. So, you could rewrite your code as:

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

Now, we note that you are basically checking a predicate against all items in a list. There's a function for this: all. So, we can shorten the code to:

canColor ::  Eq a => [(a, a)] -> Bool
canColor xs = all (\(x, y) -> lookup x xs /= lookup y xs) xs

Upvotes: 8

Related Questions