I found it strange when first learning Haskell that the language was never used in any of my classes, especially considering how much easier and more obvious it makes the implementation of fundamental data structures like trees and lists
It might make implementing some data structures easier, but not all -- for example, I don't really think Haskell would make implementing arraylists or hashmaps necessarily easier.
(Also: I think implementing trees and lists is relatively simple in languages like Java or Python. The hard part, IMO, isn't teaching students how to implement trees or lists: the hard part is showing them how to manipulate them in arbitrary ways while avoiding edge cases. That's going to be challenging whether you approach the problem imperatively or functionally.)
When building enterprise-scale systems, avoiding things like state mutation becomes critical.
But what if you want to implement something like a video game? Mutation is an integral part of programs like those. Of course, there are ways to restructure your code to avoid mutation, but most existing literature, tools, libraries, game engines, etc... related to gamedev don't take such an approach.
Or what if you want to go into embedded systems or security and end up needing to mess around with a lot of assembly or C? For better or for worse, you're going to end up spending a lot of time working with lower-level languages: functional languages won't necessarily end up being relevant to your work.
Or what if you're interested in scientific and mathematical computing? Again, I don't think functional languages are really widely-used here: languages like Python, R, Julia, C, or maybe even Matlab and Fortran are more ubiquitous for a variety of reasons.
Basically, a CS curriculum is supposed to prepare students to excel in a wide variety of backgrounds, not one specific area. For that reason, I don't know if it's necessarily correct to assume that all (or even most!) students will move into working on enterprise software and the like.
In particular, I think many "intro to CS" courses are targeted to be useful for people who may not necessarily want to move into computer science but still want to learn coding as a skill. In that case, you'd probably want to teach them a more mainstream language.
(You could also split up your "intro to CS" course into a "intro for non-majors" and "intro for majors", but that would introduce some overhead, both for students and teachers.)
But of course, none of what I said above directly pertains to the heart of your question. I'm making the argument that a school shouldn't teach only functional programming, which isn't what you're asking: why don't we start with functional programming first?
Here, I'm personally not convinced that Haskell-style languages that push for immutability and clear containment of side-effects are actually going to be approachable, or even useful, for absolute beginners.
More recently, there's been a trend to start incorporating actual hardware into intro classes -- using things like micro:bits, for example. Or to rephrase: a trend of finding ways of giving the student more interesting ways to mutate state: LEDs, stepper motors, electronic components, and so forth.
Contrast this with languages like Haskell: in order to do anything that interacts with the world, you need to start by explaining how the IO monad works (or find some convincing way of handwaving it all away).
While this isn't an insurmountable challenge, it is a potential stumbling block and is sort of annoying, especially if you're trying to ramp students up to doing interesting things as soon as possible. And the more you can improve potential stumbling blocks, the better.
A little more broadly, I think immutability and containment of side-effects can be very useful when working on large-scale programs, but they seem sort of gratuitous and unnecessary when working on smaller ones: it's challenging to demonstrate why they're useful, especially in intro when they have no context into what the alternative would look like.
(IMO this is also why many schools struggle with effectively teaching students how to use version control tools like git: even if you ask students to work in teams on a long-term project, you don't really need to use things like branches and can get away with just pushing directly to master.)
Basically, while I'm a fan of functional programming, it's hard for me to see how exactly you'd go about teaching it to beginners. I'm sure that if I were really pressed, I could figure something out, but it's non-obvious to me how I'd teach the material in a high-quality way and how I'd rearrange certain topics I think are essential.
(For example, many students struggle immensely with the notion of "indirection" -- basically, how to use things like references and pointers. But if we're using an immutable language, indirection suddenly isn't as relevant: a variable could be a reference to some data or a copy of said data: it makes no difference. In that case, how and where should I teach students about indirection?)
Taking all of the above into account, I think a more tractable alternative is to start with a language like Python (or maybe Java?) first, then move on to more challenging languages like C or Haskell second.