Generic examples - Haskell

What are some good/motivating/unexpected Generic examples?

beam

Generic church encodings :big_smile:

That's unexpected one :slight_smile: - I guess generic Show, Read or ToJSON instances could be considered motivating - they allow you to get rid of lot of boilerplate by treating datatypes uniformly

I mean, Show and Read would be interesting if GHC didn't already automatically derive them. I am probably asking for too much without even explaining the context: trying to do a short presentation for the junior devs at the office on Generics, so I wish I could find some good motivating example to use.

The current contender is Eq since it's easy to explain and implement, but then it's hard to motivate why since GHC already derives it. ToJSON might be a good example; I wonder how easy it is to implement.

I think most of them have already used Generics in the sense that they derived it and reaped the benefits of derive anyclass (...), but I don't think any of them wrote their own typeclass / instances using Generic so I thought an example might help.

I did simplified AsJSON impl for similar purposes (it just didn't end up being used :slight_smile:)
I think that one is a good candidate, because it feels more real-world-like, works with both directions (to and from generic rep) and encoding of sums is a little bit more creative than just spitting out value corresponding to some constructor, while still simple enough

(AsJSON as in custom class for going to and from Aeson.Value)

That sounds interesting, I'll have a stab at it and see how it ends up. Thanks!

Reimplementing the derivations for Eq, Show, Functor etc. using generics would make for a pretty good blog post, I still have no idea how to do most of those

Eq is pretty trivial, but Functor might be rough. That's a good idea though!

GHC's stock deriving is not extensible though, as opposed to generics. You can take a generic implementation, which is just a function, and manually replace some of the cases, or even do "surgery" on your data types before deriving.

Monoid is another common example, that is not handled by stock deriving.

I'd really love to see an implementation of uniplate using Generic but I actually don't know if that's even possible

what do you use uniplate for?

https://www.stackage.org/haddock/lts-14.22/uniplate-1.6.12/Data-Generics-Uniplate-Operations.html#t:Uniplate this doesn't look difficult to genericise

but also there are no instances for this thing, so i don't know if it's what you're talking about

Compilers. Things like transforming every element of a certain type or getting all of the elements of a certain type

I use the Data instances since it's the easiest

But also not so fast

https://www.stackage.org/haddock/lts-14.22/uniplate-1.6.12/Data-Generics-Uniplate-Data.html

yeah you could definitely generate these generically

Are you familiar with resources that might help me understand how to implement this? I've read the chapter in your book and am currently slowing going through https://www.stackbuilders.com/tutorials/haskell/generics/

But this is really all I found on the topic

Specifically I'm unsure how to recurse through types and apply a function to an element of a specific type

which specific type? something concrete? or like a recursive bit

Like have exactly the api and behavior of transform or transformBi

If I pass (Int -> Int) to transformBi it will find all Ints in the type and transform them

Or through mutual recursion and stuff

you'd do something like this:

class GTransform a struct where
  gtransform :: (a -> a) -> struct x -> struct x

then do structural recursion over struct, and give instances for instance {-# OVERLAPPING #-} a (K1 a) that performs the function and instance {-# OVERLAPPED #-} a (K1 b) that doesn't

Oh

Ok I think I understand thank you!

and then

transform :: (Generic struct, GTransform a (Rep struct)) => (a -> a) -> struct -> struct
transform f = to . gtransform f . from

Very nice

(or you could use generics to derive the uniplate class directly)

Yeah that's also a good option

Thanks for the help!

Is overlapped a thing? I get unrecognized pragma warning

@gilmi Just overlapping by itself should work

Thanks :+1:

Ok I got transform to work and that's pretty awesome thanks for the help!

liberal usage of INLINABLE will make that puppy hella fast too

Will do

So this is what I got and I see very significant improvement over uniplate Data in my tiny benchmark
https://gist.github.com/soupi/c9048ca0d53c8a3c67f7f9a217748003

Does that make sense? Also, how can I get away from defining the Expr Int instances manually, if I don't do that I get a no Generic instance for Int

@gilmi You only want overlappingon GTransform a (K1 _1 a) case

yeah, seeing a perf improvement makes sense

if you look at the core representation i bet the generic transform is implemented as a case on the data structure that replaces it with the new value

versus uniplate which i would be surprised if it gets optimized away

but yeah, you only want this case to be oerlappying: instance {-# OVERLAPPING #-} Transform a a => GTransform a (K1 _1 a) where

Ok cool, is that so I can't implement other instances?

well you want the a a case to overlap the a b case

Right

Thank you

Any ideas regarding the Int instances?

i dont think you want those int instances

transform should be just a function, not a method

ah yeah, getting this thing recursive might be tricky

why do you bind a in the class of Transform?

Can it typecheck without it when I want to apply the function?

Oh, I don't actually need that info there right?

right

or MAYBE you do!!!

what semantics do you want here

if you are targeting a structure that is recursive in itself do you want to hit the leaves or not

I want to hit all occurrences of the type

Leaves and also with mutual recursion with other types

okay

so in that case i think you want transform to be a method

but with a universal a

and then you give an overlappable Generic instance for it

and you give specific Int and other primitive instances

each of which ignores the function

But then for example transform (+1) [1,2,3] == [1,2,3] because you ignore the function right?

no

in the a (K1 a) instance you recurse, and then apply the function you have

so the recursion fails, and then you apply the function you hvae :)

Oh! I understand.

Thanks for all the help, I really appreciate it.

happy to share

I'm not exactly sure how to fix the issue here but I'm getting 'two instances involving out of scope types' error
https://gist.github.com/soupi/c9048ca0d53c8a3c67f7f9a217748003
What am I doing wrong?

Also had a problem trying to define the overlapping generic instance for Transform

I think the uniplate business this is also doable by reusing generic-lens: https://github.com/kcsongor/generic-lens/issues/103#issuecomment-570422982

I opened that issue, I remember having some trouble with generic-lens that I couldn't figure out how to implement transform and universe using it. I was under the impression that the identity traversal for the same type case was a deal breaker but maybe i was mistaken

I see. You're right something probably needs to be changed; my point was more that the necessary mechanisms are already there, so it should be possible to avoid reinventing them.

Is there a simpler solution to defining generic aeson instances for types with the same shape but different field names? Like my json is { "id": 1, ... } but my type has a nodeId :: Int, ... field. I wish I could wrap the Int in some newtype and derive via (JsonFieldName "id") or something. I guess I could also do this with generic-data-surgery by removing and re-adding the field with the different name...?

I should probably have started a new thread.

There's something to rename fields in the options you pass to genericParseJSON/genericToJSON

Guess I could use that to write JsonFieldName myself.

... but then that function is just some String -> String and I don't get any compile-time errors. :(

Would it be possible to do something like...

data T = T
    { tOne :: String
    , tTwo :: String
    , three :: String
    }
    deriving (Generic)
    deriving ToJSON via (RenameFields '[ '( "tOne", "one" ), '( "tTwo", "two" ) ] T)

... which would result in an instance as if the type had the fields one, two, and three?

@Vladimir Ciobanu You could possibly demote that list to value level and do Data.List.lookup, sticking with current name if replacement is not found

But I want a compile-time error if tOne is not a field for T.

Maybe even if one is already a field, or if I do '[ '("tOne", "one"), '("tTwo", "one") ] as well.

Oh, actually - pass that list of replacements around in class that generates instance and give it some KnownSymbol (FindReplacement sym replacements) constraint, where FindReplacement is type family

And you want to collect all field names maybe upfront - then put family that checks those lists as constraint on top

@Vladimir Ciobanu I don't think such a thing exists in a library yet, but you can do it.

The closest thing I know is this, but it doesn't check for redundancies:
https://hackage.haskell.org/package/generic-data-0.7.0.0/docs/Generic-Data-Microsurgery.html#t:RenameFields

I did manage to get a generic version of transform to work, thanks everyone for the help!
While it is faster than uniplate Data, I have a feeling it can be even faster.
@Sandy Maguire or anyone else, if you could take a look at my approach and tell me if I did anything stupid I'd greatly appreciate it. The implementation is at the bottom:

https://gist.github.com/soupi/53351593af29acf58064aac6d6609e94

And benchmark results:

https://gilmi.me/static/misc/generic-plate-results.html

nice! it would be interesting to turn on -ddump-simpl -dsuppress-all and look at why generics is faster

I need to learn how to read this but it looks like this:
https://gist.github.com/soupi/3b84c2cb3bf81f9f629e3b563d7c9bd2

try again without the bench stuff

oh, maybe there isn't any? what hs file does this correspond to

I've removed those and uniplate as well. Only leaving one call to transform and the Expr because I didn't know if it might be relevant or not

So basically there's the definition of Expr, the function opts from the benchmark and the function check that runs one transform on a simple expression, and all of the transform code

I can upload that file if you like

yes please

https://gist.github.com/soupi/ee85d03775c21ad2f9270062deeb1b80

get rid of the showing stuff also please

OK

no deriving, no showing

just main = pure (transform opts) (Lit 1)

Should I get rid of the exprssion entirely or not?

i'd move the transform stuff into a separate module

define expr with only generic

define opts

and then main = pure (transform opts) (Lit 1)

OK

right now that core contains code for all of the stuff you're deriving, plus for the generic transformations, plus for how to do the error messaging, etc

obfuscating the bit we want to look at, and i cbf to find it in that sprall

Yeah I understand I'll upload the new files in a couple of minutes

https://gist.github.com/soupi/3b84c2cb3bf81f9f629e3b563d7c9bd2

Updated the file, below there's Compiling Main

Also I had to derive Generic

Also this doesn't look totally alien to me

:) looks like it was completely optimized away

ghc so smart

So basically this is the best we can get in your opinion?

hahah well it is doing zero work

so... hard to do better than that

:) Maybe I'll try a more complex expression?

i suspect it will also optimize away

Wait did it do this at compile time??

yeah!

Oh wow

i suspect any constant expr you put there will optimize away

try making one with a NOINLINE on it

I added a read <$> getLine

Updated the files

actually try it without read

just:

foo :: Expr
foo = Neg $ Neg $ Lit 5
{-# NOINLINE foo #-}

main = do
  pure $ transform opts foo

Ok

noinline should prevent the const expr optimization

Ohh I understand

Updated

Well I can kinda read this but I'm not sure if this is the desired result

hmm the generics aren't optiizing away

oh that's probably to be expected

actually i'm not sure whats's going on here

it's been a while since i've looked at core

Can ghc look at a L1 (R1 ..) and go 'oh! That's actually Neg'?

I'll start reading the 'Optimizing Generics Is Easy!' paper, it looks relevant here.

With -O2 instead of -O it looks different

yeah?

do all of the L1s disappear?

I think they did

I updated the gist

I did try running the benchmark again with O2 and didn't see improvements though

it's getting fully optimized again

Oh

nvm im crazy

If I add getLine it's not removing the L1s anymore