Loading a set of recursively typed elements in F #
Let's say we had a vendor table in a SQL database that we want to load into F #:
+----+--------+--------+
| ID | Name | Parent |
+----+--------+--------+
| 1 | Nest | 2 |
| 2 | Google | NULL |
| 3 | Apple | NULL |
+----+--------+--------+
Using type providers, it's easy to get a table in F #, but suppose we would then like to convert the data to a sequence of providers, where Vendor is the type:
Vendor = {ID: int; Name: String; Parent: Vendor option}
How would you do it? The problem is that when creating a sequence of suppliers, we cannot match each line to a specific supplier, since we do not yet have a sequence of suppliers. It would also be nice to assume that the application allows for loops (A could have B as a parent and B could have A as a parent), although in the case of providers, this really doesn't make sense.
Instead, you can define the provider type as:
Vendor = {ID: int; Name: String; ParentID: int option}
But this seems much less graceful, since every time you want to go to the parent supplier, you have to do some sort of search. Is there a known solution? This is similar to a situation that can arise frequently (especially when working with graphs or trees).
It also seems like the solution might involve some kind of lazy evaluation, but it's not clear to me how the Lazy <T> type can be applied here in F #.
source to share
It's not a very elegant solution, but one that uses lazy evaluation on the parent would look something like this, you have two types, one that matches your table schema and one that is recursive:
type Flat = { ID: int; Name: string; ParentID : int option}
type Recursive = { ID: int; Name: string; Parent: Lazy<Recursive> option}
Then set up something similar to your table:
let records =
[
{ ID = 1; Name = "Nest"; ParentID = Some 2 }
{ ID = 2; Name = "Google"; ParentID = None }
{ ID = 3; Name = "Apple"; ParentID = None }
{ ID = 4; Name = "Yin"; ParentID = Some 5 }
{ ID = 5; Name = "Yang"; ParentID = Some 4 }
]
|> List.map (fun x -> x.ID, x)
|> Map.ofList
let getRecord recID = records |> Map.find recID
And you can connect it like this:
let rec getRecordRecursive recID =
let record = getRecord recID
{
ID = record.ID
Name = record.Name
Parent =
record.ParentID
|> Option.map (fun pid ->
Lazy.Create <| fun () ->
getRecordRecursive pid)
}
So, in a sense, you are using a lazy type to defer the next step of the recursion until you need it. Otherwise will getRecordRecursive 4
give you a stack overflow.
But there are trade-offs - for example, you no longer get good behavior in such recordings. I'm not sure if the recordings won't help you anymore Flat
in the end.
source to share