Also, they seem to grasp recursion much better via Haskell than in Python or Java. I believe that's mostly because Haskell makes structural recursion real easy (ie recursion along the structure of your data type, eg like along a tree)---and once they are comfortable with the basic idea from that, other patterns of recursion are easier to understand.

Algebraic datatypes and pattern matching on them are a great benefit for that structural recursion.