I wonder how its expressiveness compares with other languages.

Just beginning learning Haskell and this is just marvelous. It's really like they say: Experienced Haskell programmers tend to write less code, not more.
How would I learn such things? Should I finally start to write a real application with a framework which forces me to learn stuff..? I'd really appreciate some recommendations, especially those with free resources, since I'm not in a position to spend a lot of money right now.

L M A O

How can it be deduced that sort x will be memoized?

A great lesson by example! I won't forget how to use mapM, not after this...

Agreed, I modified tests to check the Euclidean division property.

sort x will be cached.

I cannot see the failing string. This is driving me crazy!

Church Numeral had fold different than those of list.

There is arguably no good definition for toInteger, though it depends on what you expect it to do. It cannot be a (non-trivial) ring homomorphism, for instance.

For quotRem, you ought to at least test the Euclidean division property: that the norm of r is less than the norm of the divisor.

Thank you for pointing this out. No, there is a good definition. The test suite was incomplete. Just added a new test

Gaussian x 0 `mod` Gaussian y 0 == Gaussian (x `mod` y) 0 

The tests for the Integral instance don't really validate that it's a good definition. Probably because there arguably is no good definition.

The following passes:

instance Integral Gaussian where
  toInteger = const 1
  quotRem z w = (1,z-w)

I didn't hear about eta-conversion, I will study. About point-free I read again and again, but what I can't agree - someone says "Look, with points your code is more clear and nice", but in fact, it really leads to obfuscation.

You can think of it as partial application, at least with anagrams w, but the correct term is actually η-reduction.

add3 x = x + 3
       = (+) 3 x
-- eta-reduction:
add3'  = (+) 3
-- which is actually a partial application of (+)

add3'' x = add3' x
-- The eta-reduction yields: add3'' = add3'.
-- But that's not a partial application of add3'.
-- It is however, indirectly, a partial application of (+).

The Haskellwiki contains an article on pointfree, which might interest you. Note that while pointfree-style is sometimes succinct, it can also lead to obfuscation.