Означает ли использование бесплатной монады в F # более высокое время запуска и ограниченные инструкции?

Question

Я читаю эту замечательную статью Марка Симанна.

В ней он дает простую демонстрацию использования свободной монады для моделирования взаимодействий с использованием чистых функций.

Я понимаю, что достаточно, чтобы написать такую ​​программу, и я могу оценить достоинства такого подхода.Однако есть один фрагмент кода, который заставляет меня задуматься о последствиях.

let rec bind f = function
    | Free instruction -> instruction |> mapI (bind f) |> Free
    | Pure x -> f x

Функция рекурсивная.

1. Учитывая, что это не хвостовая рекурсия, означает ли эточто количество инструкций, которые я включаю, ограничено пространством стека, потому что каждый раз, когда я добавляю инструкцию, она должна развернуть все, чтобы добавить ее?
2. Как и выше, означает ли это более высокое время запускапотому что каждая новая инструкция должна идти дальше вниз, чтобы быть добавленной?Это может быть незначительным, но не в этом вопрос;Я пытаюсь понять теорию, а не практичность.
3. Если ответ на поставленные выше вопросы - «Да», будет ли альтернативная реализация в духе (составьте список инструкций в том порядке, в котором вы хотите их получить)затем обработайте список в обратном порядке так, чтобы каждая инструкция была добавлена ​​в начало вашей программы, а не вглубь внизу) было бы предпочтительнее?

Возможно, я (вероятно) упустил нечто фундаментальноездесь это означает, что рекурсия никогда не должна заходить слишком далеко, пожалуйста, дайте мне знать.

Answer 1

Я думаю, что ответом на первые два вопроса является «это зависит» - есть некоторые накладные расходы, связанные со свободными монадами, и вы, конечно, можете столкнуться с переполнением стека, но вы всегда можете использовать реализацию, которая избегает этого, и если выделая ввод / вывод, тогда издержки, вероятно, не так уж и плохи.

Я думаю, что гораздо большая проблема со свободными монадами заключается в том, что они являются слишком сложной абстракцией.Они позволяют решить одну проблему (абстрагироваться от того, как вы выполняете код с большим количеством итераций), но за счет того, что вы делаете код очень сложным.Я думаю, что в большинстве случаев вы можете просто сохранить «функциональное ядро» в качестве хорошей тестируемой чистой части и «обязательную обертку» вокруг нее, достаточно простую, чтобы вам не нужно было ее тестировать и абстрагироваться от нее.

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

type Instruction = 
  | WriteLine of string
  | ReadLine of (string -> Instruction list)

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

let program = 
  [ yield WriteLine "Enter your name:"
    yield ReadLine (fun name ->
      [ if name <> "" then
          yield WriteLine ("Hello " + name) ] ) ]

Это говорит «Hello», но только когда вы вводите непустое имя, поэтому показывает, как инструкциизависит от имени, которое вы читаете.Код для запуска программы выглядит следующим образом:

let rec runProgram program = 
  match program with 
  | [] -> ()
  | WriteLine s :: rest ->
      Console.WriteLine s
      runProgram rest
  | ReadLine f :: rest ->
      let input = Console.ReadLine()
      runProgram (f input @ rest)    

Первые два случая хороши и полностью рекурсивны.Последний случай хвостовой рекурсии в runProgram, но он не хвостовой рекурсии при вызове f.Это должно быть хорошо, потому что f только генерирует инструкции и не вызывает runProgram.Он также использует медленный список добавления @, но вы могли бы исправить это, используя лучшую структуру данных (если это действительно оказалось проблемой).

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