How to fold/reduce a map or set? Unnecessary sorting too.

[jmagaram]

I'm new to fp-ts and liking it. But I ran into a roadblock attempting to do something "simple" - fold/reduce a Map. Suppose you have a Map<Person, Age> and want to find out who is the oldest (assume Person is string and Age is number). This is easy to do with reducing - just loop through and keep track of the oldest person and then return it. My first problem was trying to find the method; there is no MAP.reduce. There is a MAP.getFoldableWithIndex and MAP.toUnfoldable. I couldn't figure out the first but was able to use MAP.toUnfoldable(ordString, ARRAY.Unfoldable)), which generates an array of key value pairs, and then you can ARRAY.reduce on it - very inefficient to make that array just so I can reduce it. So then on hunting some more I see plans for ReadonlyMap.reduce. OK, didn't realize there was a difference between the read-only versions and the mutable versions and I gravitated to the shorter-name versions. Didn't even realize I wasn't using the latest version.

The second problem is that even with the 2.11 version of ReadonlyMap.reduce you must provide an Ord, which seems totally unnecessary (inefficient) for a lot of folding tasks.

So, a few questions:

1. Should I be using the Readonly versions of everything? Are the non-readonly versions legacy and deprecated?
2. Should I be using getFoldableWithIndex? If so, how do you use it?
3. Why does folding require an Ord? How about making it optional.
4. When will the 2.11 or more recent versions be ready for production use? NPM gave me the ^2.10.5 version automatically.

---

Related to the above and the unnecessary sorting, I'm trying to get a random element from a set. Notice that to do this I think I have to first convert the set to an array (inefficient), and the array must be sorted (inefficient). I wish there was a way to convert a set to an array in whatever order it happens to be in, without specifying a sort. But better would be a function to get a random element from a set. My experience is mostly with C# and F# and each time I instantiate a new array or map or set in a pipeline I cringe because what I really want is to use iterables. I've tried iter-tools and it mostly does what I want. I don't understand why iterables aren't supported in fp-ts, along with Map and Set and Array. I'm trying to figure out when to use fp-ts and when to use iter-tools.

  const noActivity = pipe(
    active,
    SET.difference(eqShortcut)(new Set(history.keys())),
    SET.toReadonlyArray(ordShortcut), // unnecessary sorting here
    NEAR.fromReadonlyArray,
    OPT.map(randomElem)
  );

---

I see now that many of the methods in the Map, Array, and Set modules are not efficient. Looking something up in a Map using EQ requires looping through every object rather than using some internal hash table. As long as we're using the built-in javascript objects there is no efficiency to be had. Extra unnecessary sorting makes it theoretically worse. I'm starting to wonder if I should completely ignore performance and efficiency. For my app, I've got thousands of items in collections, not hundreds of thousands or millions, so perhaps the browser will zip through these calculations so fast the user would never notice. Maybe I shouldn't bother with iterables and just spin up tons of temporary arrays and maps just to get whatever answer I need. If I just stick with fp-ts at least my code will be understandable and correct.

[mlegenhausen]

There is already a discussion in #1288 about the difference between Map and Record. The (silent) consensus seems to be the you should try to use Record over Map cause of the performance implications.

Now to your questions.

1. Yes, because only Readonly data structures can hold one of the most important principle in FP which that is "referential transparency", which implies immutability. You should read the introduction to functional programming by gcanti: https://github.com/enricopolanski/functional-programming. They will also be removed in fp-ts@3.
2. Never used it but seems the way to go. When performance matters I would go for a Record. For usage you can take a look at the tests.
3. This is not possible either for Map or for Set. Both data structures use complex keys/items to guarantee uniqueness. For Map it is the key and for a Set it is the item itself. If you want to guarantee "referential transparency" you need a Eq instance (which is in included in Ord) which allows to compare keys/items in a Map or Set and determine if an item is included or not. This is also why you need to go through all items. The Ord is needed cause both data structures are unordered. So going from an unordered Set to an ordered Array needs an Ord instance. This guaranteed order is again implied by "referential transparency".
4. When it is finished. You can already use the existing rc in npm. Breaking changes are unlikely in this phase.

I hope that helps. Feel free to ask further questions.

[jmagaram]

I've read through most of the link you provided about referential transparency and other functional programming concepts. Of course I understand why EQ is necessary to look something up in a Map or Set. You might want to look it up by ID or object ID or some other properties. Still don't get the ORD requirement for folding or converting a Map or Set to an Array. Seems like even if you provide an ORD the output can change depending on the order the items were added to the Map or Set, especially if that ORD doesn't refer to every unique field in the object. I'm happy with the inherent "unordered" order of these collections when doing folding and sometimes converting to an array, and providing ANOTHER order through ORD doesn't make things any better and sometimes doesn't create deterministic results. The ORD can provide multiple different results depending on the order items were added, and aren't functions supposed to always provide the same output with the same input?