Evaluation using `Traversable`

[jacereda]

I thought I might raise this issue to discuss the possibility of evaluating via Traversable.

One of the stumbling blocks I found is the Sets we have in the AST. Normal Data.Set isn't Traversable because it has Ord restrictions.

I found https://github.com/giorgidze/set-monad but it doesn't have Traversable. I have PR'd https://github.com/giorgidze/set-monad/pull/10

Maybe there're other alternatives. I guess we could implement a simplified Set without Ord restriction. Since our sets will be quite small I guess something like that could be implemented on top of List without being too inefficient.

[jacereda]

Of course we could implement manually traverse on our AST, but I thought an automatic instance based on Generic would be more desirable.

[eriksvedang]

This sounds interesting indeed! What would be a good module to first try out this approach?

[jacereda]

You mean if it should be Eval or Expand? I guess the second is simpler...

[jacereda]

Oh, instead of Generic we could also use https://downloads.haskell.org/~ghc/latest/docs/html/users_guide/glasgow_exts.html#extension-DeriveTraversable

[eriksvedang]

Oh, maybe those are the only ones... :)

guess the second is simpler

Yes it must be

[jacereda]

I guess Scoring is a fold. Not sure about Emit, could it also be a fold?

And looking at more modules, looks like most of them could benefit from Foldable and/or Traversable.

[scolsen]

I guess Scoring is a fold. Not sure about Emit, could it also be a fold?

And looking at more modules, looks like most of them could benefit from Foldable and/or Traversable.

Yes, pretty much everything, I think, can be expressed in terms of a fold over the AST

[eriksvedang]

Some of the recursive functions branch in weird ways though - concretize & manageMemory comes to mind. Perhaps it's still possible to just fold, but I'm not sure.