Back to Questions
780
views4
comments
Mapping symbols to a unique integers vs. laziness
f#

Hi,

I spent the afternoon thinking of the following problem:

I'm writing an F# program that is assembles a composite data structure. At various point a symbolic name has to be assigned a unique id. However, this id might be used at multiple locations using the predefined symbolic name. So I thought of the following function:

let generate_lazy_uid sym_name =
let dict = new System.Collections.Generic.Dictionary<_,_>();
if dict.ContainsKey(symname) then dict.[symname]
else let new_id = id _generator
dict.Add(symname,new_id);
new_id

Now, there is a computable list of ids that cannot be used, but computing this list takes a long time, thus should be deferred to the later stages of the computation. (say when the whole data structure is dumped to a file).

So I have a

let boundids : Set<int> = ... // some deferred computation

What exactly should I do to counstruct a closure-like entity which when evaluated returns a unique id not contained by the "boundids" set?

Given the symbolic name, the generate_lazy_uid function would always return the corresponding lazy id, but I have no clue by which means that can be achieved.

Any help is highly appreciated.

Thx,

Laszlo

.

I'm not sure I understand the question. Are the illegal IDs all computed at once? Or are we talking a generator that generates 'next highest illegal ID' each time you call it?

If the former, then I don't see what laziness buys you; the first time you ever create an ID, you must incur the whole expense of computing the 'illegal' set, at which point you can save that henceforth (and is easy to code). So I am guessing I misunderstand some detail of the question.

By on 1/23/2009 9:59 AM ()

Hi,

the set illegal of ids (integer values) can be computed at once, however it takes some time, say it has to fetched from a database. The data structure my program assembles may be recomputed a few times before dumping it to a file. E.g a user changes input data and he wants a kind of preview of the data where the actual id values are irrelevant. As soon as he is satisfied with the result, it can be dumped to a file. However, at this point the computation of the actual id values is inevitable.
I figured it is cleaner to have lazy ids rather than inserting additional tree processing step, since the generated data is fairly heterogeneous and the ids pop up at multiple locations.

I hope it have become clearer now...
Thx,
L

By on 1/23/2009 10:14 AM ()

Ok, I think so... so you want the 'uniqueness values' that appear throughout your structure to be computed quickly and it's ok for them to be illegal, and then at some later point you will 'commit' at which point you do the heavy lifting to compute illegal values and 'renumber' the illegal ones to be legal, is that it?

In that case, rather than do anything clever with laziness, I think I'd make the uniqueness values be like

type Unique() as this =

let static mutable universe = []

let mutable n = nextInt()

do universe <- this :: universe

member this.Value : int = n

static member Commit() =

// compute illegals

// walk universe and poke all illegal numbers to legal ones

Does it make sense (and fit the scenario)?

By on 1/23/2009 10:42 AM ()

Hi,

gee, thanks!!! I owe you one :) It works like a charm. It might be due to my limited experience in F# that I'm a little uncertain when and how to use laziness and mutable state elegantly. I've the beginner's anxiety to keep my code pure. :)

Here's the code I wrote, might be of interest to others. Please note that I ommitted the code for computation of the illegal ids for the sake of brevity.

let nextInt =
let count = ref 0
(fun() -> incr count; !count)

type Unique() as this =

static let mutable universe = []

let mutable n = nextInt()

do universe <- this :: universe

member this.Value with get() = n and set(v) = n <- v

static member Commit() =
// walk universe and poke all illegal numbers to legal ones
let illegals = Set.of_list [ 2;3 ]; // details of computation omitted

let fixIllegals = (fun (x:Unique) -> while illegals.Contains(x.Value) do x.Value <- nextInt())
List.iter fixIllegals universe

let generate_uid symname =
let dict = new System.Collections.Generic.Dictionary<_,_>();
if dict.ContainsKey(symname) then dict.[symname]
else let new_id = Unique()
dict.Add(symname,new_id);
new_id

let id1 = generate_uid "sym_id1"
printfn "%A" id1.Value
let id2 = generate_uid "sym_id2"
printfn "%A" id2.Value
let id3 = generate_uid "sym_id1"
printfn "%A" id3.Value

let refid2 = id2
printfn "%A" refid2.Value

printfn "Fixing illegal ids..."

do Unique.Commit()

printfn "%A" id1.Value
printfn "%A" id2.Value
printfn "%A" id3.Value
printfn "%A" refid2.Value

By on 1/24/2009 4:51 AM ()

    Topic tags

    IntelliFactory Offices Copyright (c) 2011-2012 IntelliFactory. All rights reserved.
    Home | Products | Consulting | Trainings | Blogs | Jobs | Contact Us | Terms of Use | Privacy Policy | Cookie Policy     		Built with WebSharper