Skip to content

Add genericTraverse#349

Closed
treeowl wants to merge 2 commits intotweag:masterfrom
treeowl:generic-traverse
Closed

Add genericTraverse#349
treeowl wants to merge 2 commits intotweag:masterfrom
treeowl:generic-traverse

Conversation

@treeowl
Copy link
Copy Markdown
Collaborator

@treeowl treeowl commented Oct 12, 2021

genericTraverse is an efficient implementation of traverse for
any Generic1 type.

@treeowl
Copy link
Copy Markdown
Collaborator Author

treeowl commented Oct 12, 2021

I'm sure everything is in the wrong place and some of the names are bad, but this seems to work quite nicely.

@treeowl
Add genericTraverse
b48778b 
`genericTraverse` is an efficient implementation of `traverse` for
any `Generic1` type.
@treeowl
Copy link
Copy Markdown
Collaborator Author

treeowl commented Oct 12, 2021

I don't know what has to happen to fix the Stack build. Tried and failed.

treeowl
treeowl commented Oct 12, 2021
View reviewed changes
src/Data/Functor/Linear/Internal/Traversable/Generic.hs
{-# INLINE gtraverse #-}

instance GTraversable V1 where
gtraverse _ v = pure ((\case) v)
Copy link
Copy Markdown
Collaborator Author

@treeowl treeowl Oct 12, 2021

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This is the way it's normally done in base. We could also match (fail) eagerly.

Copy link
Copy Markdown
Collaborator Author

@treeowl treeowl Oct 12, 2021

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

(I actually prefer the stricter way myself; just don't want to break expectations without buy-in.)

Copy link
Copy Markdown
Member

@aspiwack aspiwack Oct 12, 2021

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Do you have strong arguments either way? If not, let's probably leave it as it is in base.

Copy link
Copy Markdown
Collaborator Author

@treeowl treeowl Oct 12, 2021

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Strict lawfulness is my main argument, and I'll admit that's not terribly strong. It'll likely eliminate a little code as dead.

@utdemir
Copy link
Copy Markdown
Contributor

utdemir commented Oct 12, 2021 •
edited
Loading

Hey, thanks for the PR!

I don't know what has to happen to fix the Stack build. Tried and failed.

It was a minor fix, the linear-generics dependency had to be added under extra-deps, not packages. I pushed a commit fixing it for you.

As about this PR, it looks neat to me; but @aspiwack or @sjoerdvisscher is much better informed than me in this area, so I'm refraining from reviewing it.

@treeowl
Copy link
Copy Markdown
Collaborator Author

treeowl commented Oct 12, 2021

Thanks, @utdemir!

aspiwack
aspiwack reviewed Oct 12, 2021
View reviewed changes
Copy link
Copy Markdown
Member

@aspiwack aspiwack left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Should this PR introduce a combinator so that Traversable can be derived with deriving-via?

@sjoerdvisscher can you give this a review?

@treeowl I'm giving you the write bit, so that you can merge when the reviews are completed.

src/Control/Functor/Linear/Internal/Kan.hs
-- Traversable instances.
module Control.Functor.Linear.Internal.Kan where
import Control.Functor.Linear
import qualified Data.Functor.Linear as D
Copy link
Copy Markdown
Member

@aspiwack aspiwack Oct 12, 2021

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Suggested change
import qualified Data.Functor.Linear as D
import qualified Data.Functor.Linear as Data

In this package, there is no single-letter import 🙂

sjoerdvisscher
sjoerdvisscher approved these changes Oct 12, 2021
View reviewed changes
@treeowl
Copy link
Copy Markdown
Collaborator Author

treeowl commented Oct 12, 2021

@aspiwack, DerivingVia can't handle Traversable, due to type role issues. It's just not an option. If we dropped sequence we could use DefaultSignatures, but I know this project doesn't like those much.

@aspiwack
Copy link
Copy Markdown
Member

aspiwack commented Oct 12, 2021

@aspiwack, DerivingVia can't handle Traversable, due to type role issues. It's just not an option. If we dropped sequence we could use DefaultSignatures, but I know this project doesn't like those much.

Ah well… this is quite unfortunate. Who would have thought, when deriving-via landed that we'd run into role issues so often?

@treeowl
Copy link
Copy Markdown
Collaborator Author

treeowl commented Oct 12, 2021

@aspiwack, DerivingVia can't handle Traversable, due to type role issues. It's just not an option. If we dropped sequence we could use DefaultSignatures, but I know this project doesn't like those much.

Ah well… this is quite unfortunate. Who would have thought, when deriving-via landed that we'd run into role issues so often?

It's possible to modify the type of traverse to make it compatible. The issue is that the ergonomics of hand-written instances get a bit wonky. Ignoring the linear types, we could have

class (Functor t, Foldable t) => Traversable t where
  traverseThen :: Applicative f => (t b -> r) -> (a -> f b) -> t a -> f r
  traverseThen t f = fmap t . traverseCoerce f
  
  traverseCoerce :: (Applicative f, Coercible (t b) r) => (a -> f b) -> t a -> f r
  traverseCoerce = traverseThen coerce

@aspiwack
Copy link
Copy Markdown
Member

aspiwack commented Oct 12, 2021

Let's not go there for the moment.

@treeowl
Copy link
Copy Markdown
Collaborator Author

treeowl commented Oct 14, 2021

My biggest concern is that performance of generic Traversable instances is extremely fragile for sum types, at least under GHC 9.0. There's a tendency for things to turn into join points that we really want to inline away. I'll have to install 9.2 to see if that's changed any, but I'm not terribly optimistic. I am curious whether there's some way to add a method to Generic/Generic1 that would do a better job. It seems likely that there's some space between the GHC.Generics approach and the Data.Data approach that would be better for this sort of thing, but I don't really know what that might look like.

@tbagrel1 tbagrel1 mentioned this pull request Feb 4, 2022
Merged
@aspiwack aspiwack added this to the v0.2.0 milestone Feb 11, 2022
@tbagrel1
Copy link
Copy Markdown
Member

tbagrel1 commented Feb 15, 2022

I think that we can close it now that #366 is merged.

@aspiwack
Copy link
Copy Markdown
Member

aspiwack commented Feb 15, 2022

Yes. Let's close thank you both!

@aspiwack aspiwack closed this Feb 15, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@aspiwack aspiwack aspiwack left review comments

+1 more reviewer

@sjoerdvisscher sjoerdvisscher sjoerdvisscher approved these changes

Reviewers whose approvals may not affect merge requirements

Assignees

No one assigned

Labels

None yet

Projects

None yet

Milestone

v0.2.0

Development

Successfully merging this pull request may close these issues.

5 participants

@treeowl @utdemir @aspiwack @tbagrel1 @sjoerdvisscher