F# и хвостовая рекурсия
От: zverjuga Беларусь  
Дата: 30.10.19 21:18
Оценка:
имеется двумерный массив, заполненый 1 и 0. по сути — это бинарное изображение, где 0 — это черные пиксели, а 1 — белые. само изображение организовано так, что белые пиксели организованы по группам, которые разделены между собой черными пикселями (стенками).

задача: найти белые пятна на картинке и каждое пятно маркиковать отдельным числом. например, на картинке 3 белых пятна, разделенные черными стенками. то есть в итоговой картинке каждое пятно (состоящее из белых пикселей) обозначено числами 2, 3, 4 и так далее. реализован данный алгоритм так

// Learn more about F# at http://fsharp.org

open System

let source = array2D [[1; 1; 0; 1; 1; 1; 0; 1];
                      [1; 1; 0; 1; 0; 1; 0; 1];
                      [1; 1; 1; 1; 0; 0; 0; 1];
                      [0; 0; 0; 0; 0; 0; 0; 1];
                      [1; 1; 1; 1; 0; 1; 0; 1];
                      [0; 0; 0; 1; 0; 1; 0; 1];
                      [1; 1; 0; 1; 0; 0; 0; 1];
                      [1; 1; 0; 1; 0; 1; 1; 1]]

let (|Value|Zero|Out|) ((x: int), (y: int)) = 
    if x < 0 || y < 0 || x > (source.[0,*].Length - 1) || y > (source.[*,0].Length - 1) then
        Out
    else
        let row = source.[y, *]
        match row.[x] with
            | 0 -> Zero
            | v -> Value(v)

let processSource x y value =

    let rec markBits x y value =
        match (x, y) with
        | Value(v) ->
            if v <> value then
                source.[y, x] <- value
                markBits (x + 1) y value
                markBits (x - 1) y value
                markBits x (y + 1) value
                markBits x (y - 1) value
        | Zero | Out -> ()

    markBits x y value

[<EntryPoint>]
let main argv =
    printfn "Hello World from F#!"

    printfn "origin"
    printfn "%A" source
    printfn "--------------"

    let mutable value = 2

    source
    |> Array2D.iteri (fun y x e -> if e = 1 then
                                        processSource x y value
                                        value <- value + 1)

    printfn "modified"
    printfn "%A" source
    0 // return an integer exit code


результат работы такой
Hello World from F#!
origin
[[1; 1; 0; 1; 1; 1; 0; 1]
 [1; 1; 0; 1; 0; 1; 0; 1]
 [1; 1; 1; 1; 0; 0; 0; 1]
 [0; 0; 0; 0; 0; 0; 0; 1]
 [1; 1; 1; 1; 0; 1; 0; 1]
 [0; 0; 0; 1; 0; 1; 0; 1]
 [1; 1; 0; 1; 0; 0; 0; 1]
 [1; 1; 0; 1; 0; 1; 1; 1]]
--------------
modified
[[2; 2; 0; 2; 2; 2; 0; 3]
 [2; 2; 0; 2; 0; 2; 0; 3]
 [2; 2; 2; 2; 0; 0; 0; 3]
 [0; 0; 0; 0; 0; 0; 0; 3]
 [4; 4; 4; 4; 0; 5; 0; 3]
 [0; 0; 0; 4; 0; 5; 0; 3]
 [6; 6; 0; 4; 0; 0; 0; 3]
 [6; 6; 0; 4; 0; 3; 3; 3]]


по задумке, функция processSource реализована по принцицам хвостовой рекурсии, однако отладчик показывает, что каждый вызов рекурсивной функции markBits добавляет новый кадр в стек. то есть хвостовая рекурсия не работает. не могу понять, почему? ведь задача каждого кадра — всего лишь отметить очередной пиксель нужным числом и вызвать такую же функцию для всех соседних пикселей. сам кадр рекурсии обратно ничего не вычисляет и не возвращает. то есть компилятору нет смысла делать обычную рекурсию.

в чем ошибка? спасибо
проклятый антисутенерский закон
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.