Discreet and not discrete.

Как посчитать количество сравнений?

Реализация в лоб, подсказанная мной, всегда печатает 1

Вот код, куда я добавил работающие функции myCmp3 и get_val2 (и в main тоже кое-что добавил в самый конец):

import List
import Data.IORef
import System.IO.Unsafe

myCmp :: Int -> Int -> Ordering
myCmp x y  
    | x < y = GT
    | x == y = EQ
    | x > y = LT
    
{-# NOINLINE cmpCountRef #-}
cmpCountRef :: IORef Int
cmpCountRef = unsafePerformIO $ newIORef 0

anotherCmp :: a -> a
anotherCmp x = unsafePerformIO $ do
    c <- readIORef cmpCountRef
    writeIORef cmpCountRef (c+1)
    return x

myCmp2 :: Int -> Int -> Ordering    
myCmp2 = (anotherCmp $ myCmp)

myCmp3 :: Int -> Int -> Ordering    
myCmp3 a b = anotherCmp $ myCmp a b
    
get_val = unsafePerformIO $ do
    c <- readIORef cmpCountRef
    return c
    
get_val2 () = unsafePerformIO $ do
    c <- readIORef cmpCountRef
    return c
    
main :: IO()
main = do
    print (sortBy myCmp2 [1, 9, 2, 8, 3, 7, 4, 6, 5])
    print (myCmp2 1 9)
    print (myCmp2 9 1)
    print (get_val)

    print (sortBy myCmp3 [1, 9, 2, 8, 3, 7, 4, 6, 5])
    print (myCmp2 1 9)
    print (myCmp2 9 1)
    print (get_val2 ())

myCmp2 вычисляет константу-функцию и запоминает ее. Ну, и получается, что сравнение вызвано всего один раз, хотя, на самом деле, вызвано не сравнение, а... ну, скажем, вычисление указателя на функцию сравнения.

То же и с get_val.

Обе этих функции представляют собой CAF, constant applicative form. С помощью CAF можно запоминать результаты, это очень удобно. Но в данном случае они мешаются.

Что я и исправил в myCmp3 - теперь мы подсчитываем количество вычислений myCmp a b, что правильно, - и get_val2, которой передается незначащий аргумент, превращающий ее в функцию.

Еще надо упомянуть про прагму NOINLINE. Если cmpCountRef будет подставлена в разные выражения, то и результатом вычисления копий ее тела будут разные ссылки, и в одном месте мы получим ссылку на область памяти 1, в другом - на область памяти 2. get_val же может получить ссылку на область памяти 3. А нам надо, чтобы у всех ссылки были одинаковые, что означает обращение к одной версии cmpCountRef. Что означает запрет на подстановку, NOINLINE.

PS
Надо собраться с силами и решить-таки Ванину задачку.