F# хвостовая рекурсия

Нет. Если нужна обязательно хвостовая рекурсия, то перепиши все через монаду Async.

а если есть общие mutable привязки, которые передаются в вызов фции через аргументы? более подробно - type с mutable слотом

Не совсем понял, что имеешь ввиду. Как это влияет на хвостовой вызов?

это влияет на асинхронную запись в эту структуру

Ты о монаде Async? Моя идея была использовать то, что вычисление в этой монаде фактически раскладывается в продолжения, и там оператор for, который у тебя скрыт за List.iter, будет работать через хвостовой вызов. Асинхронность тут только в названии. Выполнение вполне может быть последовательным. Оператор for для async работает последовательно, но не кушает стек.

Да, если запускать Async через StartImmediate (по памяти), то будет последовательный запуск вычисления из того же потока.

Но тебе скорее всего нужен RunSynchronously, если ты действительно собираешься переписать через Async. Тому может быть только одна причина: высокая вложенность рекурсии и неминуемый StackOverflow без применения Async.

Что-то у меня такой вариант ещё дольше работает. Или надо не так?

let rec f n =
    if (n > 0)
    then
        let ballast = [0 .. 100000]
        let l = [0 .. 10]
        if ((n * 2) > (List.nth ballast 99999))
        then ()
        else 
            let asyncIter = l |> List.map (fun el -> 
                                             async { f (n - 1) })
            asyncIter |> Async.Parallel |> Async.RunSynchronously
            ()
    else ()

О, нет. Зачем так сложно, и зачем Parallel?

Пишу наугад:

let rec f n = async {
    if (n > 0)
    then 
        let ballast = [0 .. 100000]
        let l = [0 .. 10]
        if ((n * 2) > (List.nth ballast 99999))
        then return ()
        else 
            for el in l do         // все волшебство
                return! f (n - 1)  // в этих двух строках
    else return ()
}

Тогда функция f возвращает вычисление Async<unit>, которое можно запустить через Async.StartImmediate в том же потоке исполнения.

Повторюсь, вся эта овчинка стоит выделки только в том случае, если у тебя глубокая вложенность рекурсии, и ее никак по-другому свести к хвостовой не удается. Async сводит, но за свою плату. В твой код не вникал. Но я так понял, что он схематичный.

Посмотрел на твой код внимательнее. Зачем тебе хвостовая рекурсия? Он у тебя сильно ветвистый, широкий. Хвостовая рекурсия же нужна, если код с глубокой вложенностью. В твоем примере, хвостовая рекурсия нафиг не нужна. Скорее, вселенная помрет, чем твой код отработает для больших n.

код схематичный, а хвостовая рекурсия мне очень нужна, тем более даже в этом коде, всё зависит не только от вложенности, но и от величины балласта.

Если интересен реальный код, для которого я всё это и собираюсь делать, то вот -

let searchIter  onlyFullMatchesp
                (g1 : UndirectedGraph<Vertex, ILpEdge<Vertex, Lp>>)
                (g2 : UndirectedGraph<Vertex, ILpEdge<Vertex, Lp>>)   // Visited
                (storeAccs : accContainer)
                (activeAcc : accumulater) 
                (v1Set : Vertex * Path) 
                (v2Set : Vertex * Path)
                (reserv : reserv)
     =                                              
    let rec iterate firstIterP v1Set v2Set = 
        let v1, v1LaterPath = v1Set
        let v2, v2LaterPath = v2Set
        if activeAcc.stopped then () 
        else    
            (* outs *) 
            let outs1Paths = g1 |> getOutVertexesWithPaths_f (v1LaterPath.vertex, v1) 
            let outs2Paths = g2 |> getOutVertexesWithPaths_f (v2LaterPath.vertex, v2)
            let outs1 = outs1Paths |> getOnlyVs_f
            let outs2 = outs2Paths |> getOnlyVs_f 
            
            (* intersection *)
            let intersection = outs2 |> groupIntersectionVerts_f confp outs1 
            
            (* select search branchs *)
            match (onlyFullMatchesp, outs1 , outs2, intersection) with
            | (_, [], _, _) | (_, _, [], _) 
                -> ()
            | (_, _, _, intr) when intr.Count = 0 
                -> ()            
            | (true, _, _, intr) when intr.Count < (List.length outs2) 
                -> activeAcc.stopped <- true
                   ()            
            | _ ->            
                (* variants *)
                let variants = filteredVariants_f intersection reserv activeAcc
                match variants with 
                | [] -> if onlyFullMatchesp then activeAcc.stopped <- true
                        ()
                | _ ->
                    let splittedAlls = variants |> splitVariants_f onlyFullMatchesp
                    let onlyOriginally = splittedAlls |> onlyOriginallVariants_f
                    let withLpAnalyze = variants |> withoutUnlikeLpsPaths outs2Paths outs1Paths
                    let vrntsAndAccs = withLpAnalyze |> vrntsWithAccCopies activeAcc          
                    
                    vrntsAndAccs 
                        |> List.iteri
                            (fun step (vrnt , acc) ->
                                if (not (step = 0)) then storeAccs.add acc 
                                vrnt |> 
                                    List.iter 
                                        (fun (v2Now , v1Now) ->   
                                            let v1Path = outs1Paths 
                                                            |> List.find 
                                                                (fun path -> eq path.vertex v1Now)
                                            let v2Path = outs2Paths 
                                                            |> List.find 
                                                                (fun path -> eq path.vertex v2Now) 
                                            let okp = firstIterP || (goOnEqualPath v1Path v1LaterPath 
                                                                        v2Path v2LaterPath)
                                            match okp with
                                            | false when onlyFullMatchesp -> acc.stopped <- true
                                            | false -> ()
                                            | true ->
                                                acc.add v1Now v2Now
                                                iterate false (v1Now, v1Path) (v2Now, v2Path)))
    iterate true v1Set v2Set 
    storeAccs 

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

