Хвостовая рекурсия F# с XAMARIN MAC OS

Я пытаюсь реализовать этот пример из http://fsharpforfunandprofit.com/posts/recursive-types-and-folds-2/

Я использую Xamarin 6.1.5 для MAC OS.

Вот код

type Book = {title: string; price: decimal}

type ChocolateType = Dark | Milk | SeventyPercent
type Chocolate = {chocType: ChocolateType ; price: decimal}

type WrappingPaperStyle = 
    | HappyBirthday
    | HappyHolidays
    | SolidColor

type Gift =
    | Book of Book
    | Chocolate of Chocolate 
    | Wrapped of Gift * WrappingPaperStyle
    | Boxed of Gift 
    | WithACard of Gift * message:string

// A Book
let wolfHall = {title="Wolf Hall"; price=20m}
// A Chocolate
let yummyChoc = {chocType=SeventyPercent; price=5m}
// A Gift
let birthdayPresent = WithACard (Wrapped (Book wolfHall, HappyBirthday), "Happy Birthday")
// A Gift
let christmasPresent = Wrapped (Boxed (Chocolate yummyChoc), HappyHolidays)

let rec cataGift fBook fChocolate fWrapped fBox fCard gift :'r =
    let recurse = cataGift fBook fChocolate fWrapped fBox fCard
    match gift with 
    | Book book -> 
        fBook book
    | Chocolate choc -> 
        fChocolate choc
    | Wrapped (gift,style) -> 
        fWrapped (recurse gift,style)
    | Boxed gift -> 
        fBox (recurse gift)
    | WithACard (gift,message) -> 
        fCard (recurse gift,message) 

let totalCostUsingCata gift =
    let fBook (book:Book) = 
        book.price
    let fChocolate (choc:Chocolate) = 
        choc.price
    let fWrapped  (innerCost,style) = 
        innerCost + 0.5m
    let fBox innerCost = 
        innerCost + 1.0m
    let fCard (innerCost,message) = 
        innerCost + 2.0m
    // call the catamorphism
    cataGift fBook fChocolate fWrapped fBox fCard gift

let deeplyNestedBox depth =
    let rec loop depth boxSoFar =
        match depth with
        | 0 -> boxSoFar 
        | n -> loop (n-1) (Boxed boxSoFar)
    loop depth (Book wolfHall)


let rec totalCostUsingAcc costSoFar gift =
    match gift with 
    | Book book -> 
        costSoFar + book.price  // final result
    | Chocolate choc -> 
        costSoFar + choc.price  // final result
    | Wrapped (innerGift,style) -> 
        let newCostSoFar = costSoFar + 0.5m
        totalCostUsingAcc newCostSoFar innerGift 
    | Boxed innerGift -> 
        let newCostSoFar = costSoFar + 1.0m
        totalCostUsingAcc newCostSoFar innerGift 
    | WithACard (innerGift,message) -> 
        let newCostSoFar = costSoFar + 2.0m
        totalCostUsingAcc newCostSoFar innerGift 


let rec foldGift fBook fChocolate fWrapped fBox fCard acc gift :'r =
    let recurse = foldGift fBook fChocolate fWrapped fBox fCard 
    match gift with 
    | Book book -> 
        let finalAcc = fBook acc book
        finalAcc     // final result
    | Chocolate choc -> 
        let finalAcc = fChocolate acc choc
        finalAcc     // final result
    | Wrapped (innerGift,style) -> 
        let newAcc = fWrapped acc style
        recurse newAcc innerGift 
    | Boxed innerGift -> 
        let newAcc = fBox acc 
        recurse newAcc innerGift 
    | WithACard (innerGift,message) -> 
        let newAcc = fCard acc message 
        recurse newAcc innerGift


let totalCostUsingFold gift =  

    let fBook costSoFar (book:Book) = 
        costSoFar + book.price
    let fChocolate costSoFar (choc:Chocolate) = 
        costSoFar + choc.price
    let fWrapped costSoFar style = 
        costSoFar + 0.5m
    let fBox costSoFar = 
        costSoFar + 1.0m
    let fCard costSoFar message = 
        costSoFar + 2.0m

    // initial accumulator
    let initialAcc = 0m

    // call the fold
    foldGift fBook fChocolate fWrapped fBox fCard initialAcc gift 


