I realize that prolog is a language, but it's much harder to learn things when they are purely abstract. A good implementation and a good library go a long way.
I don't have a problem with non-mainstream languages. I like erlang.
I tried learning haskell, too. I didn't get hung up on monads; I ran into a wall when I found out there was no good way to use haskell as an embedded language or call a haskell library from something else without pulling in a big runtime (which interferes with non-trivial host applications). Correct me if I'm wrong.
It also has a bi-directional interface to Java, but Sicstus is unfortunately neither free nor cheap