Как объявить неизменный граф с круговыми ссылками? - PullRequest
Новая
       5

Как объявить неизменный граф с круговыми ссылками?

9 голосов
/ 06 января 2012

Я хочу объявить график всех состояний, где ребра представляют смежные состояния.Я думаю, что то, что я пытаюсь сделать, может быть названо «завязывание узла» (хотя я не уверен в этом).Это не работает, как я ожидал, и у меня есть пара вопросов.

Во-первых, я хочу, чтобы тип State имел строковое имя и список смежных состояний.Но это объявление выдает ошибку компилятора "... немедленная циклическая ссылка ...": 

type State = string * (State list)

Этот способ работает: 

type State(name:string, contigs: (State list)) = 
  let name = name
  let contigs = contigs

Но на самом деле это не обязательно называть членов,Кортеж в порядке.Как я могу заставить этот краткий синтаксис работать?

Во-вторых, следующий код пытается объявить, что должно быть тремя графами смежных состояний (HI и AK - это графы, состоящие из одного узла, все остальные состояния составляют последнееграфик), за которым следует список всех узлов.(Для краткости я здесь фактически объявил лишь несколько состояний): 

let rec hi = State("hi", []) 
and mo = State("mo", [il ia]) 
and il = State("il", [mo]) 
and ia = State("ia", [mo])
and states = [hi,mo,il,ia]

Это приводит к множеству ошибок, хотя в том числе "mo в конечном итоге будет оцениваться как часть его собственного определения" и "выражение былоожидается, что будет иметь тип 'a ->' b, но здесь имеет тип State ".Я думал, что ключевые слова 'rec' и 'и' позволят этому работать.Могу ли я определить этот самоссылающийся граф?Если да, то как?

Ответы [ 2 ]

6 голосов
/ 08 января 2012

Хотя то, что Даниил говорит правильно, я бы оспорил утверждение, что оно «идиоматическое», потому что это не дает очень полезной структуры данных для представления графиков в общем случае.В частности, он позволяет только добавлять новые вершины и ребра из них, но не добавлять или удалять ребра между существующими вершинами.В частности, это в основном означает, что ваш граф должен быть статически определен как константа в вашем исходном коде, поэтому вы не можете легко загрузить такой граф с диска.

Идиоматическое чисто функциональное представление графа состоит в замене разыменования на словарьпоиск.Например, представьте график в виде Map от вершин до Set s вершин, в которых есть ребра: 

> let g =
    Map["hi", set[]; "mo", set["il"; "ia"]; "il", set["mo"]; "ia", set["mo"]];;
val g : Map<string,Set<string>> =
  map
    [("hi", set []); ("ia", set ["mo"]); ("il", set ["mo"]);
     ("mo", set ["ia"; "il"])]

Например, вы можете искать вершины, непосредственно достижимые через ребра из mo вот так: 

> g.["mo"];;
val it : Set<string> = set ["ia"; "il"]

Это легче отлаживать, чем изменяемое представление, но имеет существенные недостатки:

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

  2. Сборщик мусора больше не возвращает недостижимые для вас подграфы.Обязательным решением является использование слабого словаря, но нет известных чисто функциональных слабых словарей.

Так что это возможно только в том случае, если производительность и утечки не будут проблемой.Это чаще всего тот случай, когда ваши графики маленькие или статичные.

6 голосов
/ 06 января 2012

Проблема в вашей структуре данных и использовании недопустимых разделителей элементов списка (должен быть точка с запятой). Это работает: (см. Редактирование) 

type State =
  | State of string * State list

let rec hi = State("hi", []) 
and mo = State("mo", [il; ia]) 
and il = State("il", [mo]) 
and ia = State("ia", [mo])
let states = [hi; mo; il; ia]

Рекурсивные ссылки будут реализованы в виде блоков (lazy).Таким образом, вы могли бы, немного больше печатая, сделать то же самое самостоятельно с mutable lazy s - только к вашему сведению - то, что у вас есть, идиоматично.

РЕДАКТИРОВАТЬ

Intellisense didn 'У него нет проблем с этим, но компилятор говорит, что

Рекурсивные значения не могут напрямую отображаться как конструкция типа 'List`1' в рекурсивной привязке.Эта функция была удалена из языка F #.Попробуйте вместо этого использовать запись.

Вы можете исправить это, используя seq вместо list. 

type State =
  | State of string * State seq

let rec hi = State("hi", []) 
and mo = State("mo", seq { yield il; yield ia }) 
and il = State("il", seq { yield mo }) 
and ia = State("ia", seq { yield mo })
let states = [hi; mo; il; ia]
...