Каков правильный способ выполнения изменяемых структур данных (например, списки пропуска, splay trees) в F #?

Какой хороший способ реализовать изменяемые структуры данных в F #? Причина, по которой я спрашиваю, заключается в том, что я хочу вернуться и реализовать структуры данных, которые я узнал в классе алгоритмов, которые я взял в этом семестре (списки пропусков, деревья разбиения, деревья слияния, попытки y-fast, деревья Ван Эмд Боас и т.д.)., который был чистым курсом теории без какого-либо кодирования, и я полагаю, что я мог бы также попытаться изучить F #, пока я это делаю. Я знаю, что я "должен" использовать деревья пальцев, чтобы получить функциональность Splay Tree на функциональном языке, и что я должен что-то делать с лень, чтобы получить функциональность skip-list и т.д., Но я хочу, чтобы основы были прибиты, прежде чем я попытаюсь играя с чисто функциональными реализациями.

Есть много примеров того, как выполнять функциональные структуры данных в F #, но не так много о том, как выполнять изменяемые структуры данных, поэтому я начал с исправления дважды связанного списка здесь во что-то, что позволяет вставлять и удалять в любом месте. Мой план состоит в том, чтобы превратить это в список пропусков, а затем использовать аналогичную структуру (дискриминационный союз записи) для древовидных структур, которые я хочу реализовать. Прежде чем я начну с чего-то более существенного, есть ли лучший способ сделать изменяемые структуры, подобные этому в F #? Должен ли я просто использовать записи и не беспокоиться о дискриминационном союзе? Должен ли я использовать класс вместо этого? Является ли этот вопрос "даже неправильным"? Должен ли я выполнять изменяемые структуры в С#, а не погружаться в F #, пока я не захочу сравнить их с их чисто функциональными аналогами?

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

module DoublyLinkedList =
    type 'a ll  = 
        | None
        | Node of 'a ll_node
    and 'a ll_node = {
        mutable Prev: 'a ll;
        Element : 'a ;
        mutable Next: 'a ll;
    }

    let insert x l = 
        match l with 
        | None -> Node({ Prev=None; Element=x; Next=None })
        | Node(node) ->
            match node.Prev with
                | None -> 
                    let new_node = { Prev=None; Element=x; Next=Node(node)}
                    node.Prev <- Node(new_node)
                    Node(new_node)
                | Node(prev_node) -> 
                    let new_node = { Prev=node.Prev; Element=x; Next=Node(node)}
                    node.Prev <- Node(new_node)
                    prev_node.Next <- Node(new_node)
                    Node(prev_node)

    let rec nth n l =
        match n, l with
        | _,None -> None
        | _,Node(node) when n > 0 -> nth (n-1) node.Next 
        | _,Node(node) when n < 0 -> nth (n+1) node.Prev 
        | _,Node(node) -> Node(node) //hopefully only when n = 0 :-)

    let rec printLinkedList head = 
        match head with
        | None -> ()
        | Node(x) -> 
            let prev = match x.Prev with
                        | None -> "-"
                        | Node(y) -> y.Element.ToString()
            let cur = x.Element.ToString()
            let next = match x.Next with
                        | None -> "-"
                        | Node(y) -> y.Element.ToString()
            printfn "%s, <- %s -> %s" prev cur next
            printLinkedList x.Next

Ответы

Ответ 1

Я считаю, что использование дискриминационного союза вместе с изменчивой записью - хороший подход. Дискриминационные союзы необходимы для сопоставления образцов. Альтернативой использованию изменяемой записи было бы создание случая объединения с изменяемыми ссылочными ячейками:

// Note: using ´ instead of ' to avoid StackOverflow syntax confusion
type LinkedList<´T> =  
  | None 
  | Node of (LinkedList<´T> ref) * 'T * (LinkedList<´T> ref)

Это может привести к немного более простому коду. Например, функция insert будет выглядеть так (я не пробовал, но думаю, что это должно быть правильно):

let insert x l =  
  match l with  
  | None -> Node(ref None, x, ref None)
  | Node(prev, v, next) as node -> 
      match !prev with 
      | None ->  
         prev := Node(ref None, x, ref node) 
         !prev
      | Node(_, _, prevNextRef) ->  
         prevNextRef := Node(ref (!node.Prev), x, ref node)
         prev := !prevNextRef
         !prevNextRef

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

let (|NodeInfo|) node = (node.Prev, node.Element, node.Next)

Для получения дополнительной информации см. Активные шаблоны в MSDN. Тогда функция insert будет выглядеть так:

let insert x l =  
    match l with  
    | None -> Node({ Prev=None; Element=x; Next=None }) 
    | Node(NodeInfo(None, _, _) as node) ->
        let new_node = { Prev=None; Element=x; Next=Node(node)} 
        node.Prev <- Node(new_node) 
        Node(new_node) 
    | Node(NodeInfo(Node(prev_node), _, _) as node) ->            
        let new_node = { Prev=node.Prev; Element=x; Next=Node(node)} 
        node.Prev <- Node(new_node) 
        prev_node.Next <- Node(new_node) 
        Node(prev_node)

[EDIT] На самом деле то же самое можно сделать с помощью шаблонов для извлечения элементов записи, но я думаю, что активные шаблоны могут сделать код немного приятнее.

Ответ 2

Причина, по которой я спрашиваю, заключается в том, что я хочу вернуться и реализовать структуры данных, о которых я узнал, в классе алгоритмов, которые я взял в этом семестре (списки пропуска, деревья разбиения, деревья слияния, быстрые попытки, деревья Ван Эмде Боас, и т.д.), который был чистым курсом теории без какого-либо кодирования, и я полагаю, что я мог бы также попытаться изучить F #, пока я это делаю.

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

Прежде чем я начну с чего-то более существенного, есть ли лучший способ сделать изменяемые структуры, подобные этому в F #?

Вы работаете по правильной линии. Если вы хотите примеры, посмотрите на эту изменчивую реализацию кучи, написанную в OCaml Жаном-Кристофом Филиатером. Есть много других замечательных примеров простых и эффективных изменяемых структур данных, которые используют функциональное программирование в своих API-интерфейсах, которые написаны в OCaml.

Должен ли я просто использовать записи и не беспокоиться с дискриминационным соединением?

В случае изменяемых структур данных их части часто хранятся смежно в массиве. Вот почему они часто намного эффективнее, чем их чисто функциональные коллеги.

Должен ли я выполнять изменяемые структуры в С#, а не погружаться в F #, пока я не захочу сравнить их с их чисто функциональными аналогами?

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