5 ms·

One bit of trouble I have with functional style programming is something like the following example: if I have an array of people with firstName and lastName pr

by ax 15y ago

One bit of trouble I have with functional style programming is something like the following example: if I have an array of people with firstName and lastName properties, how would I go about returning the person with the longest full name without adding any properties directly to the objects? It is a simple map then reduce to return the maximum length, a fairly trivial modification thereof to return the full name, but when I want to return the original object, I can't think of a good way to do this. The best I can figure is first mapping to a nested array where the first element is the object and the second is the computed property but that seems really messy. Thoughts?

neutronicus 15y ago
You wouldn't use map or reduce, you'd just use recursion with an accumulator. If you absolutely insist on map/reduce, you can just use reduce, where your binary function returns whichever object has a longer full name.
- ax 15y ago
  In hindsight the second solution was obvious :) But can you explain your ideal solution more? Is it something that can be accomplished in Javascript?
- rapala 15y ago
  Well, reduce is a recursion with an accumulator. Did you had something special in mind?
- eru 15y ago
  Why would you write mind-boggling recursion by hand, and not use a nice combinator that comes pre-debugged?
  - neutronicus 15y ago
    Because I had a brain fart and though "reduce" was "scan", and I didn't want to initialize an array.
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 ago
  Aren'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 ago
    Like 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 ago
  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.) 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).
ufo 15y ago
The pattern you mention of using a tuple of key-value pairs is not that bad and it even has a name. The Perl people call it the Swartzian transform. An alternative if you don't like that would be having the maximum-finding function receive an additional comparator argument, similarly to qsort.
- telemachos 15y ago
  > The Perl people call it the Swartzian transform. Yup, though one small thing: it's 'Schwartzian transform'[1] for Randal Schwartz. [1] http://en.wikipedia.org/wiki/Schwartzian_transform http://en.wikipedia.org/wiki/Schwartzian_transform
jfager 15y ago
You don't need a map, just a reduce (foldl, really). Using underscore, no double calculation: _.reduce(arr, function(p1, p2) { var len = p2.firstName.length + p2.lastName.length; return (len > p1[1]) ? [p2, len] : p1; }, [null, -1]);
- wooby 15y ago
  Also using underscore, with sortBy: _.chain(people) .sortBy(function(person) { return person.firstName.length + person.lastName.length; }) .last() .value()
  - mhansen 15y ago
    FYI, this isn't as general, but I think it shows off underscore quite nicely: _(people).max(function(person) { return person.firstName.length + person.lastName.length; });
nicklovescode 15y ago
longestName = maximumBy . comparing $ \(f,l) -> length $ f++l
- eru 15y ago
  That doesn't fit the bill. He was looking for comparison on a structure that holds more than just the name. (Though the right answer is very similar to what you've written.)
sgk284 15y ago
Similar in spirit to the Haskell and Lisp examples, here it is in Python: people = [Person('foo', 'bar'), Person('John', 'Doe'), Person('Jane', 'Anonymous')] key = lambda person: len(person.first_name + person.last_name) max(people, key=key)
gcr 15y ago
In racket, I'd write something like (argmax (λ(c) (string-length (customer-name c))) customers) http://docs.racket-lang.org/reference/pairs.html?q=argmax#(def._((lib._racket/list..rkt)._argmax) http://docs.racket-lang.org/reference/pairs.html?q=argmax#(d...) Haskell has argmaxBy: http://hackage.haskell.org/packages/archive/list-extras/0.3.0/doc/html/Data-List-Extras-Argmax.html http://hackage.haskell.org/packages/archive/list-extras/0.3.... If your language doesn't have argmax, fold the list with the best value, like this in lisp: (define (my-argmax fun lst) (foldl (λ(prev-max elt) (if (< (fun prev-max) (fun elt)) elt prev-max)) (car lst) (cdr lst))) No extra space usage, no temporary values, no sorting; all in O(N) time. :)
eru 15y ago
In Haskell there are some helper functions for these: longestLastname :: [Person] -> Person longestLastname names = maximumBy (comparing (length . lastname)) names In general, you can do map something like extractProperty list = map (\x -> (f x, x)) list Then work on the first element of the tuple (comparing for sorting etc), and at the end return the original object by extracting the second element of the tuple.

