News for hackers. Stuff that matters.
Re:Shen more strongly typed than Haskell? by skybrian on Tuesday September 09, 2014 @01:24AM (#8288865)
Haskell and similar languages are pretty hard to read for the beginners, so let me give some background:

As I understand it, the idea behind dependent typing is to safely separate a runtime check from the code that relies on the check. A runtime check can be done early in the dataflow and only done once (or at compile time for a constant), rather than repeatedly re-checked each time a function uses a value, and the compiler proves this is safe. For this to work, we must encode what we've proven (for example, the length of a list) into the return type at the time we do the runtime check. (Or for a constant, the compiler can calculate the type and we can remove the runtime check altogether.)

A very simple sort of check is just to make a NonEmptyList type and ensure that it can only be constructed if the list is non-empty. Everything downstream can rely on this with no runtime check at all. But I'm not sure this even counts; it seems like you need to encode more than one bit of data to make it a dependent type.

A more interesting example might be an unzip function that returns two lists that are proven to be the same length. In a regular programming language, the unzip function could return an EqualLenghtListPair type and then you could pass both lists around together, never having to check if their lengths are equal again. But the number of special-purpose types you need gets awkward fast so this isn't really practical without language support.

Re:Shen more strongly typed than Haskell? by tel on Tuesday September 09, 2014 @02:06AM (#8288955)
That's not really dependent typing. All of your examples are attainable without dependent types.

    data NEL a = NEL a [a]

    nel :: [a] -> Maybe (NEL a)
    nel []     = Nothing
    nel (a:as) = Just (NEL a as)

    data EqLen a b = EqLen [a] [b]
    
    unzip :: [(a,b)] -> EqLen a b
    unzip []          = EqLen [] []
    unzip [(a, b):rs] =
      let EqLen as     bs     = unzip rs
      in  EqLen (a:as) (b:bs)
A dependently typed language can of course do these things (the most popular of them are strict supersets of HM languages after all) but generally they would use dependent types to construct richer and more flexible typing invariants.
Re:Shen more strongly typed than Haskell? by skybrian on Tuesday September 09, 2014 @02:37AM (#8289003)
Well sure, that was my point. It seems like, even without dependent types, you could do a runtime check to prove anything you like in a type's constructor, and then other code can rely on it being true. But that doesn't mean it's practical to introduce a new type for every possible assertion, nor is the compiler assisting you very much with your proof.
Re:Shen more strongly typed than Haskell? by tel on Tuesday September 09, 2014 @09:46AM (#8290072)
It's obviously a tradeoff, but dependent types can make the space of these assertion types more rich and also ensure that they are true by construction.