Type classes, collections, sum types, closures, and a massive headache
Hi, I'm relatively new to Haskell, and consider myself to be towards the beginner side of the scale. Nevertheless, I've got this Haskell program I've been working on that's sitting around 11k lines right now. The pattern has been to let it grow to then knock it back by 'refactoring' or whatever you want to call it… doing it right the second time maybe… or the third time. All I want to get across is that though I consider myself a Haskell beginner I've still managed to produce something that is actually quite complex and of reasonable size in about three months. I'm still getting caught by stuff that I should not be caught by. So. Today I thought it was about time to simplify how new 'things' of a certain kind are added to the system. These things are some a cross between an event and an assertion of a fact in a rule based system. There are many different kinds of these things. I already have more than a dozen commonplace ones, and I expect there's a much larger number of more specialized ones that a user will want to add on their own. While they start out quite differently, they end up satisfying a common interface and follow the identical three or four state lifecycle. This sounded like a type class to me, and in fact, easily implemented as such. Now, this is how I got caught: it seems to be impossible to have collections of things with a common type class if they have different types. How is it that I've written that many lines of code in Haskell and I'm just noticing this now? (If I wasn't so annoyed, I'd look for something clever to reflect how loc count obviously doesn't mean much… but clever seems to be beyond me today). Is this true? Are there any GHC extensions that will let me around this? The immediate problem is mapping an input to the system, some json message containing a reference to the 'thing' (like a key of some kind). I have to take that reference and find the thing and operate on it. All operations are easily accommodated by a type class. However, since I can't have a collection with mixed types even if the types satisfy a type class, I can't quite see how to actually store the things so I can find them. So there are a couple of obvious ways to handle this. I could use an ADT and a sum type of all the known kinds of thing, but I already know that this has to be extended and that's going to be problematic with users doing this on their own. And the type signatures look ugly. So I think that's not the best. I could use an ADT that contains functions that correspond to the functions of the type class, and that close over the 'thing' in question. I think this could be made to work, but I'm concerned with walking into more nasty surprises… If anyone is able to make sense of what I wrote and has any suggestions I'd really appreciate hearing them. Thanks, Bob
If I understand your message well enough, I think you are looking for GHC's `ExistentialQuantification` extension. Building heterogeneous collections is a common example of what existential types are useful for. Take a look at this wiki page [1]; there is an example of how to accomplish this there, along with a handful of other techniques. [1] http://www.haskell.org/haskellwiki/Heterogenous_collections#Existential_type...
On Mon, Jan 28, 2013 at 5:43 PM, Bob Hutchison
Now, this is how I got caught: it seems to be impossible to have collections of things with a common type class if they have different types. How is it that I've written that many lines of code in Haskell and I'm just noticing this now? (If I wasn't so annoyed, I'd look for something clever to reflect how loc count obviously doesn't mean much… but clever seems to be beyond me today).
Is this true? Are there any GHC extensions that will let me around this?
I just encountered this recently myself. There is a GADT extension [1][2] that may help. The greater abstraction appears to lie in existential types [3]. That being said, I'm a beginner as well and haven't yet used these extensions. So far I have found that my code is simplified by redefining heterogeneous types in terms of homogeneous functions. If I have a class that implements common methods, I will reorganize lists by common function types rather than by class. Cheers, Darren --- [1] http://www.haskell.org/haskellwiki/GADT [2] http://www.haskell.org/haskellwiki/GADTs_for_dummies [3] http://www.haskell.org/haskellwiki/Existential_type
Today I thought it was about time to simplify how new 'things' of a certain kind are added to the system. These things are some a cross between an event and an assertion of a fact in a rule based system. There are many different kinds of these things. I already have more than a dozen commonplace ones, and I expect there's a much larger number of more specialized ones that a user will want to add on their own. While they start out quite differently, they end up satisfying a common interface and follow the identical three or four state lifecycle. This sounded like a type class to me, and in fact, easily implemented as such.
I hardly ever use typeclasses, I've never used existential types or GADTs, and it's worked fine for me for many years. Maybe just a difference in programming style, or the sorts of things I write, but implies at least that you can get very far not using any of that stuff. If each of your things have the same 3 or 4 states, can you make a state into a value, and compose them? E.g. 'thing1 = state1 <> state2 <> thing1state where thing1state = ...' and state1 and state2 are defined in a library. If you have lots of different ways to take A to B and want to let the caller configure it, then just pass an A->B function. If you want to configure an unpredictable subset of things, then maybe make a default record and pass 'default { aToB = customVersion }'. If each function depends on a configuration environment that you want to inherit from callers, then maybe put that record into a Reader. In my case, the main design decision winds up being the balance of data (i.e. records with values or functions) and code (i.e. functions that do parts of what you want and can be composed together in various ways). Code is extensible and flexible but can't be manipulated, data is inflexible (in that you have to hardcode some kind of "schema"), but that means you can write functions to transform it.
On 29/01/2013, at 12:43 PM, Bob Hutchison
The immediate problem is mapping an input to the system, some json message containing a reference to the 'thing' (like a key of some kind). I have to take that reference and find the thing and operate on it. All operations are easily accommodated by a type class. However, since I can't have a collection with mixed types even if the types satisfy a type class, I can't quite see how to actually store the things so I can find them.
So there are a couple of obvious ways to handle this.
I could use an ADT and a sum type of all the known kinds of thing, but I already know that this has to be extended and that's going to be problematic with users doing this on their own. And the type signatures look ugly. So I think that's not the best.
I could use an ADT that contains functions that correspond to the functions of the type class, and that close over the 'thing' in question. I think this could be made to work, but I'm concerned with walking into more nasty surprises…
My advice is to go for the latter option. I'm not sure what nasty surprises you are expecting, but this "record of functions" approach is the one that I normally take when I am building a system that needs new types added without requiring global changes. I know that existentials and GADTs are possible solutions, but I've not needed the extra complexity here. Cheers, Tim
Thanks everyone, I very much appreciate your help, and I think it did help. I've spent the last few days implementing a substantial chunk of my system using each of two different techniques. I've ended up going with and ADT containing functions closed over the 'thing'. This seems to be the consensus advice. For the record there was a perfectly viable alternative approach based on existential types (http://www.haskell.org/haskellwiki/Heterogenous_collections#Existential_type..., thank Taylor, I'd read that and it didn't register… sigh). From what I could tell from trying them there's not a lot to choose between the two techniques, some small advantages for each. The existential types technique (despite criticism as an anti-patternhttps://lukepalmer.wordpress.com/2010/01/24/haskell-antipattern-existential-..., thanks Petr) is surprisingly to my taste… what can I say? I ended up going with the ADT because I can shove some additional stuff in it, and since there's still a large exploratory aspect to the project this might matter. Thanks again, Bob
for your convenience, the correct link: https://lukepalmer.wordpress.com/2010/01/24/haskell-antipattern-existential-...
participants (5)
-
Bob Hutchison -
Darren Grant -
Evan Laforge -
Taylor Hedberg -
Tim Docker