Dependently-typed programming refers to type-level programming where prior data types determine the types of subsequent values.
By doing type-checking computations, the dependently-typed programming style allows for more nuanced type definitions. For instance, instead of defining a type for "list of numbers", we might go further with the dependently-typed "list of numbers of size n" or "list of distinct strings".
For example, it is easy to implement sprintf in an untyped way, but this function is notoriously difficult to implement in a type-safe language because the return type depends on the value of the format string:
sprintf "%s" :: String -> String sprintf "%d" :: Int -> String
To do this in Haskell, we require dependently-typed programming. Let's explore a simplified example (refer to Fun with Types, Kiselyov et al, for more information). First, we create an embedded language for format strings:
data L -- literals e.g. "hello"
data V val -- values e.g. (V Int) or (V String)
-- F: format
data F t where
Lit :: String -> F L
Val :: (val -> String) -> F (V val)The GADT F unifies L and V into a type to express print formats. The Lit data constructor takes a string and returns the format for literal strings F L. The Val constructor takes a polymorphic "to string" function and returns the format for typed values F (V val).
Next, we create a type-family to generate the appropriate type signatures for our sprintf function:
type family SPrintf f type instance SPrintf L = String type instance SPrintf (V val) = val -> String
We can now write our generic sprintf function with the return types computed by the type function SPrintf:
sprintf :: F f -> SPrintf f sprintf (Lit str) = str sprintf (Val show') = x -> (show' x)
We can use this to print various types:
sprintf (Lit "hello") -- sprintf :: SPrintf (V Float) sprintf (Val (show::Float -> String)) 1.2 -- sprintf :: SPrintf (V String) sprintf (Val (show::String -> String)) "hello"
For Val values, sprintf returns a function of the appropriate type, while sprintf (Lit "hello") simply returns a string value. This is generic programming in the dependently-typed style.
Dependently-typed programming has been around even before Haskell and has evolved alongside it. Over time, both sides have started to influence each other (for example, GADTs are an import from that paradigm.)
There is still a clear line drawn between term-level and type-level in Haskell, or, as Conor McBride puts it, "the barrier represented by :: has not been broken".
However, with each new kind-level language extension, the line is getting more blurred. Leap by lurch, Haskell is reaching towards dependently-typed programming.
As we extend the language, inference typically suffers. We need to add more and more type signatures to annotate our code. Dependently-typed languages, on the other hand, are built on a foundation of strongly-typed and inferable type-level programming. But there are some benefits of accessing dependently-typed programming through Haskell, as described in Giving Haskell a Promotion, by Yorgey et al, in 2012:
"Full-spectrum dependently-typed languages like Coq or Agda are more expressive still. But these languages are in some ways too powerful: they have a high barrier to entry both for programmers and implementers. Instead, we start from the other end: we carefully extend a state-of-the-art functional programming language with features that appear in dependently-typed languages. Our primary audience is the community of Designers and Implementers of Typed Languages, to whom we offer a big increase in expressive power for a very modest cost in terms of intellectual and implementation complexity."
While the mainstream programming communities wrestle with marrying OOP and FP, the Haskell community is exploring the synthesis of FP and dependently-typed programming.