bound
bound copied to clipboard
bound + recursion schemes
Is it possible to use bound
with recursion-schemes
library?
i.e. to define the names in an AST using bound
and doing AST transformations (optimisations, inlining, etc) with recursion-schemes
bound
tracks the context of a term in the types, which changes when going through binders, this seems quite incompatible with the view in recursion-schemes
of recursive types as fixed-points of a simple * -> *
functor.
This QA also seems relevant https://dirtcheaphaskell.io/#2018-01-25-recursion-schemes-bound
I’m not using bound
(yet), but I’ve had some recent success adapting Hinze’s approach from Efficient Generalized Folds:
https://github.com/robrix/path/blob/2da82c52cd17088fd6918ef3f37d3c13081dfd99/src/Path/Expr.hs#L32-L44
I tried a simple implementation of bound
+ recursion-schemes
, ~and it works so far~
https://gist.github.com/freckletonj/c54a60085e225e5bc67af27dc4c31f37
~I'm not sure if it'll break in subtle ways, perhaps when changing bound variables during a fold? Or using a bound var type more involved than ()
?~
EDIT: It cannot traverse into Scope
s, oops, the pattern constructor for LamF
wants a Scope ...
not an r
:
> :t PlusF
PlusF :: r -> r -> ExpF a r
> :t LamF
LamF :: Scope () Exp a -> ExpF a r
It cannot traverse into Scopes, oops, the pattern constructor for LamF wants a Scope ... not an r:
Exactly. It doesn't work correctly. With -ddump-splices
Test.hs:30:1-21: Splicing declarations
makeBaseFunctor ''Exp
======>
data ExpF (a_ablC :: ghc-prim-0.5.3:GHC.Types.Type) r_adrG
= VF a_ablC |
LamF (Scope () Exp a_ablC) |
r_adrG :@$ r_adrG |
IntF Int |
PlusF r_adrG r_adrG
deriving (Functor, Foldable, Traversable)
Note that in LamF
we still have Exp a
not r
.