I have to say that I definitely enjoy using haskell when faced with dirty complicated data, which I'm told happens a lot in larger organizations.
Wait until you discover the power of Applicative Functors. They are more restricted in their operations than Monads, so they compose better and allow for analysis.
It's easy to see why when you consider the opaqueness of the function in the right-hand side of a bind. Check out http://gergo.erdi.hu/blog/2012-12-01-static_analysis_with_ap... for an example.
F A
G A
F (G A)
G (F A)
But for monads only the first two are monads for general monads F and G. So, Applicatives compose better!In addition to composition, products of Applicatives are also Applicatives:
(F A, G A)
newtype ContT r m a = ContT ((a -> m r) -> m r)
so ContT M A is not the same as Cont (M A).Monads also compose under products as two parallel monadic computations
data (f * g) a = Pair (f a) (g a)
p1 :: (f * g) a -> f a
p1 (Pair fa _) = fa
p2 :: (f * g) a -> g a
p2 (Pair _ ga) = ga
instance (Monad f, Monad g) => Monad (f * g) where
return a = Pair (return a) (return a)
Pair fa ga >>= k = Pair (fa >>= p1 . k) (ga >>= p2 . k)
You can also talk about composition under sums data (f + g) a = Inl (f a) | Inr (g a)
and you'll get compositions of applicatives here so long as you have a notion of natural transformation class Natural f g where
phi :: f a -> g a
instance (Applicative f, Applicative g, Natural f g) => Applicative (f + g) where
pure a = Inl (pure a)
Inl ff <*> Inl fa = Inl ( ff <*> fa)
Inr gf <*> Inr ga = Inr ( gf <*> ga)
Inl ff <*> Inr ga = Inr (phi ff <*> ga)
Inr gf <*> Inl fa = Inr ( gf <*> phi fa)
but there's no way to get a similar monad. It turns out that you have to "know what branch to go down before you start" in exactly the kind of way applicatives allow and monad preclude.E.g. you can do compile-time exhaustiveness-checked pattern matching using the visitor pattern in Java/C++, but try doing that in practice and the amount of boilerplate just becomes unbearable -- and actually obscures (rather than illuminate) the essence of the data structure.
There's also the lack of higher-kinded types. (Or just plain syntactic pain of using HKTs e.g. in Scala.)
Thus, there are certainly non-trivial and interesting static invariants which you can encode in Haskell and cannot in Java.
The most critical and strong common one is probably parametricity.
Interestingly[1], the power of the type system seems to conflict somewhat with type inference. Or, at least, that a Turing Complete type-level language like in Shen or Idris does require you to spell out increasing amounts of type information. Obviously, this has to do with undecidability of TC languages, but I kind of think it's interesting that e.g. Haskell seems to occupy a kind of "sweet spot" in terms of inference and being able to tell the programmer when it needs a type ascription. AFAICT that would be impossible in a language whose type system is a-priory undecidable, correct? (Just to spell it out: In Haskell, the compiler knows that if you want feature X, Y and Z, then constructs A, B and C become undecidable... and can tell you so.)
[1] Well, I found it interesting, but I'm a layman at best.
Which is really fascinating when you think about it. It basically expresses (what we all know) that your code captures only a fragment of the intent of your efforts. Good types can capture much more intent.
So to that end, people explore interactive development. In this scenario, you provide a (potentially partial) type corresponding to the programmatic intent you desire and the compiler conducts proof search to find programs which satisfy that type!
The types are actually more informative than the programs and it provides some evidence that we'd really rather be writing at higher-level typed languages and letting the implementations fall out naturally rather than writing the implementations and hoping that inference can build the proper types.
Or something like that.
Programming is weird.
Types can't be wrong in the same way that values can be. Rather, to be more specific, in any circumstance where program derivation could even remotely succeed you will have had to have been specific enough with your types that they cannot easily produce the wrong code. It simply would fail to typecheck---at least eventually.
I wouldn't say that program derivation is limited to demo-level code, I would just say that you cannot expect proof search to achieve large fragments of code. It's just too large of a space!
Instead, it's better to think of it as an interactive game. You describe types as best as you can leaving holes where you haven't figured out what you want. The compiler responds telling you information and guesses about those holes. Furthermore, if you can nail down what you must prove sufficiently well to have confidence that it's the right thing then the compiler can probably do the trivial final details for you.
If you look through Conor McBride's (admittedly vast) literature then you'll find many things discussing this idea with respect to his (now defunct) experimental dependently typed language called Epigram.
I kind of see, logically, that the types can't be wrong in quite as many ways as the code/values/terms, but that's still a (possibly) infinite amount of wrong to contend with! Yes, we can, and frequently do, narrow it down, but still... :)
I've been aware of Mr. McBride's literature for some time, but I haven't ventured in beyond a cursory look at that ridiculously-well-punned Sinatra one. ("Do be do"... something?). It's a bit beyond what I can manage, in theory terms, at the moment.
EDIT: Sorry to sound like an excited puppy, but I don't think the time/place was quite right for me to have gone into or explored this field as I would have liked to as an undergraduate.
You face the infinite amount of wrong by working really hard to understand the right.
If you're wrong in values it'll probably still work for a while until it suddenly doesn't for rather mysterious reasons. This can be way down the line, undetected for a long time if not forever. Thus, the pain of being wrong is potentially infinite as well.
So, programming in types is no easier. It's probably even harder today since so few people do it. But the consequences are amazingly different.
And yeah, with Conor's work its "come for the puns, stay for the mind blowing computer science"
Well, I think Edwin Brady showed a couple of C++-template-errmsg-like-things during a couple of his talks, but having actually programmed semi-advanced C++-template things I think I can agree on the general thrust that type-level problems are in some sense "better problems to have".
Btw, thanks for the exchange. (This is getting too off-topic, so I'll leave it at that.)
Encoding only valid states in subareas of code can be done within C++ without extravagant constructs. Ie. instead of passing around a Car with a Car::isDriving member implement a DrivingCar class and use that where this state of car matters. It's not as neat as ADT:s in ML but provide the same Lego-block static composability with minimum amount of moving parts.
I would not use pattern matching as such in C++.
Is there a reason this is only possible in Haskell, or does Haskell just make it super convenient / idiomatic?
I had a Scala system (build on Scalaz, which is a library providing Haskell for Scala), and one of our core types was DBTransaction[_] (a monad). A developer (a skeptic of the type system) was complaining to me about all the excess work he needed to go through, how he couldn't get properly construct a LazyStream[Foo] as a result of this.
He wanted to construct a DBTransaction[LazyStream[Foo]], call runTransaction on it, and get the LazyStream[Foo] out. Then he was going to call f(lazyStream). The compiler just wouldn't allow this, so his "workaround" was to instead call lazyStream.map(f).
Turns out this workaround prevented a runtime error. If he did get his LazyStream[Foo] out, generating the next element in the stream would have called resultSet.next() after closing the connection.
This sort of thing happened quite often. People would complain that the type system made it harder for them to do what they wanted. They'd ask the FP "guru" types how to fix it and the "guru" would point out that what they wanted to do was fundamentally unsafe.
My main question is the extent to which this is possible in more conventional languages.
C's language of types is incredibly primitive. Haskell's is quite nice. Agda/Idris/Coq's type language is technically equivalent to its value language so you can encode incredible things.
It turns out that due to people's general desire for compilation to always terminate that the type language behaves quite different from the value language. It also turns out that the type language operates differently because we're more interested in logical constraints than actual evaluation.
The major thing that the above change is that you no longer have the "it's always a Turing complete language" excuse. Type languages can actually significantly and meaningfully differ in power.
So it's meaningful to say that there are constraints that can be encoded statically in Haskell but cannot in C (no matter how you try). And it's also true that Coq can encode constraints that cannot be encoded in Haskell (though Haskell keeps making its type language stronger!).
First, "Turing complete" means that you can compute anything anyone else can compute. It doesn't necessarily mean you can do it with a reasonable encoding, or do with it what you need to do with it. At the boundary between systems, encoding matters quite a lot!
Second, it's certainly true that there are constraints you can express in Haskell and not in C, but I was surprised by some of the things I could enforce in C with a little creativity.
And, yeah... even a type system as primitive as C can catch interesting invariants. This is an important counterpoint to the general idea that "types never say anything interesting".
Certainly. I had every confidence you understood that. I just wanted to be sure we avoided strengthening the "Turing complete means it can do anything any other language can" misconception.
If I understand you correctly, if the type system behaves the same as the value system, then it is possible for the compilation to never terminate. Do I have that right?
" I've been trying to get my mind around this kind of stuff for maybe a year. And I have to say that monads don't look like the solution to any of the problems that I actually face or have ever faced, in a thirty-year career." - https://news.ycombinator.com/item?id=8815973
You might be interested in this link:
http://haskellrescue.blogspot.com/2011/03/cooking-delicious-...
If you respond quickly enough and I can delete this, I will ;)
Anyway, this was quite an enlightening comment for me: Agda/Idris/Coq's type language is technically equivalent to its value language.
Given a sufficiently interesting type language, could we statically type the problem I posed in another comment here
https://news.ycombinator.com/item?id=8966065
?
To encode what you're looking for requires type-level natural numbers and a reasonable notion of type-level equality. These are fairly non-trivial. You can encode this in Haskell, but type leve" equality is a bit hard to work with so you may suffer some pains (I know, I've done it several times!). Agfa and Idris would be where I would look to see this sort of thing materialize.
About your example, it's not idiomatic Haskell. If you try to code the same exact algithm in Haskell, you'll have the same exact problem (ghc has a warning for it); if you recode it in fmap or list pattern matching that are idiomatic to Haskell, you'll avoid the problem.
There are also some things that I'm not sure are reasonable at all in something like Java/C++ without writing a lot of code. For example: https://www.chrisstucchio.com/blog/2014/type_safe_vector_add...
Java is in an interesting place in that its type system is rudimentary but not unpowerful. C is a more useful didactic target---there really do exist invariants which can be encoded in Haskell types but could never be encoded in C types!
Another huge target is parametricity. You can write Java code which is "maybe sort of parametric" but it really isn't and subsequently you can never trust it because of the existence of things like global reference equality and hash codes (in the least).
Finally, there are expressivity concerns. Java cannot encode as many things in its type language as something like Agda (to make a clear comparison). You can simply note that Java's type equality is nowhere nearly as developed as Agda's!
As an example of using Java to indicate a fairly non-trivial invariant and comparing that implementation to Scala, Haskell, and C# consider Tony Morris' challenge
http://tonymorris.github.io/blog/posts/understanding-practic...
x = r_[:n].reshape((3, -1, n/15))[:, :2].sum(axis=-1)
a compiler could figure out that the shape of x is (3, 2) and allow y = x + randn(m, 1, 2)
while forbidding z = y - r_[:7]
With NumPy you have to wait for a runtime error, and only if the shapes can't be broadcast. We're not even talking correct use of dimensions, etc.I suppose this may have been tackled in Haskell in the Repa library, but I'd need to read papers like
http://benl.ouroborus.net/papers/repa/repa-icfp2010.pdf
to know. Hence my question if we could lift this into the type system in a conventional language, but I don't think it's possible in a general way.
Just like regular old code helps you manage the relationships between an input file and an output file, the type system helps you manage the relationship between libraries, or sets of functionality in your code. I don't care what type of data you pull from the database, but that type must agree with the type of matrix you're constructing. The parser may return a syntactically correct tree, or an error. One use of the type system is to ensure that all possible error conditions are handled in a meaningful way.
You can do this in java, but haskell's type system is a bit more expressive, so it's easier to enforce higher level constraints.
Another way to look at it, the type system is like the algebra axioms you want your system to follow. if equality is reflexive, a == b, then also b == a. At that level we don't care if a is 5 or "hello" or @TcpConnection(0x1342341a).
It is substantially possible in more conventional languages, however the conventional languages have holes in them which can not be filled in by libraries.
For instance, a bog-standard approach in any OO language is to hide the raw constructor and give only mediated access via some other class method (or local equivalent construct). This can allow you to easily enforce constraints like "A CreditCardNumber either had its parity validated OR does not exist". If you then put methods on an object that allow you to only manipulate the object in certain ways that maintain the constraints, there will exist no (direct) way to violate the basic constraints of the object.
This is reasonably powerful, and mastery of this technique is something that I would consider to be core to considering yourself at least a mid-tier professional developer.
However, there are many constraints you can not enforce in conventional languages. You can not enforce via type whether or not a given call will do IO or access global variables in unexpected manners. You can not enforce via type that a given method will only be called in a certain context (key in things like transactional memory, where you'd better be doing your STM things inside an actual transaction or the whole thing breaks down). You can not enforce whether an object will or will not be shared across thread boundaries. And so on, for a wide variety of additional guarantees that can be provided by a stronger type system. In the exciting-but-experimental world of dependent typing, you can enforce at the type system that a number is even or odd and stuff like that.
There are many different additional constraints being explored right now across a wide variety of languages, and while functional languages are leading the way, and there are some solid reasons for that, it isn't just functional languages that can use this... for instance, see Rust, which isn't functional at all in the modern sense but can still guarantee some of the things I said above.
(Rust, for instance, bring a question to the fore that I've been interested in for a while, but haven't had a major language to check it with: Is the important thing about functional programming immutability, or is it controlling mutation carefully? If in practice the latter is really what's important, than it is possible to see a set of "immutable" languages and see them successfully control mutation but accidentally attribute that to the "immutability", because that's the mechanism we happened to be using to accomplish the mutation control. I've already previously explained why I believe Erlang definitely had this problem: https://news.ycombinator.com/item?id=7744109 but with Rust we can explore whether Haskell has the right of the argument, or if Rust-style mutation control will turn out in practice to be sufficient. But it will be years before we can even start forming a decent answer... Rust needs some large scale programs and a body of people with experience writing large-scale Rust programs before we can even start forming a solid answer.)
#include <math.h>
double sine(double x){
reformat_hard_drive();
return sin(x);
}
which can be easily translated to Haskell sine x = do
reformat_hard_drive
return (sin x)
So we can write the same stupid function in both languages. The bit that's specific to Haskell, as opposed to just any typed language, is that sine and sin have different types. sin is (Double -> Double) while sine is (Double -> IO Double), so swapping in sine for sin causes the code to fail to compile. Comparatively, you can drop in a random sine anywhere in your C code and the compiler will happily chug right along. While I've seen ways of implementing various invariant catching techniques like the Maybe type in C, I haven't seen anything that would catch the sine function.Now, as I said, this is a toy example. The real solution would be to fire whoever wrote the sine function. However, in larger systems, it can be translated into invariants such as declaring that a function cannot access the database or send packets on the network.
I agree this is important. I have just started to move a project to Java from Python and see that immutability and purity are attainable for certain parts of the system but appear to cost a lot (leaning hard on use of interfaces, for example) in terms of readability.
I don't envision FP or contract based programming in enterprise offshore code.
I think FP (and contract based programming) would do a much better job than Java for varying qualities of programmers on very large projects.
Types pay off the most on large systems. Architectural requirements captured formally.
This more than ANYTHING else is why I want to move enterprisey app code to Haskell. Having worked on numerous ginormous enterprisey systems -- which are usually doing pretty straightforward things, just at scale, and needing to be maintained by non-brilliant developers -- I can say pretty securely that north of 95% of the invariants could be lifted into the type system, making run-time errors a thing of the past.
Also, in most frameworky big systems, you WANT to stop devs from "just doing IO" or pretty much doing anything without a strong contract around it. Monad stacks do wonders for circumscribing your computational context in an app.
I wonder why they rewrote Aeson though ... perhaps before it was mature? Aeson's pretty awesome.