Home > Enterprise >  Write a transitive closure relation function in Haskell
Write a transitive closure relation function in Haskell

Time:10-06

I am supposed to write a function to return the transitive closure function of a relation. Here is what I have written so far:

relTrans :: [(Integer, Integer)] -> [(Integer, Integer)]
relTrans rel  |  rel == remove_dups(rel    relComp (remove_dups rel) (remove_dups rel))     =     rel
              |  otherwise                                                                  =     relTrans remove_dups(rel    relComp (remove_dups rel) (remove_dups rel))

The functions mentioned in this as remove_dups and relComp are as follows -

relComp :: [(Integer, Integer)] -> [(Integer, Integer)] -> [(Integer, Integer)]
relComp r1 r2 = [(a,c) | (a,k1)<-r1, (k2,c)<-r2, k1 == k2]

remove_dups :: [a] -> [a]
remove_dups [] = []
remove_dups (x:xs) = x : remove_dups (removeElem x XS)

removeElem :: a -> [a] -> [a]
removeElem n [] = []
removeElem n (m:zs) = if (n == m) then removeElem n zs else m:(removeElem n zs)

However, I keep getting the following error :-

    * Couldn't match expected type `[(Integer, Integer)]
                                    -> [(Integer, Integer)]'
                  with actual type `[(Integer, Integer)]'
    * The function `relTrans' is applied to two arguments,
      but its type `[(Integer, Integer)] -> [(Integer, Integer)]'
      has only one
      In the expression:
        relTrans
          remove_dups (rel    relComp (remove_dups rel) (remove_dups rel))
      In an equation for `relTrans':
          relTrans rel
            | rel
                == remove_dups (rel    relComp (remove_dups rel) (remove_dups rel))
            = rel
            | otherwise
            = relTrans
                remove_dups (rel    relComp (remove_dups rel) (remove_dups rel))
    |       
183 |               |  otherwise                                                                  =     relTrans remove_dups(rel    relComp (remove_dups rel) (remove_dups rel))
    |                                                                                                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

And this error -

    * Couldn't match expected type `[(Integer, Integer)]'
                  with actual type `[a0] -> [a0]'
    * Probable cause: `remove_dups' is applied to too few arguments
      In the first argument of `relTrans', namely `remove_dups'
      In the expression:
        relTrans
          remove_dups (rel    relComp (remove_dups rel) (remove_dups rel))
      In an equation for `relTrans':
          relTrans rel
            | rel
                == remove_dups (rel    relComp (remove_dups rel) (remove_dups rel))
            = rel
            | otherwise
            = relTrans
                remove_dups (rel    relComp (remove_dups rel) (remove_dups rel))
    |       
183 |               |  otherwise                                                                  =     relTrans remove_dups(rel    relComp (remove_dups rel) (remove_dups rel))
    |                                                                                                            ^^^^^^^^^^^

Can someone please help me out with why I am getting these errors please?

CodePudding user response:

You seem to be trying to use C-style function application here:

  relTrans remove_dups(rel    relComp (remove_dups rel) (remove_dups rel))
  --             here ^

In Haskell that applies the relTrans function to two arguments: remove_dups and (rel ...), but relTrans only has one argument, so you get an error.

You probably meant to write this:

  relTrans (remove_dups (rel    relComp (remove_dups rel) (remove_dups rel)))
  • Related