//Type Definition for a 2-3 tree
type table<'key , 'a> =
Empty
| Branch2 of table<'key , 'a> * ('key * 'a) * table<'key , 'a>
| Branch3 of table<'key , 'a> * ('key * 'a) * table<'key , 'a> * ('key * 'a) * table <'key , 'a>
//proposed body for a function that poerforms a fold over the above structure using continuations
// fold over table using continuation passing
let I x = x
let foldMapTable fl fb1 fb2 tab =
let rec Loop tab cont =
match tab with
| Empty -> fl Empty
| Branch2( bl, (k,v), br) ->
Loop bl (fun lacc ->
Loop br (fun racc ->
cont (fb2 lacc (k,v) racc)))
| Branch3(bl, (k1, v1), bc, (k2, v2), br) ->
Loop bl (fun lacc ->
Loop bc (fun cacc ->
Loop br (fun racc ->
cont (fb2 lacc (k1, v1) cacc (k2, v2) racc) )))
Loop tab I
When I try to compile I get the following error
table.fs(144,18): error FS0001: Type mismatch. Expecting a
'a -> 'b -> 'c
but given a
'c.
The resulting type would be infinite when unifying ''a' and ''b -> 'c -> 'a'.
now the strange thing is that when I comment out the Branch3 type in the Union Declaration and comment out the last case of my match statement then the resulting fold over the union of an Empty Or a Branch2 compiles.
Any ideas. I am using the ideas from the Indside F# Blog's series on Catamorphisms to try to create this functionality
Thanks