F# не должен увеличивать просто так глубину стека. Тем не менее, вижу два выхода:

• использовать С#;
• переписать через async как у меня в примере, но тогда всякие List.iter и List.iteri придется расписать явно через for. Просто нужно помнить, что обычный for и for для async - это две большие разницы, и обрабатываются они совершенно по-разному.

использовать С#;

я как раз таки и перешёл на F#, чтобы получить оптимизацию хв.р.

но тогда всякие List.iter и List.iteri придется расписать явно через for

А если есть несколько вложений List.iter/i (все они внутри Async), то надо каждый переписать через for или достаточно наиболее вложенных, на итерациях которых делается хвостовой вызов?

Есть еще вариант попробовать все же переписать через обычный хвостовой вызов.

> А если есть несколько вложений List.iter/i (все они внутри Async), то надо каждый переписать через for или достаточно наиболее вложенных, на итерациях которых делается хвостовой вызов?

Нужно взять рекурсивный вызов в return!, а ему нужен явный for. Двигайся от рекурсивного вызова.

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

А если есть несколько вложений List.iter/i (все они внутри Async), то надо каждый переписать через for или достаточно наиболее вложенных, на итерациях которых делается хвостовой вызов?

видимо все, иначе

 construct may only be used within computation expressions. To return a value from an ordinary function simply write the expression without 'return'.
 

Похоже так. Фишка в том, что return! для async превращается в хвостовой вызов. Цена - большее потребление памяти.

а как на др. яп, к примеру на CL, делать множественную хвостовую рекурсию?

В общем случае через Continuation Passing Style (CPS). Async в F# тоже работает поверх них - просто это все завуалировано.

Значение Async<'a> - это три продолжения:

• продолжение основного потока вычислений;
• продолжение в случае возникновения ошибки;
• продолжение в случае экстренного останова вычисления.

Вот эти три продолжения передаются в каждую часть вычисления Async. Обычный CPS - это первое продолжение Async.

я тут поэксперементировал с моим алгоритмом и CPS, получилось что-то страшноватое, но вроде рабочее. Я, правда, не знаю как проверить есть ли там оптимизация (единственное что лезет в голову - большие входные данные, (time (f...)) и смотреть на память).

Графы(в коде они названы деревьями) у меня там представляются двунаправленными ветвями, т.е. '((1 2 3) (2 3)) обозначает треугольный граф, в котором все 3 вершины(вершина - число в данном случае) связаны.

ссылка на код

по-моему нужны более удобные абстракции над продолжениями, по тому как писать в CPS мне не очень привычно, как миниум

F# async и есть такая абстракция над продолжениями. Еще в книге Грэма OnLisp должно быть что-то на тему CPS, хотя я не дочитал до того места. Там вводятся специальные макросы. И если бы мне пришлось писать в таком стиле на лиспе, то я бы скорее всего определил монадические аналоги PROGN (haskell's >>), LET (<-) и FUNCALL (<<=) и ввел бы UNIT (return). Тогда у меня неявно передавалось бы продолжение, а код выглядел бы похожим на обычный.

Кстати, F# async - не единственная абстракция. Есть еще Cont из хаскеля. Все это сильно взаимосвязано.

В твоем же случае async должен сильно упростить жизнь. Он чертовски много умеет.

Вот, мой опыт в изучении этой сложной материи:

http://www.linux.org.ru/forum/development/4636753#comment-4642410 (комментарий)

Я там ввел макросы cont-unit (return) и cont-let (монадическая стрелка), чтобы было удобнее писать.