5 ms·
Learn from Haskell - Functional, Reusable JavaScript
- agscala 15y agoThe article mentions it already, but if this style of programming piques your interest and you don't know about underscore.js, it's absolutely worth your time to check it out: http://documentcloud.github.com/underscore/ http://documentcloud.github.com/underscore/
- _gingerhendrix 15y agoAnother (old but good) functional programming library is http://osteele.com/sources/javascript/functional/ http://osteele.com/sources/javascript/functional/
- ax 15y agoOne 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 agoYou 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 agoIn 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 agoWell, reduce is a recursion with an accumulator. Did you had something special in mind?
- eru 15y agoWhy would you write mind-boggling recursion by hand, and not use a nice combinator that comes pre-debugged?
- neutronicus 15y agoBecause I had a brain fart and though "reduce" was "scan", and I didn't want to initialize an array.
- samdk 15y agoThe 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).
- ufo 15y agoThe 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 agoYou 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 agoAlso using underscore, with sortBy: _.chain(people) .sortBy(function(person) { return person.firstName.length + person.lastName.length; }) .last() .value()
- mhansen 15y agoFYI, 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 agolongestName = maximumBy . comparing $ \(f,l) -> length $ f++l
- eru 15y agoThat 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 agoSimilar 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 agoIn 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 agoIn 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.
- freyrs3 15y agoOne might as well say "Learn from Lisp" or "Learn from ML" as there really isn't anything Haskell specific about these kind of higher order functions. If we want to learn from Haskell, the big ideas are functional purity and its type system.
- noblethrasher 15y agoThe biggest idea is probably laziness. In Haskell, everything is basically a function. Even the number 3 is really just a function that if and when evaluated will return the value 3. I used that concept to to simply some JavaScript UI code a while back. I had SELECT element that I needed to populate dynamically but wanted the last option to invoke an action that allowed the user to add another option choice 1 choice 2 choice 3 <add new choice> I ended up populating the dropdown list using a bunch of javascript functions that looked like this function () { return { key: 1, value: 'choice 1' } } function () { return { key: 2, value: 'choice 2' } } function () { return { key: 3, value: 'choice 3' } } function () { /* do stuff that creates a new choice */ } Not sure I would have thought of that if I had not first played with Haskell and grokked laziness.
- tumult 15y ago'In Haskell, everything is a function' is absolutely wrong. People who don't know much about Haskell often say this. There's a post by Conal Elliott about this incorrect meme: http://conal.net/blog/posts/everything-is-a-function-in-haskell http://conal.net/blog/posts/everything-is-a-function-in-hask... It's simply not true. In fact, because Haskell is statically typed, it's very easy to tell what's a function and what's not: If its type doesn't have an -> in it, it's not a function.
- noblethrasher 15y ago... I know that 3 is not literally function in the Haskell type system but it's an easy way to explain it to people less familiar with the language (not that I assume freyrs3 is one of those). Also, while it might be true that "people who don't know much about Haskell" often say that everything is a function, it's also the case that people who do know a lot about the language find the notion to be pedagogically useful: On page 13 of The Haskell School of Expression, Paul Hudak offers that pi (which is of type Floating a => a and thus clearly not a function) "can be thought of as a function with no arguments".
- dinedal 15y agoI like this style of programming, but isn't there cause for concern in having such a deep call stack in JS?
- gcr 15y agoYes. V8 and other JS compilers optimize tail calls, but it's not guaranteed by the standard. (i think IE doesn't, for example)
- mhansen 15y agoI'm not sure where you got this idea. V8 does not optimize tail calls. It's easy to see this in the Chrome console, I just entered this now: var a = function(x) { if (x == 0) return 'done'; return a(x-1); }; a(100000); RangeError: Maximum call stack size exceeded http://code.google.com/p/v8/issues/detail?id=457 http://code.google.com/p/v8/issues/detail?id=457
- gcr 15y agoWait, seriously? I didn't know that. Thanks for the link! Guess it's time for me to stop relying on that behavior...
- eru 15y agoYou could probably put a trampoline around it.
- DanWaterworth 15y agoI'm been experimenting with UHC's js backend. One of the things that struck me was that in Haskell if I have a function like: forever :: Monad m => m a -> m a I can use it for either asynchronous or synchronous javascript, e.g forever :: IO a -> IO a forever :: ContT r IO a -> ContT r IO a The same function can take a synchronous js function or an async js function and run it in an infinite loop. For this reason, I think that if you want to learn from Haskell in writing reusable js then you should look into monads.
- Martijn 15y agoSmall nitpick, the type of forever is actually: forever :: Monad m => m a -> m b Since it never returns a value, the resulting monadic action can be polymorphic in its return type.
- jacobr 15y agoGreat article, I learned a lot from http://blog.jcoglan.com/2011/03/05/translation-from-haskell-to-javascript-of-selected-portions-of-the-best-introduction-to-monads-ive-ever-read/ http://blog.jcoglan.com/2011/03/05/translation-from-haskell-... as well.
- arnoooooo 15y agoWhat bothers me in this with pure JS is the verbosity of "function (arg1,arg2) {return ...;}"
- dmmalam 15y agocoffescript's sugar is pretty nice (haskell inspired)? function (a,b) {return a+b} becomes (a,b) -> a+b Hopefully in harmony we will see a shorter function syntax for environments where CS isn't an option
- udp 15y agoNot having to write `function` everywhere is pretty much the reason I started using CoffeeScript.
- fein 15y agoWhy not just save snippets? I do this in emacs (yasnippet) all the time instead of constantly rewriting the same stub. Not knocking coffescript here, just saying that "I don't want to write a specific word" is a pretty terrible reason to pick any language over another.
- eru 15y agoI guess he also doesn't want to read it everywhere and clutter up his code.
- embwbam 15y agoThe idea is that once you define "apply" and its like, you don't have to write function () { return; } inline any more. You just use library-level functions and partially apply them. These techniques reduce the number of anonymous functions you create.
- twfarland 15y agoThe currying function shown can be made more flexible: var _slice = Array.prototype.slice; var curry = function() { var args = _slice.call(arguments); return function() { var args2 = _slice.call(arguments); return args[0].apply(this, args.slice(1).concat(args2)); }; }; As can the composition func: var compose = function(f, g) { return function() { var args =_slice.call(arguments); return f(g.apply(this, args)); }; };
- peteretep 15y agoFunnily enough, it was learning Javascript that made my Perl use a lot more higher-order functions, so when it came to Haskell, I was already on that page...