Какой хороший способ реализовать изменяемые структуры данных в 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
