User loginNavigation 
Automatically Deriving Mutable Data Structures?Suppose we have the typical immutable list, with some immutable operations: type 'a list = Nil  Cons 'a * 'a list let head l = match l with Nil > raise "Error!"  Cons(x,next) > x let add l x = Cons(x,l) let map f l = match l with Nil > Nil  Cons(x,next) > Cons(f x, map f next) ... let update l item newitem = match l with Nil as cur > cur  Cons(x,next) as cur > if item = x then Cons(newitem, next) else let u = update next item newitem in if u = next then cur else Cons(x, u) let append x l = match l with Nil > Cons(x, Nil)  Cons(x,next) > Cons(x, append x next) ... Is there any reason in principle we wouldn't be able to derive a mutable version automatically? At first blush, mutability seems somewhat distributive up to polymorphic parameters. Any recursive function on abstraction Foo that returns a Foo of the exact same type is an mutable update candidate. Transforming outwardsin on a Foo: 1. Return types are replaced by unit. This translation is predicated on a "mutable Foo" being like a "ref Foo". The derived mutable abstraction would look something like: let mutable 'a list = Nil  Cons mutable 'a * mutable 'a list let update l item newitem = match !l with Nil > ()  Cons(x,next) as cur > if item = !x then x := newitem else update next item newitem let append x l = match !l with Nil as x > l := Cons(x, Nil)  Cons(x,next) > append x next I can't think of any language that allows this, or any work along these lines, but I don't really know what to search for. It seems like it would be a pretty handy language feature though. Sometimes you really need a mutable data structure, and even though you have a perfectly good immutable equivalent at hand for which the mutable version seems like a mechanical translation, you still have to translate it by hand. Can anyone provide pointers to work like this or explain the difficulties why it's not feasible in general? By naasking at 20121002 00:55  LtU Forum  previous forum topic  next forum topic  other blogs  5457 reads

Browse archivesActive forum topics 
Recent comments
2 hours 8 min ago
4 hours 5 min ago
11 hours 46 min ago
11 hours 49 min ago
12 hours 29 min ago
12 hours 48 min ago
21 hours 6 min ago
23 hours 10 min ago
1 day 28 min ago
1 day 1 hour ago