I've done a bit of functional programming too and don't get me wrong, I love the FP cultural victory of Java/C# etc. getting immensely useful functions like map, reduce, filter, lambdas and higher order functions. But if you are going to use purely immutable data structures you're going to make trade offs. In the kind of work that I do generating excess garbage or using extra memory can be unacceptable so I think I'd struggle with that but I can still apply a good % of FP principles with mutable structures of course.
If you read introductory functional programming material, you will agree they are full of h::t style pattern matching and default list types in ocaml, haskell and scala are simple linked lists (I sadly haven't tried Clojure yet). I'm open to the possibility of advanced patterns with other data structures overcoming some of these problems that I'm not very familiar with but that's what I mean with impedance mismatch, you will need to step away a bit from the clean elegant patterns of "everything is recursion+pattern matching on lists" of typical FP teaching.