News for hackers. Stuff that matters.
Re:Lisp and Haskell (2015) by sullyj3 on Thursday October 08, 2020 @03:13AM (#24716685)
Type systems can encode proofs of properties that you want your data to have. For example, suppose you want to write a function that returns the first element of a list.

  head :: [a] -> a
This is the type of a function "head" that takes a list of values of some arbitrary type a, and returns an a.

if you feed this function an empty list, what will it do? You can reason from the type signature that the only thing it possibly can do is crash, since there's no way to produce a value of type a without knowing what a is in advance.

  head (h:_rest) = h
  head [] = error "Our function is badly behaved!"
To ensure that our function never crashes, we can encode the fact that our list is nonempty in a datatype.

  data Nonempty a = Nonempty a [a]
Ie, a nonempty list must contain a value of type a, and a (possible empty) list of as. Then instead of writing a function that crashes when it receives a nonempty list, we can write a function on nonempty lists that never crashes

  head :: Nonempty a -> a
  head (Nonempty x _rest) = x
What I'm getting at is that, yes, this is just the "shape" of our data. But you can encode more interesting and valuable properties in that shape than might be apparent at first. There are many other interesting examples of using types to ensure that properties that we want to hold for our values, do in fact hold.

Edit: I should probably add that "If it compiles it works" is absolutely not always true. It's more of a community in-joke than an actual belief. But it does turn out to be true surprisingly frequently.

Re:Lisp and Haskell (2015) by neolog on Thursday October 08, 2020 @03:15AM (#24716694)
Sure, you can encode various properties in some languages, but it's not that common to actually do so.
Re:Lisp and Haskell (2015) by sullyj3 on Thursday October 08, 2020 @03:20AM (#24716721)
In Haskell, it's both common and idiomatic. There's always a tradeoff between the usefulness of having static guarantees, and the complexity of the type system features that enable those guarantees. In some cases it's more trouble than it's worth to enforce certain static properties - you have to weigh the costs and benefits on a case by case basis. But it's nice to have the option, and Haskellers make use of it frequently.
Re:Lisp and Haskell (2015) by tsimionescu on Thursday October 08, 2020 @04:05AM (#24716990)
How many functions have you seen, in Haskell, that take Nonempty a versus taking [a]? There are reasons why this type of pattern doesn't scale well, and the Haskell designers knew it. Similarly, if they had defined head [a] -> Optional a, that would have produced complications of its own.
Re:Lisp and Haskell (2015) by sullyj3 on Thursday October 08, 2020 @04:21AM (#24717080)
The general consensus in the community afaik, is that

  head :: [a] -> a
in Prelude was a mistake, and the default should be to return a Maybe/Optional. Beginners are generally advised to avoid head, and all other partial functions in the Prelude, such as tail and the indexing operator, wherever possible, and rely on pattern matching instead, which is generally sufficient and more idiomatic for the relevant use cases. I agree that having the option to use a partial function is useful, escape hatches are important, but it shouldn't be the go to.

Nonempty was just a simple example. You're right that it's not very commonly used (probably because it's not in Prelude), but the general culture of writing type safe interfaces and pushing guarantees to compile time %100 is a thing. A commonly used, more complicated example might be Servant, which is a web library which statically ensures your implementation meets an API spec.

Re:Lisp and Haskell (2015) by tsimionescu on Thursday October 08, 2020 @06:34AM (#24717806)
Well, since the Prelude was never changed to at least add an alternative headMaybe, perhaps it was not seen as a deep enough mistake.

Yes, I am aware that the Haskell community generally tries to push more guarantees to compile time, and that Haskell's ease of defining and using new types equivalent to existing ones but that signify some property helps a lot in this.

Still, there is some limit to this. For example, you have many libraries adding measurement units for Haskell, and many libraries doing linear algebra. But you won't find too many people doing linear algebra with measurement units, because the types of intermediate results explode too much (e.g. a type-safe unit-of-measurement matrix multiplication of 3x3 matrices has 18 type parameters, with complicated restrictions between them).

Re:Lisp and Haskell (2015) by sullyj3 on Thursday October 08, 2020 @07:10AM (#24717979)
Definitely don't disagree!
Re:Lisp and Haskell (2015) by marcosdumay on Thursday October 08, 2020 @03:13PM (#24722674)
> How many functions have you seen, in Haskell, that take Nonempty a versus taking [a]?

Most take Foldable or Traversable.

When it's relevant your functions can be specialized into Nonempty.

Re:Lisp and Haskell (2015) by nicusor on Thursday October 08, 2020 @05:38PM (#24724205)
We've been using this approach in Typescript. It's more palatable than Haskell since you can express an array that has at least one element as a variadic tuple `[T, ... T]`. Having the possibility to encode invariants in types is very useful, although it gets harder at times since TS chokes when you push it to its limits. Note that this happens in an old Meteor codebase that was completely JS a year and a half ago.
Re:Lisp and Haskell (2015) by tasuki on Thursday October 08, 2020 @06:29AM (#24717783)
What complications would it have produced? Eg Elm has `List.head : List a -> Maybe a` and it's just fine I think?
Re:Lisp and Haskell (2015) by sullyj3 on Thursday October 08, 2020 @07:48AM (#24718207)
In practice I've found that it leads to writing code that you know is unreachable, but you can't prove it to the compiler.
Re:Lisp and Haskell (2015) by tasuki on Thursday October 08, 2020 @09:13AM (#24718789)
If you know the list can't be empty, can't you prove that to the compiler by using a non-empty list type?
Re:Lisp and Haskell (2015) by sullyj3 on Thursday October 08, 2020 @09:52AM (#24719088)
Good point! last time I used elm i didn't know what a nonempty list was.
Re:Lisp and Haskell (2015) by curryst on Thursday October 08, 2020 @04:20AM (#24717074)
I find these generally worth it because you can surface those aspects up to the function signature. It would be a lot nicer to have a function signature that shows the limits than it is to have a failure and have to open the docs for the library to see what the limits are.

If the code is sound, it should have the same complexity anyways. I.e. putting a non-empty requirement in the function signature is just as complex as adequately handling an empty array in the code.

My personal struggle is that statically typed languages are annoying to prototype (I don't care if it segfaults on my laptop, I want to validate my idea). My struggle is prototyping in something that I can easily transition to a strictly typed version. I'm curious to try prototyping in Javascript and adding types when I move to production.

Re:Lisp and Haskell (2015) by agentultra on Thursday October 08, 2020 @09:24AM (#24718870)
I used to think Javascript was a great prototyping language. In fact I specifically practiced prototyping with it -- my github is littered with repo's for each of my prototypes -- I call them the Laundromat Demos. I would use the 70-80 minutes I had at the laundromat to write a prototype for a game in JS.

However I've tried something similar with Haskell. I think I prefer Haskell for prototyping these days. It turns out you can get a long way playing with the types. Often I spend more time prototyping the types and they guide me to the implementation which is often quite small.

It takes some training and work to get there but I think Haskell, for me, is a better prototyping language -- I don't have to deal with undefined, accidental prototype overloading, etc.

Re:Lisp and Haskell (2015) by ghostwriter on Thursday October 08, 2020 @11:19AM (#24719899)
+1, I'm impressed how far these prototypes can get you, especially if there's an extra layer of correctness on top of the existing Haskell type signatures. For instance, LiquidHaskell [1] can naturally shift you towards implementing most of the necessary validation and parsing logic as part of your work on precise type signatures.

[1] https://www.youtube.com/watch?v=zCJV0xNY06o

Re:Lisp and Haskell (2015) by tome on Thursday October 08, 2020 @11:44AM (#24720206)
Interesting correspondence between your comment and sfvisser's:

https://news.ycombinator.com/item?id=24716903

Re:Lisp and Haskell (2015) by heavenlyblue on Thursday October 08, 2020 @03:42AM (#24716848)
You don’t need Haskell to do this however.
Re:Lisp and Haskell (2015) by elbear on Thursday October 08, 2020 @05:43AM (#24717486)
You need a type system that is expressive enough to allow you to encode logic in the types. Of course, Haskell is not only language with such a type system: PureScript, F#, Rust, OCaml, Scala have similar features, although not all.
Re:Lisp and Haskell (2015) by jimbokun on Thursday October 08, 2020 @12:54PM (#24721059)
Shouldn't head return "Maybe a", since the head of an empty list would be "None"? (Not sure if I got the Haskell terminology correct.)
Re:Lisp and Haskell (2015) by rowanG077 on Thursday October 08, 2020 @03:14PM (#24722684)
In a better world it would. Currently it the head of an empty list crashes the program. Many people in the Haskell world are really salty about this but they don't want to break the API for it.
Re:Lisp and Haskell (2015) by iambrj on Thursday October 08, 2020 @05:35AM (#24717452)
For the curious, I suggest reading Philp Wadler's "Theorems for free!" which explains how to derive a theorem for a given type. Practically, this helps compilers make certain optimizations based on the theorems it derives from the types.
Re:Lisp and Haskell (2015) by Kednicma on Thursday October 08, 2020 @10:41AM (#24719477)