And yeah, the compiler can derive the functor instance! I don't know the mechanism for how it works but I think it might assume the last type parameter is the 'container' field (think the values in a list or maybe)
It's not in the standard lib, but you can find a few implementations (it's usually called cata for catamorphism) available on hackage. I have used recursion-schemes and it works pretty well.
I learned about this stuff via this excellent blog series: https://blog.sumtypeofway.com/posts/introduction-to-recursio...
Compare the Functor instances of the original inductive Tree type with TreeShape a:
instance Functor Tree where
fmap :: (b -> c) -> Tree b -> Tree c
fmap f (Leaf v) = Leaf (f v)
fmap f (Node l r) = Node (fmap f l) (fmap f r)
instance Functor (TreeShape a) where
fmap :: (rec -> b) -> TreeShape a rec -> TreeShape a b
fmap _ (Leaf v) = Leaf v
fmap f (Node l r) = Node (f l) (f r)
You see that in the latter the function we map over acts on the rec type which is the induction we factored out and is only present in the Node case. You can view the Leaf case as the termination case where Fix stops expanding. It's useful to write out the evaluation by hand on a small example to see how it works.> I'm also curious about "the compiler is more than happy to do it for us" - is that in the form of `deriving Functor`?
It is indeed the deriving Functor. You can even examine what the compiler does by dumping out the instance using the -ddump-deriv flag.
For more background reading as to why this is possible here are a few links:
- https://mail.haskell.org/pipermail/libraries/2011-February/0...
- https://www.schoolofhaskell.com/user/edwardk/snippets/fmap
> I have never seen stock before!
It comes from the DerivingStrategies lang extension which makes it explicit that this derivation is "built in". Everything works the same without it though so we can just ignore it as well.
> Lastly, does `processFunctor` exist in the standard library?
If by standard you mean the Prelude then no, but there are tons of packages, eg.:
- https://hackage.haskell.org/package/data-fix
- https://hackage.haskell.org/package/recursion-schemes
`fmap _ (Leaf v) = Leaf (f v)` right? (s/v/f v)
I'm also curious about "the compiler is more than happy to do it for us" - is that in the form of `deriving Functor`? I have never seen stock before!
Lastly, does `processFunctor` exist in the standard library? Seems powerful but unsure why I would personally have to write it with each project.