From Object Oriented Programming to Functional Programming(github.com)
github.com
From Object Oriented Programming to Functional Programming
https://github.com/Dobiasd/articles/blob/master/from_oop_to_fp_-_inheritance_and_the_expression_problem.md
4 comments
> class hierarchies just don't really work in Haskell
They work beautifully in Haskell
They work beautifully in Haskell
class Eq a => Ord a
class (Num a, Ord a) => Real aIt's more that classes just don't behave the same as `class` in an OOP sense. You can create a subtype hierarchy using typeclasses—Functor->Application->Monad->MonadPlus/Applicative is a great example and the `lens` hierarchy is an even more sophisticated one.
But these are subtype hierarchies, not subclass hierarchies. Furthermore, classes don't necessarily provide you with the full convenience of an object, though they can come close. Finally, people aren't used to working in codata and Haskell doesn't make it easy, so you have trouble there, too.
But these are subtype hierarchies, not subclass hierarchies. Furthermore, classes don't necessarily provide you with the full convenience of an object, though they can come close. Finally, people aren't used to working in codata and Haskell doesn't make it easy, so you have trouble there, too.
You can't create subtype hierarchies in Haskell. Haskell doesn't have any subtyping: every value has exactly one type. This is why you cannot use the OOP solution for the game, which requires lists whose elements have a common supertype. Even with existential types (as the author mentions), you still do not have any subtyping.
Typeclasses are collections of types. All types in the applicative class are also in the functor class, but none of these types are subtypes of any others.
Typeclasses are collections of types. All types in the applicative class are also in the functor class, but none of these types are subtypes of any others.
Except there are quantified types, so `forall a. Functor a => a` is the type of "all types instantiating Functor" and `forall a. Applicative a => a` is a subtype. These are commonly used due to the implicit forall quantification.
Edit: I'm rusty here, but after re-reading the LSP I'd also say that existential types could exhibit subtyping as the set of statements provable about them is often exactly those provable about the universally quantified type.
Edit: I'm rusty here, but after re-reading the LSP I'd also say that existential types could exhibit subtyping as the set of statements provable about them is often exactly those provable about the universally quantified type.
Neither of the types you gave is inhabited, because the 'a' has kind * -> * .
I think what you've said about subtyping is muddled. If a type A is a subtype of B, then values of type A should be values of type B. Now let's take an example from the number class hierarchy. Consider
The only formal account of universal quantifiers in type theory, of which I am aware, extends the term language by introducing a capital lambda that ranges over types. So the polymorphic identity function is actually the term
This makes good sense of the way number classes work in Haskell. When you write
EDIT: Another way of explaining the counterexample: any type in Applicative is also in Functor. But, on one informal interpretation of forall, the intersection of all applicatives is actually a proper superset of the intersection of all functors.
I think what you've said about subtyping is muddled. If a type A is a subtype of B, then values of type A should be values of type B. Now let's take an example from the number class hierarchy. Consider
1) forall a. Num a => a
2) forall a. Integral a => a
n = 1 :: forall a. Integral a => a
n :: forall a. Num a => a
The only formal account of universal quantifiers in type theory, of which I am aware, extends the term language by introducing a capital lambda that ranges over types. So the polymorphic identity function is actually the term
Λa. λx:a. x
This makes good sense of the way number classes work in Haskell. When you write
n :: Num a => a
n = 1
EDIT: Another way of explaining the counterexample: any type in Applicative is also in Functor. But, on one informal interpretation of forall, the intersection of all applicatives is actually a proper superset of the intersection of all functors.
I wouldn't expect (Integral a, Num b) => a -> b, but I do expect the opposite. That seems to be exactly the definition of LSP.
And yeah, if you add System F type binders then you can do all of this explicitly, you just need to also manually pass around instance dictionaries. A morphism from one instance dictionary to another (which "forgets" "methods") provides your subtyping relation.
And yeah, if you add System F type binders then you can do all of this explicitly, you just need to also manually pass around instance dictionaries. A morphism from one instance dictionary to another (which "forgets" "methods") provides your subtyping relation.
You have
The problem can be circumvented as described in the OP, or by using existential types. However, we still have hetergeneous lists, but the concrete type has been abstracted.
(Integral a, Num b) => a -> b
(Num a, Integral b) => a -> b
n :: Num a => a
n = 1
n :: Integral a => a
Num a => [a]
The problem can be circumvented as described in the OP, or by using existential types. However, we still have hetergeneous lists, but the concrete type has been abstracted.
Okay, sorry, my arguments have been a little imprecise—the disadvantage of typing on a phone. I'll try to do better now.
(1) Given two typeclasses which have `class A x => B x` then the type `forall x . B x => x` can be coerced to `forall x . A x => x`. You can do this explicitly using existential types.
(2) Functions are a little weird since (->) is a profunctor and thus is contravariant in the first argument and covariant in the second. Thus, using the coercion above you'd note that any function where `forall x . A x => x` is an input may be replaced by `forall x . B x => x` and when it's an output then the replacement goes the other way.
(3) fromIntegral is a bad example because it relies on the specific functions in the typeclasses Integral and Num--- it's just `fromIntegral . toIntegral`.
I think this kind of stuff is a kind of subtyping. It seems to follow the Liskov Substitution Principle.
(1) Given two typeclasses which have `class A x => B x` then the type `forall x . B x => x` can be coerced to `forall x . A x => x`. You can do this explicitly using existential types.
(2) Functions are a little weird since (->) is a profunctor and thus is contravariant in the first argument and covariant in the second. Thus, using the coercion above you'd note that any function where `forall x . A x => x` is an input may be replaced by `forall x . B x => x` and when it's an output then the replacement goes the other way.
(3) fromIntegral is a bad example because it relies on the specific functions in the typeclasses Integral and Num--- it's just `fromIntegral . toIntegral`.
I think this kind of stuff is a kind of subtyping. It seems to follow the Liskov Substitution Principle.
That's either backwards or just wrong. Perhaps you're confusing this with the syntax for existentials in data-declarations? I'm really not sure.
'forall x. A x. x' is a type of polymorphic values. Given such a value, I can instantiate the type-variable to any instance of the type class A. For instance, given
More generally, you cannot coerce a value of type 'forall x. B x => x' to one of type 'forall x. A x => x', because that would allow the type variable to range outside B. Consider:
If you want to talk about contravariance, you can note that when you add a type-class constraint of the form A x => x, you've basically got an implication, and the "A x" is in contravariant position. That's why your example is, if anything, the wrong way around.
What you can do with existential types in Haskell is kind of like subtyping. At least, it's kind of like what you do in the C++ example with abstract types. But that's because abstract types are kind of like existential types. Full class hierarchies can then be mocked with Haskell type classes, existential quantifiers and explicit coercion functions, but that's because subclassing is kind of like containment which is kind of like implication which is kind of like the type of a coercion function. But by this stage, we've got a long way off from saying that type-class hierarchies in Haskell are subtype hierarchies, as you originally suggested. They're certainly not in Haskell 98, and with existential types, they don't give you the implicit upcasting that comes from values having multiple types. Even with existential types, all values have exactly one type, and this is crucial to remember when trying to reason about Haskell's type system. In other words, forget about subtypes!
'forall x. A x. x' is a type of polymorphic values. Given such a value, I can instantiate the type-variable to any instance of the type class A. For instance, given
x :: Num a => a
y :: Float
y = x
z :: Integer
z = x
x :: forall a. Integral a => a
y :: Float
y = x
More generally, you cannot coerce a value of type 'forall x. B x => x' to one of type 'forall x. A x => x', because that would allow the type variable to range outside B. Consider:
x :: forall x. Real x
x = 0.5
coerce :: (forall x. Real x) -> (forall x. Num x)
n :: forall x. Num x
n = coerce x
m :: Integer
m = n
If you want to talk about contravariance, you can note that when you add a type-class constraint of the form A x => x, you've basically got an implication, and the "A x" is in contravariant position. That's why your example is, if anything, the wrong way around.
What you can do with existential types in Haskell is kind of like subtyping. At least, it's kind of like what you do in the C++ example with abstract types. But that's because abstract types are kind of like existential types. Full class hierarchies can then be mocked with Haskell type classes, existential quantifiers and explicit coercion functions, but that's because subclassing is kind of like containment which is kind of like implication which is kind of like the type of a coercion function. But by this stage, we've got a long way off from saying that type-class hierarchies in Haskell are subtype hierarchies, as you originally suggested. They're certainly not in Haskell 98, and with existential types, they don't give you the implicit upcasting that comes from values having multiple types. Even with existential types, all values have exactly one type, and this is crucial to remember when trying to reason about Haskell's type system. In other words, forget about subtypes!
Essentially I'm saying nothing more than I can change a function A -> (B, C) to a function (A, X) -> B. Typeclasses provide a way to represent a more general space of those functions. Existential types are the explicit way of writing the kind of subtyping I'm talking about—so if you need it to be an explicit hierarchy then, yes, you need extensions to Haskell98.
The best example of doing this without existential types (though it violates Haskell98 in its own way) the lens library. It absolutely provides a natural subtyping hierarchy without using existential types, though all of the coercions are implicit.
I'm very confident in my understanding of the Haskell behavior, but I'm happy to concede that my use of subtyping terminology is off. I cannot see how the behavior you see in lens doesn't provide a stellar example of LSP, though.
The best example of doing this without existential types (though it violates Haskell98 in its own way) the lens library. It absolutely provides a natural subtyping hierarchy without using existential types, though all of the coercions are implicit.
I'm very confident in my understanding of the Haskell behavior, but I'm happy to concede that my use of subtyping terminology is off. I cannot see how the behavior you see in lens doesn't provide a stellar example of LSP, though.
Ahh, hah. My mistake on the kinds. I changed it from an example on Num and Show because I don't much like how they're related.
There's always O'haskell. I believe normal Haskell does support structural subtyping, even if not nominal.
>There's always O'haskell.
No, there isn't. Last update was in 2001. It was never really alive, but it is very dead now.
No, there isn't. Last update was in 2001. It was never really alive, but it is very dead now.
Right, but it still demonstrates how nominal subtyping could be added to Haskell.
Isn't that more a has-a than an is-a?
The proposed class hierarchy for different types of "game objects" is exactly the type of hierarchy which will bite you in the ass very soon when adding more features, an entity-component-system would be a better solution for this specific problem (composition instead of inheritance). Newbie programmers should never be taught this "animal - cat - dog" nonsense IMHO because this approach of modelling software after real-world objects doesn't work for anything slightly more complex. For instance, what if you have two different enemy types which both need to implement a common feature but differ in others? Please don't say 'multiple inheritance' ;) This doesn't mean that OOP is bad at all IMHO, just that it shouldn't be treated as a holy grail (applies to all design principles), and doesn't mean that you have to go all-functional. All IMHO of course.
These exercises have nothing to do with expression problem.
The goal of expression problem is ability to add new cases in type and new operations on type without touching existing code (and without compromising static type safety)
The goal of expression problem is ability to add new cases in type and new operations on type without touching existing code (and without compromising static type safety)
They also get the solution wrong: only OOP can define new variants and only FP can define new operations. Actually, there are plenty of language, FP and OOP, where it is easy to define new variants and new operations orthogonally without sacrificing separate compilation (e.g. any OO language with mixins like Scala). Mads published a paper [1] on some solutions back in 2004.
[1] http://lambda-the-ultimate.org/node/2232
[1] http://lambda-the-ultimate.org/node/2232
It's also easy enough to define new variants in Haskell if you package things as codata. I feel it's less to do with OOP/FP and more to do with whether you're using data or codata.
Could you elaborate or provide links to examples of what you mean by solving this with codata?
My terminology isn't great, but what I'm talking about in practice is usually what happens as the next step after someone gets talked down from using existential types all over the place.
I'm personally a big fan of existential types, but they usually don't need to be explicit. One place that shows up on Hackage that's worth studying is Edward Kmett's `folds` library. The type, Data.Fold.L.L is a codata type
The existential type highlights that L is acting as codata, but it's usually not recommended in practice as existential types are a little hard to manage. You could write L more simply and eliminate the `r` data
In any case, the point is that it's easy to build a variety of L variants, but hard to extend new operations on Ls.
I'm personally a big fan of existential types, but they usually don't need to be explicit. One place that shows up on Hackage that's worth studying is Edward Kmett's `folds` library. The type, Data.Fold.L.L is a codata type
data L = forall r . L (r -> b) (r -> a -> r) r
The existential type highlights that L is acting as codata, but it's usually not recommended in practice as existential types are a little hard to manage. You could write L more simply and eliminate the `r` data
data L = L b (a -> L)
In any case, the point is that it's easy to build a variety of L variants, but hard to extend new operations on Ls.
Btw, here are a few example variants of `L`
sum :: Num a => L a a
sum = L id (+) 0
prod :: Num a => L a a
prod = L id (*) 1
list :: L a [a]
list = id (\r a -> a : r) []Any book that sounds like "functional programming in practice" for C++ programmers ?
What about a component oriented design? This is the standard architecture for games anyway.
An enemy, actually every entity, would just be a map of components, which can be simple algebraic data types. The actions can be implemented as a system function with pattern matching or guards, like:
In reality systems usually work on more than one component, so you'd have to make actions that work on tuples of components, but you'll figure it out :)