Functional - Functional data structure with efficient maps

You are viewing an archived Text-only version of the thread. To view this thread in it's original format and/or if you want to reply to this thread please [click here]

Author

Functional data structure with efficient maps

Diego Olivier Fernandez Pons

2004-06-30, 9:05 am

Bonjour,

Does anyone know about a persistent (purely functional) data structure
designed to handle efficiently inner maps for integers ?

The only way I know to do this is to rebuild completely the data
structure by something like

map f data = from_list (List.map f (to_list data))

which isn't very efficient when handling large data sets

example of use in Caml

let sigma = function
| 0 -> 1
| 1 -> 2
| 2 -> 6
| 3 -> 3
| 4 -> 0
| 5 -> 4
| 6 -> 5
| _ -> failwith "invalid argument"

let myset = Set.from_list [0;4;5;6]
let newset = Set.map sigma myset (* should be efficent here *)

# Set.to_list newset
- [0;1;4;5]

Diego Olivier

Sponsored Links