Tôi đã viết một hàm thú vị trong F #, có thể duyệt và ánh xạ bất kỳ cấu trúc dữ liệu nào (giống như chức năng ở mọi nơi có sẵn trong Phế liệu của bạn). Thật không may nó nhanh chóng gây ra một tràn ngăn xếp trên thậm chí cấu trúc dữ liệu khá nhỏ. Tôi đã tự hỏi làm thế nào tôi có thể chuyển đổi nó thành một phiên bản đệ quy đuôi, tiếp tục phiên bản phong cách đi qua hoặc một thuật toán tương đương bắt buộc. Tôi tin rằng F # hỗ trợ monads, do đó, đơn nguyên tiếp tục là một lựa chọn.Làm thế nào tôi có thể thực hiện chức năng F # này không gây ra tràn ngăn xếp
// These are used for a 50% speedup
let mutable tupleReaders : List<System.Type * (obj -> obj[])> = []
let mutable unionTagReaders : List<System.Type * (obj -> int)> = []
let mutable unionReaders : List<(System.Type * int) * (obj -> obj[])> = []
let mutable unionCaseInfos : List<System.Type * Microsoft.FSharp.Reflection.UnionCaseInfo[]> = []
let mutable recordReaders : List<System.Type * (obj -> obj[])> = []
(*
Traverses any data structure in a preorder traversal
Calls f, g, h, i, j which determine the mapping of the current node being considered
WARNING: Not able to handle option types
At runtime, option None values are represented as null and so you cannot determine their runtime type.
See http://stackoverflow.com/questions/21855356/dynamically-determine-type-of-option-when-it-has-value-none
http://stackoverflow.com/questions/13366647/how-to-generalize-f-option
*)
open Microsoft.FSharp.Reflection
let map5<'a,'b,'c,'d,'e,'z> (f:'a->'a) (g:'b->'b) (h:'c->'c) (i:'d->'d) (j:'e->'e) (src:'z) =
let ft = typeof<'a>
let gt = typeof<'b>
let ht = typeof<'c>
let it = typeof<'d>
let jt = typeof<'e>
let rec drill (o:obj) : obj =
if o = null then
o
else
let ot = o.GetType()
if FSharpType.IsUnion(ot) then
let tag = match List.tryFind (fst >> ot.Equals) unionTagReaders with
| Some (_, reader) ->
reader o
| None ->
let newReader = FSharpValue.PreComputeUnionTagReader(ot)
unionTagReaders <- (ot, newReader)::unionTagReaders
newReader o
let info = match List.tryFind (fst >> ot.Equals) unionCaseInfos with
| Some (_, caseInfos) ->
Array.get caseInfos tag
| None ->
let newCaseInfos = FSharpType.GetUnionCases(ot)
unionCaseInfos <- (ot, newCaseInfos)::unionCaseInfos
Array.get newCaseInfos tag
let vals = match List.tryFind (fun ((tau, tag'), _) -> ot.Equals tau && tag = tag') unionReaders with
| Some (_, reader) ->
reader o
| None ->
let newReader = FSharpValue.PreComputeUnionReader info
unionReaders <- ((ot, tag), newReader)::unionReaders
newReader o
FSharpValue.MakeUnion(info, Array.map traverse vals)
elif FSharpType.IsTuple(ot) then
let fields = match List.tryFind (fst >> ot.Equals) tupleReaders with
| Some (_, reader) ->
reader o
| None ->
let newReader = FSharpValue.PreComputeTupleReader(ot)
tupleReaders <- (ot, newReader)::tupleReaders
newReader o
FSharpValue.MakeTuple(Array.map traverse fields, ot)
elif FSharpType.IsRecord(ot) then
let fields = match List.tryFind (fst >> ot.Equals) recordReaders with
| Some (_, reader) ->
reader o
| None ->
let newReader = FSharpValue.PreComputeRecordReader(ot)
recordReaders <- (ot, newReader)::recordReaders
newReader o
FSharpValue.MakeRecord(ot, Array.map traverse fields)
else
o
and traverse (o:obj) =
let parent =
if o = null then
o
else
let ot = o.GetType()
if ft = ot || ot.IsSubclassOf(ft) then
f (o :?> 'a) |> box
elif gt = ot || ot.IsSubclassOf(gt) then
g (o :?> 'b) |> box
elif ht = ot || ot.IsSubclassOf(ht) then
h (o :?> 'c) |> box
elif it = ot || ot.IsSubclassOf(it) then
i (o :?> 'd) |> box
elif jt = ot || ot.IsSubclassOf(jt) then
j (o :?> 'e) |> box
else
o
drill parent
traverse src |> unbox : 'z
Bạn có thể cho một ví dụ, nơi bạn đã đi stack overflow? –