by ax 15y ago

neutronicus 15y ago

You wouldn't use map or reduce, you'd just use recursion with an accumulator. If you absolutely insist on map/reduce, you can just use reduce, where your binary function returns whichever object has a longer full name.

ax 15y ago
In hindsight the second solution was obvious :) But can you explain your ideal solution more? Is it something that can be accomplished in Javascript?
rapala 15y ago
Well, reduce is a recursion with an accumulator. Did you had something special in mind?
eru 15y ago
Why would you write mind-boggling recursion by hand, and not use a nice combinator that comes pre-debugged?
- neutronicus 15y ago
  Because I had a brain fart and though "reduce" was "scan", and I didn't want to initialize an array.

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 ago
Aren'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 ago
  Like 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 ago
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.) 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).

ufo 15y ago

The pattern you mention of using a tuple of key-value pairs is not that bad and it even has a name. The Perl people call it the Swartzian transform. An alternative if you don't like that would be having the maximum-finding function receive an additional comparator argument, similarly to qsort.

telemachos 15y ago
> The Perl people call it the Swartzian transform. Yup, though one small thing: it's 'Schwartzian transform'[1] for Randal Schwartz. [1] http://en.wikipedia.org/wiki/Schwartzian_transform http://en.wikipedia.org/wiki/Schwartzian_transform

jfager 15y ago

You don't need a map, just a reduce (foldl, really). Using underscore, no double calculation: _.reduce(arr, function(p1, p2) { var len = p2.firstName.length + p2.lastName.length; return (len > p1[1]) ? [p2, len] : p1; }, [null, -1]);

wooby 15y ago
Also using underscore, with sortBy: _.chain(people) .sortBy(function(person) { return person.firstName.length + person.lastName.length; }) .last() .value()
- mhansen 15y ago
  FYI, this isn't as general, but I think it shows off underscore quite nicely: _(people).max(function(person) { return person.firstName.length + person.lastName.length; });

nicklovescode 15y ago

longestName = maximumBy . comparing $ \(f,l) -> length $ f++l

eru 15y ago
That doesn't fit the bill. He was looking for comparison on a structure that holds more than just the name. (Though the right answer is very similar to what you've written.)

sgk284 15y ago

Similar in spirit to the Haskell and Lisp examples, here it is in Python: people = [Person('foo', 'bar'), Person('John', 'Doe'), Person('Jane', 'Anonymous')] key = lambda person: len(person.first_name + person.last_name) max(people, key=key)

gcr 15y ago

In racket, I'd write something like (argmax (λ(c) (string-length (customer-name c))) customers) http://docs.racket-lang.org/reference/pairs.html?q=argmax#(def._((lib._racket/list..rkt)._argmax) http://docs.racket-lang.org/reference/pairs.html?q=argmax#(d...) Haskell has argmaxBy: http://hackage.haskell.org/packages/archive/list-extras/0.3.0/doc/html/Data-List-Extras-Argmax.html http://hackage.haskell.org/packages/archive/list-extras/0.3.... If your language doesn't have argmax, fold the list with the best value, like this in lisp: (define (my-argmax fun lst) (foldl (λ(prev-max elt) (if (< (fun prev-max) (fun elt)) elt prev-max)) (car lst) (cdr lst))) No extra space usage, no temporary values, no sorting; all in O(N) time. :)

eru 15y ago

In Haskell there are some helper functions for these: longestLastname :: [Person] -> Person longestLastname names = maximumBy (comparing (length . lastname)) names In general, you can do map something like extractProperty list = map (\x -> (f x, x)) list Then work on the first element of the tuple (comparing for sorting etc), and at the end return the original object by extracting the second element of the tuple.