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

를, 깊이는 추한 비트가 심판 세포와 과제입니다, 잘 보인다. 왜 당신이 그들을 필요로하는지 나는 불분명하다. 그냥 cont 매개 변수로 id (신원 기능)을 전달하면 sumRec이 값을 반환한다는 것을 의미하므로 ref 셀은 필요하지 않습니다. (내가 잘못 될 수있다,이 분석 - 한 눈에 파악할 수 있습니다.)

(나는 또한 newDepth 제거하고 취득하는 것과 인라인 (depth-1) 스타일의 문제로 재귀 호출 사이트에서.)

마지막으로, 나는 sumTreeContMonad이 무엇인지 모르지만, sumTreeContMonad t k 대신에 sumRec t -1 k을 사용할 수 있으며, 똑같이 작동하는 것으로 보입니다.

(블로그 코드보다는 코드의 사진이 있다면, 난 그냥이 개선 내 자신의 코드를 게시 할 수 있지만 데이터 유형과 같은. 왜 게시물에 사진을 전사 기분이 안?)

Answer 2

먼저 요구 사항이 무엇인지 이해하는 것이 중요하다고 생각합니다.

• 알고리즘의 연속 버전은 depth (항상 트리의 나머지 부분을 처리하기 때문에)를 유지할 필요가 없습니다. 그러나 트리가 커질 수 있기 때문에 연속을 사용해야합니다.

• 반면에 병렬 버전은 depth (제한된 수의 재귀 호출 만하기 때문에)을 유지해야하지만 연속성을 사용할 필요가 없습니다 (깊이가 상당히 제한되어 있기 때문에 당신은 새로운 작업을 시작합니다, 어쨌든 스택을 유지하지 않습니다).

즉, 실제로 두 가지 측면을 결합 할 필요가 없습니다. 그럼 당신은 아주 간단한 방법으로 병렬 버전을 다시 작성할 수 있습니다 : 당신은 그냥 경우 tree when depth <= 0의 현재 나무에 호출 할 수 있기 때문에 sumTreeContMonad의 코드를 복제 할 필요가 없습니다

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 

.

Task 대신 Task<int>을 작성하여 참조 셀을 사용하지 않고 하나의 백그라운드 작업 만 생성하고 현재 스레드에서 작업의 두 번째 부분 만 수행하도록 알고리즘을 수정했습니다.