5 ms·
The map is unnecessary. Just reduce: (* assuming: val total_len : string -> int *) List.reduce seq ~f:(fun a b -> if (total_len a) > (total_len
by samdk 15y ago
The map is unnecessary. Just reduce:
(* assuming: val total_len : string -> int *)
List.reduce seq ~f:(fun a b ->
if (total_len a) > (total_len b) then a else b)
It's not necessary in this case, but fold is often a lot more useful than reduce. At least the way I think of it, the type of reduce is 'a list -> ('a -> 'a -> 'a) -> 'a, whereas the type of fold is 'a list -> init:'b -> ('b -> 'a -> 'b) -> 'b. The upside is that you can construct basically any type of thing you'd like, since 'b is a completely different type. The downside is that if 'a is different than 'b, you need some sort of initial value to give it.
edit: Yes, this does require you to compute string length multiple times...but keep in mind that getting string length is very cheap in languages with good strings. (That is, basically everything except C's null-terminated strings.) 99% of the time it's not going not going to matter at all. If you do care, you can map to a tuple of (original_struct,total_len) and then do the reduce and then another map to get back to your original structure, or use a fold, as I mentioned, or write a (tail-)recursive function that does it in slightly fewer operations. (Although I don't think JS has tail-call optimizations, so that's probably a bad idea if you're doing it in JS.)
- ax 15y agoAren't I then computing the value of total_len for my largest object numerous times? That was why I went for the map, it made some sense to pre-compute the lengths and then find the largest one. Certainly I could implement some caching mechanism but that would come with some implementation complexity?
- Raphael_Amiard 15y agoLike in a procedural language, you can precompute and keep the results. It's still more concise. I use Ocaml's tuples here to make a pair of the length/object but you could use a struct/object/array/whatever: let precomp = List.map lst (fun el -> ((length el), el)) in let get_max (l1, el1) (l2, el2) = el1 if l1 > l2 else el2 in List.reduce lst get_max
- adimitrov 15y agoYes, this does require you to compute string length multiple times...but keep in mind that getting string length is very cheap in languages with good strings. (That is, basically everything except C's null-terminated strings.) Since this is a discussion about Haskell, too, I feel obliged to say that computing the length of a String type in Haskell is an O(n) operation, because String is really just type String = [Char] i.e. a linked list of Char values. Typically, if you want performance out of strings in Haskell, you'll use the Text or ByteString types BUT the length operation of Data.Text is still O(n). Only ByteString offers length :: ByteString -> Int Which is O(1).
- eru 15y agoYou can use a reduce/fold here, but it goes against the notion of building your program up from smaller pieces. Functional people call this composability, normal people call it code reuse. reduce/fold is a very general and powerful tool. In general you want to use the most specific and least powerful solution you can get away with. This spares the reader some thinking, and in theory gives the compiler more leeway. Also with less power there's less room for error. Here a combination of maximum (or maximumBy in Haskell) and map will give you what you are looking for.