MonadFix экземпляр для []

Question

Экземпляр определяется как

instance MonadFix [] where
  mfix f = case fix (f . head) of
             []    -> []
             (x:_) -> x : mfix (tail . f)

Но я не могу понять интуитивное значение этого понятия в отношении [] Монада рассматривается как недетерминированные вычисления. В mfix f функция f не должен быть строгим в своем аргументе, поэтому он не может проверить аргумент. И согласно определению он также не может использовать аргумент где-либо в своем выводе, иначе в какой-то момент он ударит fix (f . head) и расходятся. Так есть ли смысл (или хороший пример) для mfix для списков, кроме mfix (const someList)?

Answer 1

Наверное, проще всего так сказать. Функции f для которого mfix f полностью определены те, для которых позвоночник f x не зависит от xпоэтому их можно записать в виде

f x = [f1 x, ..., fn x]

для некоторых n (возможно, бесконечность) и некоторые f1,..., fn, затем

mfix f = [fix f1, ..., fix fn]

(конечно, чтобы это действительно было полностью определено, каждый fix fi также должны быть определены).

---

mfix может рассматриваться как недетерминированный, давая вам фиксированную точку недетерминированной функции. Довольно серьезное ограничение заключается в том, что форма недетерминированных вычислений никак не может зависеть от входных данных. Кажется, нам нужно какое-то ограничение на вычисления, чтобы начать, но вы можете надеяться, что по крайней мере сможете условно уничтожить ветвь вычисления (скажем, если какое-то промежуточное вычисление отрицательно). Я всегда думал, что это можно использовать mfix таким образом, используя другую монаду недетерминизма, чья операция выбора не ассоциативна, но никогда не проработала детали.

Answer 2

Все fix варианты имеют проблему, если вы на самом деле используете их со строгой функцией, но это как правило, не проблема в реальном случае использования^†: a в основном всегда является типом функции, и любая лямбда уже в NF.

Итак, что касается конкретного использования... ну, вот, по крайней мере, кое-что сходящееся:

f :: (Int -> Int) -> [Int -> Int]

f f' = [\x -> if x>0 then f' (x-1) * i else 1 | i<-[0..]]

f в основном генерирует список степенных функций.

GHCi> take 20 $ mfix f <*> [1,2][0,0,1,1,2,4,3,9,4,16,5,25,6,36,7,49,8,64,9,81]

Что это на самом деле полезно для меня, я не уверен, но у него довольно интересное поведение.

Я только что заметил, что это плохой пример, так как на самом деле это эквивалентно одному fix (f . head), Хм...

---

^†_{Вы, кажется, совершенно правы: это проблема в случае}a -> [a] _{потому что нет очевидного способа сделать структуру списка зависимой от аргумента без строгости.}