All geek questions in one place

Haskell bifunctor after least fixed type

I am not sure how to get a functor instance after creating a fixed point:

data FreeF fa next = PureF a | FreeF (f next) deriving (Functor) data Mu f = In { out :: f ( Mu f ) } newtype Free fa = Free( Mu (FreeF fa) ) instance Functor f => Functor (Free f) where fmap h (Free (out -> PureF a)) = Free (In (PureF (ha))) fmap h (Free (out -> FreeF fn)) = Free (In (fmap undefined undefined)) --stuck

If I modify Mu to accept an additional type parameter, I can progress as long as ...:

 data Mu fa = In { out :: f ( Mu fa ) } deriving (Functor) newtype Free fa = Free( Mu (FreeF fa) a ) instance Functor f => Functor (Free f ) where fmap h (Free (out -> PureF a)) = Free . In . PureF $ ha fmap h (Free (out -> FreeF fn)) = Free . In . FreeF $ fmap undefined fn

Here I need to have undefined :: Mu (FreeF fa) a -> Mu (FreeF fb) b , but mu f is a functor for the same f and here it changes in type.

What is the correct way to solve this problem?

+5
source share
2 answers

mu f is a functor for the same f and here it changes in type.

Fortunately, we define Functor (Free f) , and we actually use this instance of Functor to display over a in PureF constructors. Functor (Free f) abstracts on all "internal" occurrences a .

So, whenever we want to match both occurrences of a , for example, when we want to implement FreeF fa (Mu (FreeF fa)) -> FreeF fb (Mu (FreeF fb)) , we can do this by wrapping everything on the way back to Free , matching, then expanding again.

The following are your original data definitions:

 newtype Free fa = Free {unFree :: Mu (FreeF fa)} -- add "unFree" instance Functor f => Functor (Free f) where fmap h (Free (In (PureF a))) = Free (In (PureF (ha))) fmap h (Free (In (FreeF fn))) = Free (In (FreeF (fmap (unFree . fmap h . Free) fn)))

Some tests:

 {-# LANGUAGE UndecidableInstances, StandaloneDeriving #-} deriving instance Show (f (Mu f)) => Show (Mu f) deriving instance Show (Mu (FreeF fa)) => Show (Free fa) foo :: Free [] Int foo = Free $ In $ FreeF [ In $ PureF 100, In $ PureF 200 ] > fmap (+100) foo Free {unFree = In {out = FreeF [In {out = PureF 200},In {out = PureF 300}]}}
+4
source

I haven’t done this before, but I think I see something. Your intuition about adding an argument to Mu is good, but you need to pass it so that Free f matches, i.e. So that f takes two arguments instead of one:

 newtype Mu fa = In { out :: f (Mu fa) a }

Mu f should be Functor under the right conditions, which will give you the example you are looking for. What are these conditions? We need:

 fmap' :: (a -> b) -> f (Mu fa) a -> f (Mu fb) b

We expect f be functorial in the second argument, so no problem. So what we really need to get

 f (Mu fa) b -> f (Mu fb) b ^ ^ +--not varying--+

We can use the instance recursively to get Mu fa -> Mu fb , so we just need f be a functor in its first argument. Hence:

 class Bifunctor f where bimap :: (a -> c) -> (b -> d) -> fab -> fcd

Then you can write suitable instances

 instance (Functor f) => Bifunctor (FreeF f) ... instance (Bifunctor f) => Functor (Mu f) ...
+3
source

Source: https://habr.com/ru/post/1240647/

More articles:


All Articles