I did my algo1 class with Haskell (Hugs 98) and honestly it was great. It also "evens the playing field" a lot among people with previous coding experience vs. people getting their toes wet for the first time. A lot of that was having a very powerful REPL.
The problem is when you want to get into basic data structures. The learning curve for Haskell, if you want students to come up with their own implementations, steepens up a lot.
