Как объединить монады состояний и продолжения в F #

Question

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

Однако код выглядит довольно уродливым - было бы неплохо использовать государственную монаду, чтобы нести текущую глубину, но государственная монада не является хвостовой рекурсивной. В качестве альтернативы, как мне изменить монаду продолжения, чтобы нести вокруг государства? Или создать комбинацию состояний и продолжения монад?

let sumTreeParallelDepthCont tree cont = 
    let rec sumRec tree depth cont = 
    let newDepth = depth - 1 
    match tree with 
    | Leaf(num) -> cont num 
    | Branch(left, right) -> 
     if depth <= 0 then 
     sumTreeContMonad left (fun leftM -> 
      sumTreeContMonad right (fun rightM -> 
      cont (leftM + rightM))) 
     else 
     let leftTask = Task.Factory.StartNew(fun() -> 
       let leftResult = ref 0 
       sumRec left newDepth (fun leftM -> 
       leftResult := leftM) 
       !leftResult 
      ) 
     let rightTask = Task.Factory.StartNew(fun() -> 
       let rightResult = ref 0 
       sumRec right newDepth (fun rightM -> 
       rightResult := rightM) 
       !rightResult 
      ) 
     cont (leftTask.Result + rightTask.Result) 
    sumRec tree 4 cont // 4 levels deep 

У меня есть немного более подробно на этом блоге: http://taumuon-jabuka.blogspot.co.uk/2012/06/more-playing-with-monads.html

Answer 1

В моих глазах, глубина выглядит хорошо, некрасиво бит реф клетка и назначение. Я не понимаю, зачем вам это нужно; Я думаю, что просто передача id (функция идентификации), поскольку параметр cont означает, что sumRec вернет значение, и вам не понадобятся ячейки ref. (Может быть, я не прав, это анализ, на наглядном.)

(я бы также избавиться от newDepth и просто рядного (depth-1) на сайтах рекурсивных вызовов, как со стилем.)

Наконец, я не знаю, что такое sumTreeContMonad, но оказалось, что вы можете просто использовать sumRec t -1 k вместо sumTreeContMonad t k, и он будет работать так же.

(Если ваш блог был код, а не фотографии кода, я мог бы просто опубликовать свой собственный код с этими уточнениями, но я не чувствую, как переписывание типов данных и такие. Почему размещать фотографии?)

Answer 2

Я думаю, что важно сначала понять, каковы ваши требования.

• Последовательная версия алгоритма не нужно держать depth (потому что он всегда обрабатывает остальную часть дерева). Тем не менее, он должен использовать продолжения, потому что дерево может быть большим.

• Параллельная версия, с другой стороны, должна содержать depth (потому что вы хотите только ограничить количество рекурсивных вызовов), но не нужно использовать продолжения (потому что глубина довольно ограничена и когда вы начинаете новую задачу, в любом случае она не держит стек).

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

let sumTreeParallelDepthCont tree = 
    let rec sumRec tree depth = 
    match tree with 
    | Leaf(num) -> num 
    | tree when depth <= 0 -> 
     sumTreeContMonad tree id 
    | Branch(left, right) -> 
     let leftTask = Task.Factory.StartNew(fun() -> sumRec left (depth + 1)) 
     let rightResult = sumRec right (depth + 1) 
     leftTask.Result + rightResult 
    sumRec tree 4 // 4 levels deep 

Там нет необходимости дублировать код из sumTreeContMonad, потому что вы можете просто назвать его текущее дерево в случае tree when depth <= 0.

Это также позволяет избежать использования ссылочных ячеек, создав Task<int> вместо Task, и я модифицировал алгоритм только для создания одной фоновой задачи и выполнения второй части работы над текущим потоком.