Загрузка набора рекурсивно типизированных элементов в F #

Question

Предположим, мы имели таблицу поставщиков в базе данных SQL, который мы хотим загрузить в F #:

+----+--------+--------+ 
| ID | Name | Parent | 
+----+--------+--------+ 
| 1 | Nest | 2  | 
| 2 | Google | NULL | 
| 3 | Apple | NULL | 
+----+--------+--------+ 

Использование провайдеров типа достаточно легко получить таблицу в F #, но предположим, что мы хотим, чтобы затем преобразовать данные в последовательность Вендоры, где Vendor является тип, как это:

Vendor = {ID: int; Name: String; Parent: Vendor option} 

Как бы один идти о делать это? Проблема в том, что при создании последовательности поставщиков мы не можем сопоставлять каждой строке конкретный поставщик, так как у нас пока нет последовательности поставщиков. Было бы неплохо также предположить, что приложение допускает циклы (A может иметь B в качестве родителя, а B может иметь A в качестве родителя), хотя в случае продавцов это на самом деле не имеет смысла.

Вы могли бы вместо того, чтобы определить тип поставщика, как:

Vendor = {ID: int; Name: String; ParentID: int option} 

Но это, кажется, гораздо менее элегантно, так как каждый раз, когда вы хотите, чтобы ссылаться на родительскую поставщика вы должны сделать какой-то поиска. Есть ли известное решение? Это похоже на ситуацию, которая может часто возникать (особенно при работе с графами или деревьями).

Также кажется, что решение может включать в себя какую-то ленивую оценку, но мне непонятно, как здесь можно применять Lazy < 'T> типа F #.

Answer 1

Это не особенно элегантное решение, но тот, который использует ленивые вычисления для родителей будет выглядеть примерно так: вы бы иметь два типа, одна из которых соответствует схеме вашей таблицы и один рекурсивный:

type Flat = { ID: int; Name: string; ParentID : int option} 

type Recursive = { ID: int; Name: string; Parent: Lazy<Recursive> option} 

Тогда давайте создадим что-то, что выглядит как ваш стол:

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 

И вы можете поместить его вместе, как это:

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)   
    } 

Итак, в каком-то смысле вы используете ленивый тип, чтобы отложить следующий шаг рекурсии, пока вам это не понадобится. В противном случае getRecordRecursive 4 даст вам переполнение стека.

Но есть компромиссы - вы, например, больше не получаете хорошего поведения на таких записях. Я не уверен, что вам не лучше с Flat записями в конечном счете.