но вот похоже, ReaderT World [] x и Reader World [x] это чуть-чуть разные вещи 8)

ага, одолел

mapReaderT (f . runIdentity) g

Я правильно рассуждаю, что если map определяется вот так:

map _ [] = []
map f (x:xs) = (f x):(map f xs)

то это не является хвостовой рекурсией, т.к. после вычисления (map f xs) еще нужно к нему приставить (f x) ?

да, не является, и поэтому это эффективно работает

то есть накапливает thunk-и по мере необходимости?

получается ли что хвостовая рекурсия всегда строгая?

наоборот, thunk-и не накапливаются, хранится только один thunk для списка по мере потребления

то есть в любой момент времени у нас может быть 0 thunk-ов если список вычислен, или 1 thunk, в котором конструктор списка какой-то, который еще никто не потребил

ну и для элементов той части списка что уже потребилась, тоже по thunk-у офк

хвостовая рекурсия не строгая, он просто не матчится с ленивостью особо,

чтобы потребить первый элемент map f xs достаточно только один шаг map-а сделать

а с хвостовой рекурсией нужно было полностью весь список обойти, чтобы первый элемент получить, и скок там thunk-ов накопилось бы страшно представить

да, получается хвостовую рекурсию почти всегда лучше делать строгой

Получается что для хвостовой нужно иметь весь список чтобы к нему приставить голову, что убивает ленивость, верно?

в хвостовом решении список в конце пришлось бы еще развернуть

map f xs = go [] xs where
 go result [] = reverse result
 go result (x:xs) = go (f x:result) xs

а для потребеления первого элемента лениво развернутного списка нужно весь список, чтобы его развернуть

Сложно к этому привыкнуть, так как обычно слышишь что хвостовая рекурсия - это оптимизация. Хорошо, тогда как решить стоит ли прибегать к хвостовым решениям или нет? Ну кроме ситуаций когда ты написал, увидел что работает медленно, попробовал переписать и помогло

очень просто. Функции которые структуру, которую можно постепенно потреблять, а не сразу - без хвостовой.

так например map генерирует вложенно элементы f a : (f b : (fc : ...)), поэтому тут лучше без хвостовой рекурсии

а когда гененируется значение, которое можно потребить только целиком (число, рекорд со строгими полями), то хвостовая и строгая функция

хороший пример - сумма списка чисел

если мы складываем список интов, то лучше делать хвостовой строгий фолд (foldl' то есть). Потому что по итогу нужно потребить результат целиком за раз

а вот если мы определим свой тип натуральных чисел + сложение + сравнение

data Nat = Zero | Succ Zero

(+) :: Nat -> Nat -> Nat
(+) Zero b = b
(+) (Succ a) b = Succ (plus a b)

(<=) :: Nat -> Nat -> Bool
Zero <= b = True
a <= Zero = False
Succ a <= Succ b = a <= b

то тут сложение генерирует значение, которое не обязательно потреблять целиком. Например, чтобы сравнить, что какое-то число x (которое предположим 10^6) меньше чем 100, достаточно только 100 итераций <=, поэтому если мы это число x считаем как сумму списка из 10^6 единиц, то достаточно потребить только 100 элементов списка фолдом, поэтому лучше подойдет ленивый не хвосторекурсивный foldr

таким образом можно и бесконечность описать, и тоже вполне успешно сравнивать ее с другими небесконечными числами

хм, получается даже так:
- строгое значение, которое нужно целиком потребить - строгая хвосторекурсивная функция
- ленивое значение, которое можно потребить постепенно - ленивая нехвосторекурсивная функция

data Nat = Zero | Succ Nat?

Ну 1 будет Succ Zero, 2 это  Succ $ Succ Zero и так далее.

Просто хочу убедиться что я правильно понял и там ачипятка