4 ms·

This is really great, thanks :) `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

This is really great, thanks :) `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.

pwm 6y ago
> `fmap _ (Leaf v) = Leaf (f v)` right? (s/v/f v) 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/015964.html https://mail.haskell.org/pipermail/libraries/2011-February/0... - https://www.schoolofhaskell.com/user/edwardk/snippets/fmap 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/data-fix - https://hackage.haskell.org/package/recursion-schemes https://hackage.haskell.org/package/recursion-schemes - https://hackage.haskell.org/package/compdata https://hackage.haskell.org/package/compdata - https://hackage.haskell.org/package/yaya https://hackage.haskell.org/package/yaya
tominated 6y ago
Not quite - think of the functor as a container for the recursive field, not the values attached to leaves. The leaf is your base recursive case and doesn't have a value to map over. Having your functor instance map over this recursive field is what allows you to write a non-recursive function that expects the field to have the already processed value from it's children! 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-recursion-schemes.html https://blog.sumtypeofway.com/posts/introduction-to-recursio...

pwm 6y ago

> `fmap _ (Leaf v) = Leaf (f v)` right? (s/v/f v) 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/015964.html https://mail.haskell.org/pipermail/libraries/2011-February/0... - https://www.schoolofhaskell.com/user/edwardk/snippets/fmap 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/data-fix - https://hackage.haskell.org/package/recursion-schemes https://hackage.haskell.org/package/recursion-schemes - https://hackage.haskell.org/package/compdata https://hackage.haskell.org/package/compdata - https://hackage.haskell.org/package/yaya https://hackage.haskell.org/package/yaya

tominated 6y ago

Not quite - think of the functor as a container for the recursive field, not the values attached to leaves. The leaf is your base recursive case and doesn't have a value to map over. Having your functor instance map over this recursive field is what allows you to write a non-recursive function that expects the field to have the already processed value from it's children! 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-recursion-schemes.html https://blog.sumtypeofway.com/posts/introduction-to-recursio...