haskellfunctional-dependencies

Illegal functional dependencies using the natural type,


data Zero = Zero 
data Succ x = Succ x 

class NatToPeano a b | a -> b where 
    toPean :: b
instance NatToPeano 0 Zero where toPean = Zero 
instance (NatToPeano (x-1) a) => NatToPeano x (Succ a) where
     toPean = Succ (toPean @(x-1))

This yields the error:

 Functional dependencies conflict between instance declarations:
  instance NatToPeano 0 Zero -- Defined at parsejava.hs:26:10
  instance NatToPeano (x - 1) a => NatToPeano x (Succ a)
    -- Defined at parsejava.hs:28:10

 26 | instance NatToPeano 0 Zero where

Solution

  • As per @Noughtmare's answer, you probably can't do exactly what you're trying to do here. For a comprehensive solution to converting back and forth between GHC type-level naturals and type-level Peano numbers, consider the type-natural package which uses a lot of trickery to get this right and to provide appropriate machinery to actually make it usable.

    The closest you may be able to come with your current code is to define a type family to convert GHC type-level naturals to your Peano representation solely at the type level:

    type family ToPeano n where
      ToPeano 0 = Zero
      ToPeano n = Succ (ToPeano (n-1))
    

    and then introduce a class to generate term-level Peano numbers from their type:

    class KnownPeano p where
      peano :: p
    instance KnownPeano Zero where peano = Zero
    instance KnownPeano x => KnownPeano (Succ x) where peano = Succ peano
    

    This will allow you to define a function:

    toPeano :: (KnownPeano (ToPeano n)) => ToPeano n
    toPeano = peano
    

    that uses the ToPeano type family to calculate the appropriate Peano type from the GHC natural, and then the peano type class function to generate the term-level Peano value for the Peano type, so you can write:

    ghci> toPeano @0
    Zero
    ghci> toPeano @2
    Succ (Succ Zero)
    

    This might be what you wanted, but it's hard to tell if it will actually work in your real application.

    The complete code:

    {-# LANGUAGE GHC2021 #-}
    {-# LANGUAGE AllowAmbiguousTypes #-}
    {-# LANGUAGE DataKinds #-}
    {-# LANGUAGE TypeFamilies #-}
    {-# LANGUAGE UndecidableInstances #-}
    
    module FundepPeano where
    
    import GHC.TypeNats
    
    data Zero = Zero
      deriving (Show)
    data Succ x = Succ x
      deriving (Show)
    
    type family ToPeano n where
      ToPeano 0 = Zero
      ToPeano n = Succ (ToPeano (n-1))
    
    class KnownPeano p where
      peano :: p
    instance KnownPeano Zero where peano = Zero
    instance KnownPeano x => KnownPeano (Succ x) where peano = Succ peano
    
    toPeano :: (KnownPeano (ToPeano n)) => ToPeano n
    toPeano = peano
    
    main :: IO ()
    main = do
      print $ toPeano @0
      print $ toPeano @2