Haskell GHC 9.0.1-alpha

Rust doesn’t have linear types, but rather affine types, and present quite different designs.

Talks that might be informative for the curious:

https://www.youtube.com/watch?v=t0mhvd3-60Y

https://www.youtube.com/watch?v=uxv62QQajx8

Your first link says that Rust puts linearity on the kinds (types of types, not types of data).

SPJ usually makes great introductions about new things being introduced to GHC. Here's one about linear types: https://www.youtube.com/watch?v=t0mhvd3-60Y

> How do people that don't have PhDs bridge the gap in their knowledge from what's commonly taught/used (OOP and it's design patterns) to thinking in terms of monads/monoids/functors/etc.

In my own experience, you just practice, and munch new knowledge bits by bits. The crucial point here is that you don't need to know _all_ of haskell to be productive using it.

So you learn the basics, start using monads without understanding the Monad abstraction (it's really not something you need to understand to use), and after a while it just clicks. And once you're confortable with this basic knowledge, you learn new things when you need them.

As a result, I (and many other paid haskellers) have a job writing haskell without having a PhD, without learning category theory, or without a deep math bagage.

>How do people that don't have PhDs bridge the gap in their knowledge from what's commonly taught/used (OOP and it's design patterns) to thinking in terms of monads/monoids/functors/etc. ?

I can just speak for myself. Started programming via vocational training (apprenticeship for the title 'computer science expert' in germany) about 4 years ago.

Learned programming with python, which I loved for the productivity it gave me, the whole superpower yadiya. Was assigned some webrelated tasks, so I got in touch with javascript.

My style in these languages was actually 'functional' without me knowing about functional programming - but only to some extent. Mutability, nonstatic typing etc.

So, wanting to become a better programmer, I googled things like "advanced python", which yielded things like decorators, generators and metaclasses. In some video about map, filter and reduce something in me clicked - I didn't want to hide attributes and state in classes and objects anymore. It's not modular, it's not atomic, it's not beautiful.

I came across Rich Hickeys talks [1] and immediately saw that I'm ...home. The paradigms just click with me, I can't imagine falling back to impurity and oop (unless it can't be avoided for whatever reasons). (I still don't write clojure though, for now I'm still enjoying playing around in python and haskell where I can (you may substitute python with js))

And, honestly - if you have the curiosity to learn Haskell, do you really need a phd? I've taught myself bits of maths in the last four years (higher mathematics - number theory (not tech related, just curiosity), graph theory, category theory etc), just driven by curiosity. That being said: If you'd ask me about these topics on the street, I wouldn't claim to be a mathematician, far from it. I just satisfied my curiosity.

I want to understand. Not some math or haskell in specific, but life, logic, control flow, systems theory... Having this urge, diving deeper into mathematical concepts once you need them doesn't feel like a burden. I don't even have my A-levels, so I'm probably as far from a phd as you'll find on HN, but that wouldn't stop me from exploring, from learning, from progress.

Sorry if that was too personal and too much text, I just felt like I'm in the rare position to be able to answer something in depth on HN :-)

[1] https://github.com/tallesl/Rich-Hickey-fanclub#talks

Some more links that I used:

Functor, aplicative, and monad:

https://typeslogicscats.gitlab.io/posts/functor-applicative-...

Category theory for programmers:

https://www.youtube.com/watch?v=I8LbkfSSR58&list=PLbgaMIhjbm...

Ironically SPJ doesn’t have a PhD. Basically this is more a question of interest and time investment and not whether you got a title.

> Are there are books/video lectures that explain linear types how they are useful in a programming language?

Just to throw out an example of how they are useful: loads of Ethereum contracts (e.g. every ERC20 variant) track a kind of private assets (tokens). A big class of bugs is double-spend or double-store of these assets, since any instance of that kind of behaviour completely invalidates the contract.

As it turns out, linear types[0] are just the tool to prevent those bugs.

[0]: https://github.com/flintlang/flint/blob/master/proposals/000...

When I was at the university this kind of stuff was 4th year material, hardly PhD level.

Just get a book like "ML for the Working Programmer", and go through it and its exercises.

https://www.cl.cam.ac.uk/~lp15/MLbook/

Then either follow up with SML books,

http://www.smlnj.org/doc/literature.html#books

Or jump nicely into Haskell with " Learn You a Haskell"

http://learnyouahaskell.com/

knowledge about haskell tends to be presented in a "first principles" fashion for whatever reason, which is unfortunate. It's not a very pedagogically sound method. I think it has to do with the systematic temperament of most haskell programmers. But motivation and example should really come first.

The important thing is to not be intimidated. You can really get away with just mimicing code:

  main = do x <- getLine
            putStrLn ("Hello, " ++ x)  

for quite a while before you find that you actually need a proper understanding of the underlying concepts of eg. what monads are and how they work. This is enough to get your classic beginner command line programs running. You can do useful stuff with a very basic understanding. And yet you see people trying to start with

  (>>=) :: m a -> (a -> m b) -> m b
  pure  :: a -> m a

as if that's supposed to be in any way meaningful or useful to a newcomer. The trick is to find the good tutorials that give examples for concepts first, and do a good job of demonstrating why abstracting those examples is a useful thing to do.

I don't find FP those concepts any harder to grok than GoF design patterns (in fact, I've never actually gone through the latter in depth; I just see them mentioned occasionally and have learned some via osmosis).

In fact, those particular concepts you list at the end (monad, monoid, functor) are particularly easy: they're just different ways to think about lists (which we can then generalise to other things). I think the main obstacle is terminology, which makes things feel unfamilar.

For example, two lists can be appended together: programmers do this all the time, so it's a very familar operation; hence it might be useful if we could take this intuition and apply it to other situations. One interesting fact about list append, which we often take for granted, is that nesting doesn't matter, e.g. these will always be the same (modulo runtime: the first traverses 'bar' twice, the second traverses 'foo' twice):

    foo.append(bar.append(baz))
    foo.append(bar).append(baz)

We can capture this idea of "combining where nesting doesn't matter" using an interface, e.g. an OOP programmer might write an 'Appendable' interface with an 'append' method. We can implement 'Appendable' for lists, but we can also implement it for other collections like arrays, sets, or even implementation-specific collections like some 'big data' library that distributes values over a cluster of machines.

An interesting thing happens if we try to implement 'Appendable' for key/value mappings: we have to deal with key collisions (the same key appearing in both mappings). One way to handle this is to always keep values from the first mapping; another way is to always keep values from the second mapping. There's also a third possibility: if the value type is also 'Appendable', we can 'append' the conflicting values together! So far, this seems like a neat little API to expose in a package or standard library.

However, there's nothing about this interface which is specific to collections! We can look through our standard programming toolkit for other things which happen to be 'Appendable' too (AKA "combined where nesting doesn't matter"). One obvious example is numbers: addition is a valid way to 'append' numbers, as are multiplication, 'max' and 'min'. This works well with the key/value example above, e.g. we might have a bunch of mappings which count occurrences of something; we can append those mappings together by adding conflicting counters, to get an overall count of all occurrences; if we instead map keys to the largest observed value of something, we can append those mappings by maxing conflicting values, to get the overall largest values; and so on, as a way to divide and conquer our problems.

Note that averaging is not a valid 'append' for numbers since nesting matters, e.g.

      mean(mean(1, 3), 4)
    = mean(2         , 4)
    = 3

      mean(1, mean(3, 4))
    = mean(1, 3.5)
    = 2.25

However, if we keep a pair of total/count, they can be 'appended' by adding separately (and not reducing), e.g.

      mean(mean(1/1, 3/1), 4/1)
    = mean(4/2           , 4/1)
    = 8/3

      mean(1/1, mean(3/1, 4/1))
    = mean(1/1, 7/2)
    = 8/3

The name 'append' doesn't quite capture what's going on here, but it makes sense if we squint a little.

Another form of 'Appendable' value is "optional" or "erroneous" results (e.g. Maybe<T>, Option<T>, Try<T>, Either<Error, T>, ParseResult<T>, etc.). To 'append' two such values together we check the first one to see if it succeeded: if so we return it, otherwise we return the second. (Note that this faces the same ambiguity as for key/value mappings: we could begin by checking the second value instead; or, if the results are themselves 'Appendable', we could 'append' them together iff both were successful!).

In this case it looks like the name 'append' is misleading, since we're actually performing error handling/recovery! This might seem weird: in both OOP and FP we're meant to program to interfaces rather than implementations, but in this case generic code like 'foo.append(bar)' might mean "append the contents of bar to the end of foo's contents", or "add the numbers foo and bar", or "if foo failed try recovering with bar instead". Those seem to be very different things, so what's going on? Well, we can think about it from two different perspectives:

- An "optional" or "erroneous" type is a form of collection: it either contains a single value (a successful result), or no values (an error occurred). They're like lists with at most one element (perhaps with some error information in the empty case). The error-handling behaviour of 'try the first value then the second' is exactly the same as 'append two lists-with-at-most-one-element' (if the first list has an element we use that, otherwise we look in the second list).

- Looking at it the other way around, if a "list with at most one element" represents a potentially optional/erroneous result, then a "list" represents a value with any number of successful results (including zero)! From this perspective, when we append two lists together we create a value with all of the results of both; this is a form of error handling (once we've exhausted the results in the first list, we move on to the second)!

There's a nice paper called 'How to Replace Failure by a List of Successes' which explores this in more detail ( https://rkrishnan.org/files/wadler-1985.pdf ). In particular this 'error handling with multiple results' is actually backtracking search (as found in logic programming)! If we append the lists we get a depth-first search; interleaving gives us a breath-first search.

We seem to be straining to idea of "appending" a little, but it gets worse! Another standard programming construct which turns out to be 'Appendable' (AKA "combined where nesting doesn't matter") is functions (AKA procedures, methods, programs, etc.). In this case we use function composition, e.g. appending two functions like 'append(f, g)' gives us a new function like 'x => f(g(x))'. Functions (especially pure functions) are a bit like key/value mappings: calling a function on some argument is like looking up some key in a mapping; hene we can think of functions as "collections" of their return values. However, the implementation of 'append' for functions is very different to what we did for key/value mappings: it fits the interface, and is a common and useful operation, but is it really a good idea to think of this as 'appending'? We're appending the processing steps, but that requires thinking at a higher level of abstraction.

Since composing functions doesn't run them, we can actually compose programs written in a different language to the one we're using! As a very simple example, here's some Javascript which composes Python lambda functions (represented as strings):

    const append = function append(f, g) {
      return "lambda x: (" + f + ")((" + g + ")(x))";
    }

    console.log(append("lambda x: x+1", "lambda x: 2*x"));

    > "lambda x: (lambda x: x+1)((lambda x: 2*x)(x))"

The first lambda is an increment function, the second is a doubling function; 'appending' these gives a lambda which doubles its argument then increments it! This sort of thing is useful in metaprogramming, compiler implementations, etc., although it's generally done with ASTs rather than strings.

Hopefully it's clear that this very simple 'Appendable' interface crops up in all sorts of situations: I named it after the behaviour for lists, but it turns out to describe many more things where my terminology doesn't quite make sense.

Functional programmers use this interface a lot, although they call it 'Semigroup' (a term inherited from algebra). I think that's a pretty awful name, but my "OOP-friendly" alternative also turned out to be pretty bad too (naming things is hard, after all!); hence we shouldn't be too worried about the names. It's much more helpful to grasp some origin for the idea (e.g. appending lists), then gradually work our way out into less familiar examples.

You asked about "monoids": that's the same as Semigroup (AKA 'Appendable'), except it also has an "empty" value which leaves things unchanged if we 'append' it. For example; appending an empty list/map/set/etc., adding zero, multiplying by one, averaging with 0/0, 'max'ing with -infinity, 'min'ing with +infinity, composing with the identity function 'x => x' (or "lambda x: x")

If we go down a similar rabbit hole as above, but for 'map(myFunction, myList)' rather than 'append(list1, list2)', we get a 'Mappable' interface; which FP programmers call 'Functor'. It turns out that functions are also 'Mappable', and their 'map' function is also function composition; I like to think of this from the "functions are collections of their return values" perspective.

If we do the same for list concatenation (i.e. combining a list-of-lists into a single list) we end up with a 'Collapsable' interface, which FP programmers call 'Monad'.

They must be used once and exactly once, no more or less.

I liked this paper:

http://www.cs.utexas.edu/~hunt/research/hash-cons/hash-cons-...

And previous discussion: https://news.ycombinator.com/item?id=20369522

Yes, it's useful for reasoning about resources (file handles, sockets, memory buffers) etc.

My understanding is that the current implementation is only groundwork for possible future performance benefits, since there are no changes to the runtime system or garbage collector, and that their current intended use is mostly for allowing library authors to encode safe session/resource handling in the type system. So, new libraries can make it a type error to fail to properly close a connection or release a shared resource.

Simon Peyton Jones talk: https://www.youtube.com/watch?v=t0mhvd3-60Y

Rust has affine types (can be used no more than once), but not linear types (must be used exactly once). Linear types would be a nice feature for rust, and there's been some discussion about how to add them, but as far as I know there hasn't been any real progress there.

Affine types in Rust are anything with move semantics; for example you can create a method that consumes itself like this:

    impl A { 
      fn use(&mut self) { 
        // takes a mutable reference to self, so it
        // can be used again later
      }

      fn consume(self) {
        // moves self into this function, which means
        // it cannot be used again
      }
    }

Idris2 has linear types. I don’t think it will come to Idris.

One of the best write-ups on the differences (at a level that is comprehensible to most programmers) is Linearity, Uniqueness, and Haskell by Edsko de Vries.

1 - http://edsko.net/2017/01/08/linearity-in-haskell/

> is Rust the motivating factor behind linear types cropping up lately?

Philip Wadler wrote "Linear Types Can Change the World!" while he was working on Haskell back in 1990. I vaguely remember there were some mentions of possibly adding it a year or two before Rust was publicly announced, but it seemed like it was going to be far off at the time. I wouldn't be surprised if Rust contributed to a lot of the interest in it - Simon Peyton Jones did specifically say that he had "Rust Envy" for shipping something similar to linear types in one of his talks.

Linear Types can Change the World!: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.31.5...

I am fairly well read on substructural type theories, if you could explain what you mean by ‘strictly superior’ then maybe I could formulate some points of interest, but as the question stands, I don’t think there is any justification for claiming that affine types are better than linear types.

Linear types let you ensure resource cleanup; files flushed/closed, memory freed, radiation-emitter disabled. That's why even in safe Rust code, it's possible to leak memory, and for the program to e.g. shut down without calling the "switch off the radiation emitter" destructor on a medical device.

From https://gitlab.haskell.org/ghc/ghc/-/wikis/linear-types :

"The centrepiece of our design is to avoid code duplication. Crucially, the same types can be used in linear and non-linear contexts. For example, the linear-base library uses the same types as base. So libraries developed with linear-base will be compatible with libraries developed with base."

From the looks of it this isn't done anyway, just a stepping stone to get to the final destination.

Just like value types, modules and concepts in other languages, sometime big bangs require incremental additions to the stable language instead of big bangs.

* So is it appropriate to say that in linear types a callee says "I will use this exactly once", and in uniqueness types a callee says "I need exclusive access to this"?

* Is there an obvious way to translate from one to the other?

* Rust's type system sounds a lot closer to uniqueness types than linear or affine types. So why do so many people in this thread say that Rust has affine types?

It seems inconsistent to claim both a) this proposal/implementation has bad ergonomics and doesn't solve real problems, and b) the library ecosystem will become irreparably fragmented as library authors rush to incorporate it or provide linear forks.

Surely if enough people are expending the effort to bring -XLinearTypes to a non-trivial portion of the extant Haskell universe, it is by definition both useful and at least somewhat ergonomic?

> this extension doesn't do what they want

It seems that you are the one wanting Linear types to be Uniqueness types instead.

> no one bothered working through all the ugly details like exception handling in the context of a real application.

Citation needed?

> it's absolutely going to make the library ecosystem permanently worse, as lots of packages will get linearity annotations added > Lots of forks will arise without them, for the people who don't want the hassle

How would the situation be different for Uniqueness types?

> I really don't believe this is ever going to be better than existing techniques.

The paper has examples of how it's better than existing method (such at the ST trick). Took me like an hour to read the entire thing months ago.

Strong objections weren't ignored - they just weren't especially compelling. And when pressed for an alternative, nobody could come close to something of the rigor of what was merged.

This entire comment is FUD and the fact that it's at the top of HN is such a PITA. Now I'm gonna have to hear even more people copy-paste argue against the extension instead of making real progress.

This isn't going to make the library ecosystem worse. Please just edit that statement of "fact" out of your comment for all our sakes.

That's all okay though. I'll go make some video games with type-safe manual memory management thanks to this extension :) that's the power of not complaining when things aren't as perfect as you can imagine them.