There are claims that Scala&#39;s type system is Turing complete. My questions are:

1. Is there a formal proof for this?

2. How would a simple computation look like in the Scala type system?

3. Is this of any benefit to Scala - the language? Is this making Scala more &quot;powerful&quot; in some way compared languages without a Turing complete type system?

I guess this applies to languages and type systems in general.

The type system in Scala is Turing complete. Proof? Example? Benefits?

I have read that Scala&#39;s type system is weakened by Java interoperability and therefore cannot perform some of the same powers as Haskell&#39;s type system.  Is this true?  Is the weakness because of type erasure, or am I wrong in every way?  Is this difference the reason that Scala has no typeclasses?


Disadvantages of Scala type system versus Haskell?

I know that Java&#39;s type system is unsound (it fails to type check constructs that are semantically legal) and undecidable (it fails to type check some construct).

For instance, if you copy/paste the following snippet in a class and compile it, the compiler will crash with a `StackOverflowException` (how apt). This is undecidability.

    static class ListX&lt;T&gt; {}
    static class C&lt;P&gt; extends ListX&lt;ListX&lt;? super C&lt;C&lt;P&gt;&gt;&gt;&gt; {}
    ListX&lt;? super C&lt;Byte&gt;&gt; crash = new C&lt;Byte&gt;();

Java uses wildcards with type bounds, which are a form of use-site variance. C# on the other hand, uses declaration site variance annotation (with the `in` and `out` keywords). It is known that declaration-site variance is weaker than use-site variance (use-site variance can express everything declaration-site variance can, and more -- on the down side, it&#39;s much more verbose).

So my question is: Is C# type system sound and decidable? If not, why?

Is C# type system sound and decidable?

