One data with two structures: Functional Programming vs Imperative Programming

2
votes

Suppose in C, we have following struct: 

struct MyData {
    char key1[20];
    long key2;
    ...  /* some data */
};

Essentially, in addition to some data, we have two keys: key1 and key2. Suppose we need to manage a bunch of objects of MyData in two different ways, for example, to quickly find corresponding object based on either key1 or key2 (but not both). One way to meet this requirement is to build two different RB-trees (or hash-tables) according to the two keys, respectively. In C/C++, the data need not to be duplicated since we only need to record the pointers of objects.

In above hypothetical example, the key point is that we have a bunch of data with same type and we can organized it through two different data structures without duplicating the data in imperative language. I am wondering how pure functional programming can efficiently meet this requirement without duplicating data. To make it more general or challenging, the two data structures may not be of same type. For example, one could be rb-tree and the other could be hash-table.

If possible, please layout your solution in Haskell.

PS: As a newbie to functional programming, I couldn't help wondering how to achieve some tricks from imperative programming in a pure functional programming. I know sometimes it doesn't make sense at all. If someone feels this question is also pointless, please layout the detail reasoning.

Thanks

2
haskelldata-structuresfunctional-programming
Could you use union here, intending to use either key1 or key2 in this MyData struct? – a3.14_Infinity
No. If you use key1 to search the object, you may also want to know what's the corresponding key2 value of the object. – Yan Zhu
You only want to lookup the values? Or also modify them? Mutation does make things a bit more complicated in the functional settings. In imperative languages the changes are automatically propogated between the shared values of the two structures, this is not so in the functional approach at least if you don't use some special data structure. – Bakuriu
@Bakuriu: there is also little need for such change propagation in functional programming. – Erik Kaplun

2 Answers

7
votes

This is generally not an issue in functional programming either.

data MyData = MyData
  { key1 :: ByteString
  , key2 :: Int
  , {- some data -} }

Now we can build a HashMap ByteString MyData, using key1 as the key, or a Vector MyData using key2 as the index, or whatever. Only the pointers to the keys will be duplicated, not the records or even the keys themselves.

4
votes

There is little reason for Haskell or any other language, imperative or functional, to not store references/pointers to immutable objects (especially those bigger than a pointer) by default, except for specific reasons of optimisation such as perhaps memory layout or when functional code is rewritten by e.g. the compiler under the hood to be more performant.

In other words, there is little reason to not assume Haskell (or any other modern language) handles this as expected and as efficiently as C.