Hacker News Reader

Comment by ax | Hacker News Reader

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?

View on HN

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.)

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?

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

    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).

You 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.

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]);

Also using underscore, with sortBy:

    _.chain(people)
    .sortBy(function(person) { 
      return person.firstName.length + person.lastName.length; })
    .last()
    .value()

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;
  });

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.

> 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

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#(d...)

Haskell has argmaxBy: 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. :)

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

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.)

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.

In hindsight the second solution was obvious :) But can you explain your ideal solution more? Is it something that can be accomplished in Javascript?

Well, reduce is a recursion with an accumulator. Did you had something special in mind?

Why would you write mind-boggling recursion by hand, and not use a nice combinator that comes pre-debugged?

Because I had a brain fart and though "reduce" was "scan", and I didn't want to initialize an array.

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.

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)

Reply on news.ycombinator.com