vmchale / recursion_schemes

Recursion schemes for Idris
BSD 3-Clause "New" or "Revised" License
64 stars 5 forks source link

Strange behavior for mutumorphism #3

Closed xgrommx closed 7 years ago

xgrommx commented 7 years ago

Hello again @vmchale =) I had to play with mutumorphism. For example I use classic version with mutual recursion

even :: Int -> Bool
even 0 = True
even n = odd (n - 1)

odd :: Int -> Bool
odd 0 = False
odd n = even (n - 1)

This is my code with example above but via recursion schemes

data Nat = Zero | Succ Nat deriving Show
data NatF a = ZeroF | SuccF a deriving (Show, Functor, Foldable, Traversable)

type instance Base Nat = NatF

instance Recursive Nat where
  project = \case
    Zero -> ZeroF
    Succ a -> SuccF a

instance Corecursive Nat where
  embed = \case
    ZeroF -> Zero
    SuccF a -> Succ a

toNat :: Integer -> Nat
toNat = ana $ \x -> if x == 0 then ZeroF else SuccF (pred x)

fromNat :: Nat -> Integer
fromNat = cata $ \case ZeroF -> 0; SuccF x -> x + 1

-- my version of mutu
mutu :: Recursive t => (Base t (a, a) -> a) -> (Base t (a, a) -> a) -> t -> a
mutu = go where go f g = g . fmap (go g f &&& go f g) . project

-- your version of mutu
mutu' :: Recursive t => (Base t (b, a) -> b) -> (Base t (b, a) -> a) -> t -> a
mutu' f g = snd . cata (f &&& g)

-- version of even-odd via mutumorphism
evenOdd :: Nat -> Bool
evenOdd = mutu f g where
  f ZeroF = False
  f (SuccF (b, _)) = b
  g ZeroF = True
  g (SuccF(b, _)) = b

evenOdd' :: Nat -> Bool
evenOdd' = mutu' f g where
  f ZeroF = False
  f (SuccF (b, _)) = b
  g ZeroF = True
  g (SuccF(b, _)) = b

So classic version for odd even 10 -- True My version evenOdd 10 -- True Your version evenOdd' 10 -- False

So, maybe your version of mutu has some different result or maybe my version. But anyway my result the same as in classic version. Thanks

vmchale commented 7 years ago

Thanks for the code! I added your mutumorphism as mutu for the time being until I can find a paper than can tell me which is "canonical". I also added your example to the test suite for the future.