J>1. Допустим мы имеем функцию f(arg), которая детерминирована, делает свою работу и делает её медленно. Мы хотим приделать кэш вызовов. Собственно вопрос, где хранить состояние — тот самый кэш?

Одно вычисление

x=f arg

будет вычислено не более, чем один раз. Это тебе гарантирует семантика языка с ленивым порядком вычислений.

Если нам нужен именно кэш, то два варианта: запихнуть все это дело в монаду состояния с отображением

Map ArgType ArgResult

или сделать отображения

fromInt :: Int -> ArgType

и

toInt :: ArgType -> Int

, сделать (бесконечный) список результатов

results = map (f . fromInt) [1..]

и выбирать из него путем

cachedResult arg = results !! toInt arg

.

Бесконечный список можно заменить на любую другую бесконечную структуру, это несложно.

J>2. Как возможно определить и вообще работать с явно недетерминированными функциями типа rand()?

Про rand тебе уже объяснили.

Добавлю, что rand с типом rand :: RndState -> (Int,RndState) может быть сконвертирован в бесконечный список псевдослучайных чисел типа Int, с которым работать достаточно удобно, например, обычной сверткой.

PS
Тех, кто говорят, что нет языков без состояния, не слушай. Они все еще не научились абстрактному мышлению.