Как функционально обновить записи с полями, которые поддерживают модификации на месте, в OCaml? - PullRequest
Новая
       19

Как функционально обновить записи с полями, которые поддерживают модификации на месте, в OCaml?

2 голосов
/ 01 марта 2010

Предположим, у меня есть запись с полем Hashtbl: 

type rec = {
  table : (int, int) Hashtbl.t;
  value : int;
  (* more fields... *)
}

Как мне обновить его функционально, т.е. что-то вроде этого: 

let new_rec = { old_rec with
  value = old_rec.value + 1 ;                 (* that's ok *)
  table = hash_table + (key -> value binding) (* but how should I do this??? *)
}

Я бы хотел услышать об общем подходе, это не относится к Hashtbl. Очевидно, мне придется скопировать такую ​​структуру, а затем изменить копию. Но с чем я сталкиваюсь, так это с тем, чтобы сделать результирующий код максимально функциональным.

Ответы [ 3 ]

3 голосов
/ 01 марта 2010

Чтобы сделать его использование максимально функциональным, вы можете сделать что-то вроде этого, 

let functional_insert tbl k v =
    let x = Hashtbl.copy tbl in
    let () =  Hashtbl.replace x k v
    x

Конечно, если вы много делаете, было бы лучше использовать функциональную структуру данных - Map в ocaml. Это также общий подход: если структура данных изменчива, ее необходимо скопировать, чтобы использовать ее функционально. Просто для справки (для взвешивания, если вам нужно заменить структуру), реализация Hashtbl представляет собой массив связанных списков; 

type ('a, 'b) t =
  { mutable size: int;                        (* number of elements *)
    mutable data: ('a, 'b) bucketlist array } (* the buckets *)

and ('a, 'b) bucketlist =
    Empty
  | Cons of 'a * 'b * ('a, 'b) bucketlist
3 голосов
/ 02 марта 2010

Мне бы очень хотелось услышать об общем подходе, это не относится к Hashtbl

Основная проблема, которую вы пытаетесь решить, состоит в том, чтобы взять изменяемую структуру данных и обращаться с ней как с неизменяемой . Тот факт, что это происходит при создании новой записи, - это красная сельдь. (Хотя я укажу, что, поскольку вы создаете запись, в которой каждое поле отличается, old_rec with является излишним и отвлекающим.)

Общим решением для обработки изменяемой структуры данных, как если бы она была неизменной, было copy, затем mutate . Но это решение чревато опасностью:

  • При точно неясно, при каких обстоятельствах достаточно мелкой копии или когда вам, возможно, придется написать глубокую копию.

  • Если абстракция изменчива, нет гарантии, что даже предлагает операцию копирования (или соответствующую операцию копирования).

  • Копии могут быть дорогими, особенно глубокие копии.

Именно эти соображения и побуждают людей избегать изменчивого состояния. Я понимаю, что это трудно сделать в Caml, потому что стандартные библиотеки необычайно необходимы для функционального языка. Тем не менее, я считаю, что правильная «общая» стратегия в долгосрочной перспективе заключается в замене изменчивых абстракций чисто функциональными структурами данных .

Приложение: Вот пример для хеш-таблиц: 

let extend key val tbl =
  let h = Hashtbl.copy tbl in
  let _ = Hashtbl.replace tbl key val in
  h

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

1 голос
/ 01 марта 2010

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

Только из просмотра документации онлайн, я думаю.

val replace : ('a, 'b) t -> 'a -> 'b -> unit

Hashtbl.replace tbl x y заменяет текущую привязку x в tbl привязкой x к y. Если x не связан в tbl, привязка x к y добавляется к tbl. Это функционально эквивалентно Hashtbl.remove tbl x, за которым следует Hashtbl.add tbl x y.

...