[<EntryPoint>]
let main args =

       printfn "Arguments passed to function : %A" args
       let a = deeplyNestedBox 100000

       let res2= a |> totalCostUsingFold 


       // printfn "res2 = %A" res2
       0

Мне кажется, что это хвостовая рекурсия (как сказано на веб-странице), но я получаю ошибку stackoverflow во время выполнения

В параметрах компиляции проекта я выбрал поле «генерировать хвостовые вызовы».

Что-то не так с моим кодом или с Xamarin?


person Fagui Curtain    schedule 15.03.2017    source источник
comment
Возможно, это ограничение Mono, если вы будете искать SO, появится несколько вопросов, касающихся оптимизации хвостовых вызовов. Например. эта заявка все еще открыта.   -  person s952163    schedule 15.03.2017


Ответы (2)


Я не уверен, является ли это причиной переполнения стека, но рекурсивные вызовы в cataGift мне не кажутся хвостово-рекурсивными:

let rec cataGift fBook fChocolate fWrapped fBox fCard gift :'r =
    let recurse = cataGift fBook fChocolate fWrapped fBox fCard
    match gift with 
    | Book book -> 
        fBook book
    | Chocolate choc -> 
        fChocolate choc
    | Wrapped (gift,style) -> 
        fWrapped (recurse gift,style)
    | Boxed gift -> 
        fBox (recurse gift)
    | WithACard (gift,message) -> 
        fCard (recurse gift,message) 

В последних трех случаях вы вызываете recurse gift, который является рекурсивным вызовом, а затем передаете результат другой функции, такой как fCard или fBox.

Чтобы сделать его хвост-рекурсивным, вам нужно изменить код так, чтобы вызов recurse был последним в теле случая совпадения (возможно, с использованием продолжения или путем передачи функции fCard в recurse каким-либо образом).

person Tomas Petricek    schedule 15.03.2017
comment
catagift не является хвостовой рекурсией. foldПодарок есть. это функция, которая вызывается в totalCostUsingFold, которая вызывается в основной части. catagift был там только для контекста, учитывая, что я взял источник из http-ссылки. Я мог/должен был удалить из этого обсуждения - person Fagui Curtain; 15.03.2017
comment
А, спасибо за пояснение — не поможет ли удалить определение let recurse и просто напрямую вызвать foldGift? - person Tomas Petricek; 15.03.2017
comment
привет Томас удаление let recurse и прямой вызов foldGift действительно работает !! но это странно, разве код не рекурсивен по-прежнему с исходным синтаксисом? - person Fagui Curtain; 17.03.2017
comment
@FaguiCurtain Да, код по-прежнему является хвостовой рекурсией, но с внутренней функцией он компилируется с использованием инструкции .tail. Без этого, я думаю, компилятор сможет оптимизировать код самостоятельно. - person Tomas Petricek; 17.03.2017
comment
Я не уверен, что понимаю ваш комментарий. С внутренней функцией, если она скомпилирована с .tail, разве она не должна быть хороша, как предполагает ее имя? я смутно помню, как увидеть сборку в VS, как мне увидеть ее в (Mono)/Xamarin и где именно я должен искать намеки на хвостовую рекурсию в сборке? - person Fagui Curtain; 18.03.2017
comment
@FaguiCurtain Да, я думаю, что это все еще должно работать, но в случае, если что-то не так в моно с .tail, версия с локальной функцией не будет работать, но версия без нее все равно будет ... - person Tomas Petricek; 18.03.2017
comment
Я думаю, вы используете Windows? - person Fagui Curtain; 19.03.2017

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

Да, Mono по-прежнему не поддерживает хвостовые вызовы:

https://bugzilla.xamarin.com/show_bug.cgi?id=12635#c11

Это страшно!

person J D    schedule 11.04.2017