[qaisjp]

That's what my university did.

First semester was Haskell and Logic (truth tables, state machines), and some other stuff

Second semester was Java, and some other stuff

[karmakaze]

Were there many that seemed to have more difficulty with this introduction than if they were shown a procedural language, that you noticed?

My hunch is that to complete beginners a declarative approach is simpler than a 'play computer' mental simulation to coding. We shouldn't be initially shown what's effectively a Turing machine and save that for a later Theory of Computation or intro to procedural languages.