Lambda the Ultimate

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 outwards-in on a Foo:

1. Return types are replaced by unit.
2. Arguments of type Foo become "mutable Foo".
3. A recursive call propagates the update forwards.
4. For any application of the same Foo constructor to function arguments and referencing the remainder of the data structure, an in-place update for the closest mutable variable is inserted.
5. For any application of a different Foo constructor than the one just matched, the in-place update bubbles up to the previous activation frame.
6. Any code that simply returns the current element is eliminated.

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?

http://www.typescriptlang.org

TypeScript starts from the syntax and semantics that millions of JavaScript developers know today.

TypeScript types let you define interfaces between software components and to gain insight into the behavior of existing JavaScript libraries.