Elaboration:
With advanced type systems you can prove that your code satisfies (or fails to satisfy) any property that you can encode as types. The more expressive the type system, the more properties you can encode, and the more kinds of claims you can prove.
But there will always be some properties that cannot be proved or that are too expensive to encode within a given type system. If you care about these properties, you'll have to find some other way of making sure they hold. So, even with advanced type systems, you'll end up writing tests.
The flip side is that there are many important properties that you cannot adequately test for (e.g., "my code is free of injection vulnerabilities"). If you're not using proofs to make sure that these properties hold, there's little reason to believe that they do hold, regardless of how much testing you do. So, even with lots of tests, you'll end up using types.
You need both.
If those fail at any point it drives you to either use a more permissive type or to just test some useful cases. Not infrequently, test cases can be upgraded into more powerful types.
It's one thing to name a few example inputs and outputs of a single function, it's another thing to think about how a single function interacts with itself (such as what's needed to write a quickcheck property like "for all strings, `reverse . reverse == id`"), it's yet another thing to think about how collections of related functions interact (like seeing some Category laws), and it's a whole set of further things to see all that thoroughly enough to encode it in a logic system.
My thought is that the general advantage of TDD is that you are thinking about your eventual implementation from the outside. You write tests in a different mindset based on expectations, rather than when you are implementing the production code where you are more concerned with the details of logic, etc. Unit tests also tend to be a bit more readable than the actual implementation logic, and so act as a nice form of documentation as a side-effect. In this way, test-first development provides a more gradual transition between a specification or design and the end implementation, which results in fewer missed requirements, allows for easy refactoring, etc.
This is of course only related to TDD however, not unit testing in general. Hence, it still irks me that many of my tests look so similar to the logic they are testing, and thus aren't really testing for correctness at all.
Like that you build your confidence layer by layer and with every set of tests you verify that you are still building on solid ground instead of quicksand.
That's why you test at the interface level, it allows you to swap out the implementation without having to re-work all the test code.
I'm not sure if you're in the same situation I was in, but let me tell you: My situation was an anti-pattern. All I was testing was that my code does what it does. I wasn't testing that my code was working.
Make sure you're not making the same mistake. If you are, a symptom would be that lots of tests fail when you're only refactoring.
The symptom of many tests failing during refactoring is something I'll be keeping in mind, however.
I watched a talk by Yaron Minksy the other day that also talked about the idea that you should "make illegal states unrepresentable" that was really good: http://vimeo.com/14313378 (he starts talking about that at around ~17:50)
First we create two differently typed tags for Red and Black.
data Red
data Black
Note this differs from something like data Color = Red | Black
in that Red and Black are distinct at the type level---the compiler will actually complain if one is used where the other ought to be.Now we state that Trees must have Black roots. This is done using a GADT (Generalized Algebraic Data Type) which allows us to build constructors of types which restrict some of the types.
data Tree a where
Tree :: Node Black n a -> Tree a
For instance, compare PoorTree which would let us make Trees with Red roots data PoorTree c n a = PoorTree (Node c n a)
It really does nothing more than wrap up a Node to hide it and change the interface (if you want).Now we need one last piece before digging in to the core. This is the existence of Type-level Naturals. The idea is that, like Red and Black, we introduce two new distinct types, one basic and one parametric.
data Zero = Zero
data Succ a = Succ a
which lets us write (very verbose) naturals like (Succ (Succ (Succ Zero))) == 3 and have the type reflect this exact value (Succ (Succ (Succ Zero))) :: (Succ (Succ (Succ Zero)))
(Note this is a little weird, since we can also form the value (Succ 'a' :: Succ Char) which doesn't make much sense. More powerful dependently typed features help here.)Now consider just a branch in the tree, we form that with a simple data type
data NodeH l r n a = NodeH (Node l n a) a (Node r n a)
which tracks the left and right colors in its type using the l and r type parameters. It also guarantees the constraint that both the left and right child trees have the same black-height. So, if (black3 :: Node Black (Succ Zero) Char) then (NodeH black3 'a' black3 :: NodeH Black Black (Succ Zero) Char). And if (black2 :: Node Black Zero Char) then (NodeH black3 'a' black2) is a compile time type error.So with all these pieces, we can encode the Red/Black criteria directly into our Nodes. Remember already that if we have a Tree it must have the first Node be Black. We can now construct new Nodes in three ways, each of these ways being constrained so as to enforce the balance rules.
data Node t n a where
-- If we construct a Node with Nil, it forms a leaf.
-- Not only are we not allowed to associate left and
-- right branches (we don't get to give it a NodeH type),
-- we're forced to set the numerical type parameter to Zero ~= 0.
Nil :: Node Black Zero a
-- If we construct a Node with BlackNode, we can pass a
-- subtree with the NodeH parameter, but the type of node we
-- get back is necessarily going to increase its height
-- since (Succ n) is like (n + 1).
BlackNode :: NodeH t0 t1 n a -> Node Black (Succ n) a
-- Or we can construct a Red node. In this case, our black-height
-- remains unchanged, but we can ONLY do so when we've got a NodeH
-- branch with two black subNodes.
RedNode :: NodeH Black Black n a -> Node Red n a
So, it's a type error to construct a tree in this format which doesn't obey the Red/Black balance rules. Any transformations you write on the tree will be rejected by the compiler if they break the rules. data Node = Nil | BlackNode | RedNode
but with the extra extra restrictions on the type variables.As weird as it is, I always recommend Agda/Coq for learning GADTs. It feels like overkill, but Haskell's DT stuff is really wonky, so it's nice to see GADTs expressed in a clean manner before trying them out in Haskell.
This is often conflated with type inference where the program code itself is analyzed in order to compute what type it "ought to be". Some combination of type checking and type inference is a powerful, fast, comprehensive tool for encoding how your program ought to behave alongside the program itself.