A [recent blog post on William Cook&#39;s Fusings](http://wcook.blogspot.com/) mentions:

&gt; The key point is that structures in Ensō are viewed holistically as graphs, not as individual values or traditional sums-and-products data structures.

What are the traditional sums-and-products data structures he is referring to?

What are &quot;sums-and-products&quot; data structures?

What is the difference when I write this?

    data Book = Book Int Int

versus

    newtype Book = Book (Int, Int) -- &quot;Book Int Int&quot; is syntactically invalid

Difference between `data` and `newtype` in Haskell

What are the advantages and limitations of dynamic type languages compared to static type languages?

**See also**: [whats with the love of dynamic languages][1] (a far more argumentative thread...)


  [1]: https://stackoverflow.com/questions/42934/whats-with-the-love-of-dynamic-languages

Dynamic type languages versus static type languages

I read through the Wikipedia article *[Existential types][1]*. I gathered that they&#39;re called existential types because of the existential operator (∃). I&#39;m not sure what the point of it is, though. What&#39;s the difference between 

    T = ∃X { X a; int f(X); }

and

    T = ∀x { X a; int f(X); }

?

  [1]: https://en.wikipedia.org/wiki/Type_system#Existential_types


What is an existential type?

I have seen several sources echo the opinion that &quot;Haskell is gradually becoming a dependently-typed language&quot;. The implication seems to be that with more and more language extensions, Haskell is drifting in that general direction, but isn&#39;t there yet.

There are basically two things I would like to know. The first is, quite simply, what does &quot;being a dependently-typed language&quot; actually _mean_? (Hopefully without being too technical about it.)

The second question is... what&#39;s the drawback? I mean, people know we&#39;re heading that way, so there must be some advantage to it. And yet, we&#39;re not there yet, so there must be some downside stopping people going all the way. I get the impression that the problem is a steep increase in complexity. But, not really understanding what dependent typing is, I don&#39;t know for sure.

What I _do_ know is that every time I start reading about a dependently-typed programming language, the text is utterly incomprehensible... Presumably that&#39;s the problem. (?)


Why not be dependently typed?

It seems that a `newtype` definition is just a `data` definition that obeys some restrictions (e.g., only one constructor), and that due to these restrictions the runtime system can handle `newtype`s more efficiently. And the handling of pattern matching for undefined values is slightly different. 

But suppose Haskell would only knew `data` definitions, no `newtype`s: couldn&#39;t the compiler find out for itself whether a given data definition obeys these restrictions, and automatically treat it more efficiently? 

I&#39;m sure I&#39;m missing out on something, there must be some deeper reason for this.

Why is there &quot;data&quot; and &quot;newtype&quot; in Haskell?

I see this code in this blog: [Type-Level Programming in Scala](http://apocalisp.wordpress.com/2010/06/08/type-level-programming-in-scala/):

    // define the abstract types and bounds
    trait Recurse {
      type Next &lt;: Recurse
      // this is the recursive function definition
      type X[R &lt;: Recurse] &lt;: Int
    }
    // implementation
    trait RecurseA extends Recurse {
      type Next = RecurseA
      // this is the implementation
      type X[R &lt;: Recurse] = R#X[R#Next]
    }
    object Recurse {
      // infinite loop
      type C = RecurseA#X[RecurseA]
    }

There is an operator `#` in the code `R#X[R#Next]` which I&#39;ve never seen. Since it&#39;s difficult to search it(ignored by search engines), who can tell me what does it mean?

What does the `#` operator mean in Scala?

I&#39;ve heard that Scala has path-dependent types. It&#39;s something to do with inner-classes but what does this actually mean and why do I care?

What is meant by Scala&#39;s path-dependent types?

Dependent method types, which used to be an experimental feature before, has now been [enabled by default in the trunk][1], and apparently this seems to have created [some excitement][2] in the Scala community. 

At first look, it&#39;s not immediately obvious what this could be useful for. Heiko Seeberger posted a simple example of dependent method types [here][3], which as can be seen in the comment there can easily be reproduced with type parameters on methods. So that wasn&#39;t a very compelling example. (I might be missing something obvious. Please correct me if so.)

What are some practical and useful examples of use cases for dependent method types where they are clearly advantageous over the alternatives? 

What interesting things can we do with them that weren&#39;t possible/easy before? 

What do they buy us over the existing type system features?

Also, are dependent method types analogous to or drawing inspiration from any features found in the type systems of other advanced typed languages such as Haskell, OCaml?


  [1]: https://lampsvn.epfl.ch/trac/scala/changeset/25859
  [2]: http://twitter.com/#!/milessabin/status/127160650249154560
  [3]: https://gist.github.com/1303276#comments

What are some compelling use cases for dependent method types?

**Given**:

    data Foo =
      FooString String
      …

    class Fooable a where --(is this a good way to name this?)
      toFoo :: a -&gt; Foo

I want to make `String` an instance of `Fooable`:

    instance Fooable String where
      toFoo = FooString

GHC then complains:

    Illegal instance declaration for `Fooable String&#39;
        (All instance types must be of the form (T t1 ... tn)
         where T is not a synonym.
         Use -XTypeSynonymInstances if you want to disable this.)
    In the instance declaration for `Fooable String&#39;

If instead I use `[Char]`:

    instance Fooable [Char] where
      toFoo = FooString

GHC complains:

    Illegal instance declaration for `Fooable [Char]&#39;
       (All instance types must be of the form (T a1 ... an)
        where a1 ... an are type *variables*,
        and each type variable appears at most once in the instance head.
        Use -XFlexibleInstances if you want to disable this.)
    In the instance declaration for `Fooable [Char]&#39;

**Question**:

* Why can I not make String and instance of a typeclass?
* GHC seems willing to let me get away with this if I add an extra flag. Is this a good idea?



Why can I not make String an instance of a typeclass?

I know `newtype` is more often compared to `data` in Haskell, but I&#39;m posing this comparison from more of a design point-of-view than as a technical problem.

In imperitive/OO languages, there is the anti-pattern &quot;[primitive obsession][1]&quot;, where the prolific use of primitive types reduces the type-safety of a program and introduces accidentally interchangeability of same-typed values, otherwise intended for different purposes. For example, many things can be a String, but it would be nice if a compiler could know, statically, which we mean to be a name and which we mean to be the city in an address.

So, how often then, do Haskell programmers employ `newtype` to give type distinctions to otherwise primitive values? The use of `type` introduces an alias and gives a program&#39;s readability clearer semantics, but doesn&#39;t prevent accidentally interchanges of values. As I learn haskell I notice that the type system is as powerful as any I have come across. Therefore, I would think this is a natural and common practice, but I haven&#39;t seen much or any discussion of the use of `newtype` in this light.

Of course a lot of programmers do things differently, but is this at all common in haskell?

  [1]: http://sourcemaking.com/refactoring/primitive-obsession

Haskell type vs. newtype with respect to type safety

The [Haskell Wiki](http://en.wikibooks.org/wiki/Haskell/Existentially_quantified_types#Explaining_the_term_existential) does a good job of explaining how to use existential types, but I don&#39;t quite grok the theory behind them.

Consider this example of an existential type:

    data S = forall a. Show a =&gt; S a      -- (1)

to define a type wrapper for things that we can convert to a `String`. The wiki mentions that what we *really* want to define is a type like

    data S = S (exists a. Show a =&gt; a)    -- (2)

i.e. a true &quot;existential&quot; type - loosely I think of this as saying &quot;the data constructor `S` takes any type for which a `Show` instance **exists** and wraps it&quot;. In fact, you could probably write a GADT as follows:

    data S where                          -- (3)
        S :: Show a =&gt; a -&gt; S

I haven&#39;t tried compiling that, but it seems as though it should work. To me, the GADT is obviously equivalent to the code (2) that we&#39;d like to write.

However, it&#39;s completely not obvious to me why (1) is equivalent to (2). Why does moving the data constructor to the outside turn the `forall` into an `exists`?

The closest thing I can think of are [De Morgan&#39;s Laws](http://en.wikipedia.org/wiki/De_Morgan&#39;s_laws#Extensions) in logic, where interchanging the order of a negation and a quantifier turns existential quantifiers into universal quantifiers, and vice-versa:

    &#172;(∀x. px) ⇔ ∃x. &#172;(px)

but data constructors seem to be a totally different beast to the negation operator.

What is the theory that lies behind the ability to define existential types using `forall` instead of the non-existent `exists`?

What&#39;s the theoretical basis for existential types?

[Hoogle][1] allows you to search many standard Haskell libraries by either function name, or by approximate type signature. I find it very useful. Is there anything like Hoogle for Scala? Search in [ScalaDoc 2][2] only finds types and packages by name.


  [1]: http://www.haskell.org/hoogle/
  [2]: http://www.scala-lang.org/archives/rc-api/index.html

Scala Hoogle equivalent?

When I was experimenting with Haskell kinds, and trying to get the kind of `-&gt;`, and this showed up:

    $ ghci
    ...
    Prelude&gt; :k (-&gt;)
    (-&gt;) :: ?? -&gt; ? -&gt; *
    Prelude&gt; 

Instead of the expected `* -&gt; * -&gt; *`.
What are the `??` and `?` things? Do they mean concrete types or &quot;kind variables&quot;? Or something else?


Haskell Weird Kinds: Kind of (-&gt;) is ?? -&gt; ? -&gt; *

I have heard of types being referred to as &quot;boxed&quot; in some languages. 

In Java, I have heard of &quot;autoboxing&quot;. What is this? Is it having wrapper classes for a type? How would my code change if I&#39;m working with boxed or unboxed types?

What does it mean to say a type is &quot;boxed&quot;?

How to explain Scala&#39;s type system to a Haskell expert?
What examples show Scala&#39;s advantages?

How to explain Haskell&#39;s type system to an advanced Scala practitioner?
What can be done in Haskell that can&#39;t be done in Scala?


What are the differences and similarities of Scala and Haskell type systems?

What is the difference between **static** and **dynamic** programming languages? I know that it is all about type systems, but I’m looking for more clear clarifications.

Difference between static and dynamic programming languages

It is well known that Haskell-style typeclasses and ML-style modules offer different mechanisms for specifying *interfaces*. They are (possibly) equivalent in power, but in practice each has their own benefits and drawbacks.

Since I&#39;m a bit of an inclusionist when it comes to language features, my question is this: What are the primary theoretical difficulties with adding ML-style modules to Haskell? I&#39;m interested in answers along the following lines:

* What existing type system features interact poorly with ML-style modules? (An example of poor interaction is GADT and functional dependencies, even though fundeps are technically equivalent to associated types!)

* What things have to be given up on the compiler end in order to compile ML-style modules?

* How do ML style modules interact with type inference?

Related reading:

* &lt;a href=&quot;http://existentialtype.wordpress.com/2011/04/16/modules-matter-most/&quot;&gt;Robert Harper’s post that provoked this question&lt;/a&gt;
* &lt;a href=&quot;http://www.reddit.com/r/haskell/comments/grq99/ml_modules_matter_most/&quot;&gt;Discussion on Haskell Reddit&lt;/a&gt;

What are the primary theoretical difficulties with adding ML-style modules to Haskell?

Correct me if I&#39;m wrong, but it seems like algebraic data types in Haskell are useful in many of the cases where you would use classes and inheritance in OO languages. But there is a big difference: once an algebraic data type is declared, it can not be extended elsewhere. It is &quot;closed&quot;. In OO, you can extend already defined classes. For example:

    data Maybe a = Nothing | Just a

There is no way that I can somehow add another option to this type later on without modifying this declaration. So what are the benefits of this system? It seems like the OO way would be much more extensible.

Why are Haskell algebraic data types &quot;closed&quot;?

I&#39;ve studied scala for several months, but still at the beginner level. Now I found I have huge trouble with functional programming and scala&#39;s type system. 

I tried finding some documents and blogs, but I can&#39;t understand most of them(especially type-system ones). So I&#39;m looking for some small and good scala projects that I can read the sources to learn.

Could you please recommend me some?

All Type Systems Solutions on Gang of Coders

Total of 23 Type Systems Solutions

The type system in Scala is Turing complete. Proof? Example? Benefits?

Disadvantages of Scala type system versus Haskell?

Is C# type system sound and decidable?

What are "sums-and-products" data structures?

Difference between `data` and `newtype` in Haskell

Dynamic type languages versus static type languages

What is an existential type?

Why not be dependently typed?

Why is there "data" and "newtype" in Haskell?

What does the `#` operator mean in Scala?

What is meant by Scala's path-dependent types?

What are some compelling use cases for dependent method types?

Why can I not make String an instance of a typeclass?

Haskell type vs. newtype with respect to type safety

What's the theoretical basis for existential types?

Scala Hoogle equivalent?

Haskell Weird Kinds: Kind of (->) is ?? -> ? -> *

What does it mean to say a type is "boxed"?

What are the differences and similarities of Scala and Haskell type systems?

Difference between static and dynamic programming languages

What are the primary theoretical difficulties with adding ML-style modules to Haskell?

Why are Haskell algebraic data types "closed"?

Small and good scala projects to learn scala -- especially functional programming and type system