Re:Don’t Think, Just Defunctionalize
by maxiepoo on Wednesday December 23, 2020 @09:25AM
(#25517881)
Yes, this is well known, good catch!
If you read McBride's paper "Clowns to the Left of Me, Jokers to the Right" (https://www.cis.upenn.edu/~cis39903/static/clowns.pdf) is exactly about systematically deriving the type of defunctionalized stacks for the fold over an ADT. The ordinary derivative is then the special case where you are just mapping a function that doesn't change the type.
> Defunctionalizing CPSed code will always produce a type isomorphic to a list, i.e. a stack (or something simpler if there is no recursion)
and McBride's derivatives of data structures?
(also, on very small machines, like in the card processing days, one had to mutate the input data structure itself as the holder of defunctionalised control information, instead of keeping it in a side structure as done here. On one hand this is a pain, on the other, it can also be useful nowadays, as it opens up parallelisation opportunities.)