> But I didn't find it much to fall back on when trying to
  > do something complicated and having a hard time thinking
  > about how to break down the problem without for loops
  > and case statements and value accumulators.

When I'm porting some stateful code to Haskell, I usually start by transcribing it as closely as possible. That means using for-loops, using stateful accumulators, and usually putting the whole thing in an IO. Once you've got a bit component compiled and working, you can start factoring out chunks into smaller, pure functions. It's the same as working out a big tangle in some string: keep working and the mess will just sort of evaporate.

Of course, the difficulty here varies wildly depending on how good the original code is. Most stateful code is pretty ugly (lots of mutation, lots of tangled side-effects), but a few developers are competent enough to write good code in any language.

  > Maybe it's more robust than I know, but it seems like
  > such a small piece of such a big language. Calling
  > Haskell imperative on account of that seems like
  > calling perl OO because you can kinda sorta do basic
  > OO stuff most of the time.

I think you're looking at the word "imperative", and assuming a lot of properties that simply aren't included. A language is not imperative or declarative; a language can support writing in imperative or declarative style, and some languages support certain styles better than others, but it's not like one is much better than the other.

  > And a stateful language accumulates progress in
  > changing values, while a functional language does so
  > by resolving expressions.

Every program progreses by changing values. The difference is scope; a stateful language progresses by applying a sequence of mutations to a single state. Every procedure is a sequence of mutations to that state. Haskell programmers (somewhat snarkily) call that state the World.

In functional programs, state is still accumulated, but in fragments. Each function has access only to what state it needs, and its contribution to the program's progress is restricted to its returned value. Only IO values have access to the World.

That last sentence means that Haskell is also a stateful language. It is, effectively, a superset of C.

  > So far so good, but I can't really decouple the
  > concepts. How would you break a problem down by time,
  > but track results through logical resolution? Isn't the
  > point of a step or instruction to leave something about
  > the state of the program changed--I mean, isn't it
  > inherently stateful?

The point of imperative programming isn't necessarily state, but dependency. Step 10 depends on the results of step 9, which depends on the results of step 8, and so on. It might be that no step actually requires access to the whole state -- only one little corner of it.

In well-designed programs written in stateful language, a great deal of effort is spent on how to separate state from dependency. In Haskell, the compiler handles it.

  > So how in the world would you make a declarative
  > program accumulate progress via state?

With parameters and the call tree, primarily.

That was . . . really enlightening.

Thank you for taking the time to educate me. I've found the Haskell community uncannily welcoming to newbies, and you seem to be continuing the tradition.

To complete the exercise (in no particular language),

Imperative and stateful:

   var factorialResult = 1;

   factorial(n) {

     if(n <= 1) {
       factorialResult = 1
     } else {
       factorial(n-1)
     }

     factorialResult = factorialResult * n
   }

Imperative and functional:

   factorial(n) = {

     var lastResult = 1

     if(n <= 1)
       lastResult = 1
     else
       lastResult =  factorial(n-1)

     return n * lastResult

   }

Declarative and stateful:

   var factorialResult = 1

   factorial(n) {
     if(n > 1)
       pointlessFunction(multiplyBy(n), factorial(n-1)) 
   }

   multiplyBy(n) {
     factorialResult *= n
   }

Declarative and functional:

   factorial(n) {

     if(n <= 1) 
        1

     else
        n * factorial(n-1)

   }

Everyone learns imperative and stateful. Some people also learn declarative and functional. Good programmers tend to do functional when working imperative. And declarative stateful is possible, but just plain silly.

No value judgement can be made between imperative and declarative; do what suits the problem. Sometimes you're following a recipe for cookies, and other times you're parsing XML.

Functional is better than stateful, but not in a competitive sense -- not like ipods are better than walkmans. More in a pragmatic sense -- more like laws are better than wars . . . when the law will solve your problem. Sometimes you really do need to talk to the world. For everything else, there's functional programming.